Recursividade Estrutura de Dados Definição Um algoritmo é dito recursivo quando ele chama a si mesmo ou chama uma seqüência de outros algoritmos, e um deles chama novamente o primeiro algoritmo. Estrutura de Dados Recursividade Divisão do problema original em pequenas ocorrências Dividir para conquistar (divide and conquer) A dificuldade não está só no reconhecimento das situações Mas também no equilíbrio entre espaço (memória ocupada) e tempo (tempo de execução) E manter ao mesmo tempo uma boa compreensão da solução do problema Estrutura de Dados A função fatorial n! = n x (n-1) x . . .x 1 Uma definição mais precisa se n 0 1 n! n * (n - 1)! se n 0 Calculando 4 ! usando a última definição, faríamos: 4! = 4 x 3! = 4 x (3 x 2!) = 4 x (3 x (2 x 1)) = 4 x (3 x (2 x (1 x 0!))). = 4 x (3 x (2 x (1 x 1))) = 4 x (3 x (2 x 1)) = 4 x (3 x 2) =4x6 = 24 Estrutura de Dados Todo processo recursivo consiste de duas partes Solução trivial: Dada por definição, obtida sem recursão. Solução geral: Parte do problema que em essência é igual ao problema original, sendo porém menor. Estrutura de Dados Versão recursiva para calcular o fatorial /* fatorial Pré-condição Pós-condição */ : versão recursiva : n é um inteiro não negativo : retorna o valor do fatorial de n int fatorial(int n) { if(n == 0) return 1; else return n*fatorial(n-1); } Estrutura de Dados Chamando a função: fatorial(3) Estrutura de Dados Utilizando árvore de recursão float ex(float a, float b) { if (a >= b) return((a+b)/2); else return(ex(ex(a+2,b-1),ex(a+1, b-2))); } Estrutura de Dados Utilizando árvore de recursão Estrutura de Dados Rotinas recursivas e pilhas Controle de chamadas e retornos de rotinas com pilha Quando uma rotina é chamada, empilha-se o endereço de retorno + todas as variáveis locais Quando ocorre o retorno da rotina, as variáveis locais que foram criadas deixam de existir Estrutura de Dados Observações sobre um algoritmo recursivo Pode ser conciso e elegante Pode ser difícil a compreensão dos detalhes de seu funcionamento computacional Pode requerer um exaustivo acompanhamento do programa O computador pode utilizar pilhas para esse controle A mente humana não é tão boa para tais tarefas Parece ser difícil para uma pessoa guardar uma longa seqüência de resultados e então voltar para terminar um trabalho Estrutura de Dados Para facilitar o acompanhamento, podemos utilizar Ilustrações especiais Árvores de Recursão Estrutura de Dados Alguns resultados mdc (6,12) = 6 mdc (12,20) = 4 mdc (20,24) = 4 Estrutura de Dados Desenvolvendo algoritmos recursivos Ache o passo chave Ache uma regra de parada Como este problema pode ser dividido? Como posso desenvolver o passo chave da solução? Uma regra de parada indica que o problema ou uma parte razoável do mesmo foi feito Ela é geralmente pequena e dá a solução trivial, sem a necessidade da recursão Monte seu algoritmo Combine a regra de parada e o “passo chave” usando uma instrução if Estrutura de Dados Desenvolvendo algoritmos recursivos Verifique o término Certificar que a recursão sempre terminará Comece com uma situação geral Verifique se num número finito de passos, a regra de parada será satisfeita e a recursão termina Desenhe uma árvore de recursão É a ferramenta chave para analisar algoritmos recursivos Estrutura de Dados