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