27
SEGURANÇA DA INFORMAÇÃO SI-3 LINGUAGEM DE PROGRAMAÇÃO. “RECURSIVIDADE” Assuntos abordados : Conceito de recursividade Recursividades(Função recursiva) Algoritmos comentados usando Funções recursivas FACULDADE SENAC Prof.: Alice Alunos : Mackley MAURICIO Pedro costa Rogério vinicius wanderson

Apresentação recursividade rev2

Embed Size (px)

Citation preview

Page 1: Apresentação recursividade rev2

SEGURANÇA DA INFORMAÇÃO

SI-3LINGUAGEM DE PROGRAMAÇÃO.

“RECURSIVIDADE”

Assuntos abordados :

• Conceito de recursividade• Recursividades(Função recursiva)• Algoritmos comentados usando

Funções recursivas

FACULDADE SENAC

Prof.: Alice

Alunos :Mackley MAURICIO Pedro costaRogérioviniciuswanderson

Page 2: Apresentação recursividade rev2

RECURSIVIDADE - FUNÇÕES RECURSIVAS

A Recursividade é um recurso de programação,onde uma função pode chamar a si própria.

Para utilizar a função recursiva é fundamental estabelecer um critério de parada, ou seja ,um parâmetro que determine quando a função deverá parar de chamar a si mesma.

Isto impede que a função se chame infinitas vezes.

paradigma de programação dinâmica

Page 3: Apresentação recursividade rev2

RECURSIVIDADE - FUNÇÕES RECURSIVAS

Técnica de programação que permite funções

chamarem a si mesmas

Pode ser aplicada sobre problemas que requerem que os mesmos passos

sejam executados diversas vezes...

Page 4: Apresentação recursividade rev2

As funções recursivas se assemelham a loops.

Contudo exige condição de parada no momento em que o problema é resolvido.

RECURSIVIDADE - FUNÇÕES RECURSIVAS

Page 5: Apresentação recursividade rev2

Condição de parada- quando referenciamo-nos neste quesito,indicamos que a mesma solução é aplicada várias vezes até que o problema seja resolvido.

A condição de parada é aquela situação na qual o problema já foi resolvido,neste caso a solução do problema não será necessário aplicar aquela mesma solução repetidas vezes.

RECURSIVIDADE - FUNÇÕES RECURSIVAS

Page 6: Apresentação recursividade rev2

Problemas podem ser solucionados tanto por recursão como com iteração.

Existem outros tipos de problemas cujas soluções são inerentemente recursivas, já que elas precisam manter registros de estados anteriores. Um exemplo é o percurso de uma árvore; outros exemplos incluem a função de Ackermann e algoritmos de divisão e conquista, tais como oQuicksort. Todos estes algoritmos podem ser implementados iterativamente com a ajuda de uma pilha, mas o uso de uma pilha, de certa forma, anula as vantagens das soluções iterativas.

Porque fazermos recursão e não interação ?

Vantagem:

Desvantagem:

RECURSIVIDADE VS ITERAÇÕES

Código Simplificado Elegante

Tempo de processamento Memória

Page 7: Apresentação recursividade rev2

Recursão em Cauda

Recursão Indireta

Recursão Aninhada

TIPOS DE RECURSÃO

Chamada recursiva ao final da função.

Chamada através de outras funções.Análise de Expressões: 3 + (2 * (4 +

4)).

Chamada recursiva com um dos seus parâmetros chama a própria função.

Page 8: Apresentação recursividade rev2

As funções recursivas em cauda formam uma subclasse das funções recursivas, nas quais a chamada recursiva é a última instrução a ser executada. Por exemplo, a função a seguir, para localizar um valor em uma lista ligada é recursiva em cauda, por que a última coisa que ela faz é invocar a si mesma:

EXEMPLO:registro noh dado: inteiro *proximo: registro nohfim_registro *acha_valor(*cabeca: registro noh, valor: inteiro): registro nohinicio se cabeca = NULO então acha_valor <- NULO senão se cabeça.dado = valor então acha_valor <- cabeca senão acha_valor <- acha_valor(cabeca.proximo, valor) fim_sefim

RECURSIVIDADE EM CAUDA

Page 9: Apresentação recursividade rev2

Funções podem ser recursivas (invocar a si próprias) indiretamente, fazendo isto através de outras funções: assim, "P" pode chamar "Q" que chama "R" e assim por diante, até que "P" seja novamente invocada.

Um exemplo é a análise de expressões. Suponha que você tem um analisador sintático para cada tipo de sub-expressão, e tenha uma expressão "3 + (2 * (4 + 4))". A função que processa expressões "+" chamaria uma segunda função que processaria expressões "*", que, por sua vez, chamaria novamente a primeira.

RECURSÃO INDIRETA

Page 10: Apresentação recursividade rev2

Uma chamada recursiva pode receber um argumento que inclui uma outra chamada recursiva. Um exemplo é a função de Ackermann, uma função que cresce de forma incrivelmente rápida.

EXEMPLO:função ack(n: inteiro, m: inteiro): inteiroinicio se n = 0 então ack <- m + 1 senão se n > 0 E m = 0 então ack <- ack(n - 1, m) senão ack <- ack(n - 1, ack(n, m - 1)) fim_sefim

RECURSÃO ANINHADA

Page 11: Apresentação recursividade rev2

Loop Infinito

Falha de segmentação

Estouro de Pilha

Complexidade

PRINCIPAIS ERROS

Geralmente ocasionado pelo mal entendimento do programador.

“Segmentation fault” – Acesso indevido a memória.

Ocasionado por muitas chamadas.

Entendimento e implementação.

Page 12: Apresentação recursividade rev2

If( topo_da_escada){ para else retornar_atividade }

RECURSIVIDADE - FUNÇÕES RECURSIVAS

Page 13: Apresentação recursividade rev2

FAT(4)= 4 X 3 X 2 X 1

FAT(3)= 3 X 2 X 1

FAT(2)= 2 X 1

FAT(1)= 1

RECURSIVIDADE - FATORIAL

Page 14: Apresentação recursividade rev2

RECURSIVIDADE - FATORIAL

FAT(4)= 4 X FAT(4)

FAT(3)= 3 X FAT(3)

FAT(2)= 2 X FAT(1)FAT(1)= 1 X FAT(0)

Page 15: Apresentação recursividade rev2

FATORIAL

#include<stdio.h>#include<stdlib.h>

int fatorial (num){ if(num ==0) return 1; else return num * fatorial(num-

1);}

#include<stdio.h>#include<stdlib.h>

int fatorial (num){ if(num ==0) return 1; else return num * fatorial(num-

1);}

num=3

num=2

Page 16: Apresentação recursividade rev2

FATORIAL

#include<stdio.h>#include<stdlib.h>

int fatorial (num){ if(num ==0) return 1; else return num * fatorial(num-

1);}

#include<stdio.h>#include<stdlib.h>

int fatorial (num==0){ if(num ==0) return 1; else return num * fatorial(num-

1);}

num=1

num=0

Page 17: Apresentação recursividade rev2

FATORIAL

#include<stdio.h>#include<stdlib.h>

int fatorial (num){ if(num ==0) return 1; else return num * fatorial(num-

1);}

#include<stdio.h>#include<stdlib.h>

int fatorial (num==0){ if(num ==0) return 1; else return num * fatorial(num-

1);}

num=1

num=0

1 1

Page 18: Apresentação recursividade rev2

FATORIAL

#include<stdio.h>#include<stdlib.h>

int fatorial (num){ if(num ==0) return 1; else return num * fatorial(num-

1);}

#include<stdio.h>#include<stdlib.h>

int fatorial (num){ if(num ==0) return 1; else return num * fatorial(num-

1);}

num=3

num=2

6 1

Page 19: Apresentação recursividade rev2

EXEMPLO DE CÓDIGO RECURSIVO USANDO POTÊNCIA

Page 20: Apresentação recursividade rev2

potencia (base , expoente) base=5 expoente =3

If (y==0) return 1 ; else return x* potencia (x,y-1) ; x=5 y= 2

If (y==0) return 1 ; else return x* potencia (x,y-1) ; x=5 y=3

If (y==0) return 1 ;else return x* potencia (x,y-1) ; x=5 y= 1

If (y==0) return 1 ; else return x* potencia (x,y-1) ; x=5 y= 0

FUNÇÃO RECURSIVA ,USANDO POTÊNCIA

Page 21: Apresentação recursividade rev2

potencia (base , expoente) base=5 expoente =3

If (y==0) return 1 ; else return x* potencia (x,y-1) ; x=5 y= 2

If (y==0) return 1 ; else return x* potencia (x,y-1) ; x=5 y=3

If (y==0) return 1 ;else return x * 1 x=5 y= 1

FUNÇÃO RECURSIVA ,USANDO POTÊNCIA

Page 22: Apresentação recursividade rev2

potencia (base , expoente) base=5 expoente =3

If (y==0) return 1 ; else return x* potencia (x,y-1) ; x=5 y= 2

If (y==0) return 1 ; else return x * 5 ; x=5 y=2

FUNÇÃO RECURSIVA ,USANDO POTÊNCIA

Page 23: Apresentação recursividade rev2

potencia (base , expoente) base=5 expoente =3

If (y==0) return 1 ; else return x * 25 ; x=5 y= 2

If (y==0) return 1 ; else return x * 5 ; x=5 y=2

FUNÇÃO RECURSIVA ,USANDO POTÊNCIA

Page 24: Apresentação recursividade rev2

potencia (base , expoente) base=5 expoente =3

If (y==0) return 1 ; else return x * 25 ; x=5 y= 2

125

FUNÇÃO RECURSIVA ,USANDO POTÊNCIA

Page 25: Apresentação recursividade rev2

void stringinv_aux (char * s, int i, int j){

if ( j - i > 2){

stringinv_aux (s, i + 1, j – 1); // Inverter a sub-string.}

// Trocar os caracteres extreinos.

char aux = s[j];

s[j] = s[i]; s[i] = aux;

}

void stringinv(char * str){

stringinv_aux(str, 0, strlen(str));

}

INVERSÃO DE UMA STRING

Page 26: Apresentação recursividade rev2

#include <iostream.h>

void esc_numero1(int num){

if (num > 0)

esc_numero1(num-1);

cout << num << " ";

}

void esc_numero2(int num){

if (num > 0)

cout << num << " ";

esc_numero2(num-1);

}

int main(){

int numero=0;

cout << "Introduza o numero inicial (>0)";

cin >> numero;

esc_numero1(numero);

cout << endl;

esc_numero2(numero);

}

ESCREVER UMA SEQUÊNCIA DE NÚMEROS NA VERTICAL

Page 27: Apresentação recursividade rev2

Exemplo 1:

#include <iostream>

int res(int numerador, int denominador);

int res(int x, int y){

if (x < y) return(x);

return( res (x – y, y) );

}

Exemplo 2:

#include <iostream>

long int mult(int x, int y);

long int mult(int x, int y){

if (y == 1)

return (x);

else

return(x + mult(x, y-1));

}

CALCULO DO RESTO DA DIVISÃO DE DOIS NÚMEROS