Recursividade (Suzana)

Prévia do material em texto

Recursividade
Aula 5
� Em matemática vários objetos são definidos 
apresentando-se um processo que os 
produz. 
� Ex PI (circunferência/diâmetro)
� Outra definição de um objeto por um 
processo é o fatorial de um número
� Fatorial(n) ou n! 
� = n*(n-1)*(n-2)...(2)*1 se n >0
� =1 se n==0
� Se formulamos:
� 0! = 0
� 1! = 1
� 2! = 2 * 1
� 3! = 3 * 2 * 1
� 4! = 4 * 3 * 2 * 1
� Não é possível listar a fórmula para fatorial de cada 
inteiro
� Para evitar qualquer abreviatura e um cjto infinito de 
definições poderemos apresentar um algoritmo que 
aceite um número inteiro n e retorne n!
prod = 1;
for (x = n; x > 0; x--)
prod *= x;
return prod;
ALGORITMO ITERATIVO: Requer de repetição 
explícita até uma condição ser satisfeita.
� Um algoritmo pode ser considerado “Um 
programa ideal” sem quaisquer limitações 
práticas de um computador real e portanto 
pode ser usado para definir uma função 
matemática, entretanto uma função de C não 
serve como definição matemática da função 
fatorial por causa de limitações como 
precisão e tamanho finito de uma máquina 
real.
� Examinemos detalhadamente a definição de n! que 
lista uma fórmula separada para cada valor de n
� Ex 4! = 4 * 3 * 2 * 1 isso é igual a 4 * 3! 
� Para todo n>0 verificamos que 
n! = n* (n-1)!
� Podemos definir:
0! = 1
1! = 1 * 0! 
2! = 2 * 1!
3! = 3 * 2!
4! = 4 * 3!
5! = 5 * 4!
� Se empregamos uma notação matemática temos 
que
� n! = 1 se n == 0
� n! = n * (n - 1)! se n >0
� Definição de uma função em termos de se mesma, 
aparentemente circular.
� Método conciso de escrever um número infinito de 
equações necessárias para definir n! 
� Definição RECURSIVA
� A recursividade pode ser utilizada quando um 
problema puder ser definido em termos de si 
próprio.
� Por exemplo, quando um objeto é colocado entre 
dois espelhos planos paralelos e frente a frente 
surge uma imagem recursiva, porque a imagem do 
objeto refletida num espelho passa a ser o objeto a 
ser refletido no outro espelho e, assim, 
sucessivamente.
� Uma função recursiva chama ela mesma, mas com 
outros parâmetros.
Algoritmos Recursivos
� A idéia básica de um algoritmo recursivo consiste em 
diminuir sucessivamente o problema em um problema 
menor ou mais simples, até que o tamanho ou a 
simplicidade do problema reduzido permita resolvê-lo de 
forma direta, sem recorrer a si mesmo.
� Quando isso ocorre, diz que o algoritmo atingiu uma 
condição de parada, a qual deve estar presente em pelo 
menos um local dentro algoritmo.
� Sem esta condição o algoritmo não pára de chamar a si 
mesmo, até estourar a capacidade da pilha de execução, o 
que geralmente causa efeitos colaterais e até mesmo o 
término indesejável do programa.
Componentes de um algoritmo
recursivo
� Condição de parada, quando a parte do 
problema pode ser resolvida diretamente, 
sem chamar de novo a função recursiva.
� Outros comandos que resolvem uma parte
do problema (chamando novamente a função
recursiva);
Algoritmos Recursivos
f1(..)
...
...
...
chama f1(..)
...
...
fim
f1(..)
...
...
...
condição de 
parada!
f1(..)
...
...
chama f1(..)
...
...
1. 5! = 5 * 4!
2. 4! = 4 * 3!
3. 3! = 3 * 2!
4. 2! = 2 * 1!
5. 1! = 1 * 0!
6. 0! = 1
Cada caso é reduzido a um caso mais simples até
chegarmos ao caso 0! Que é definido 
imediatamente como 1
Se voltarmos
6’ 0! = 1
5’ 1! = 1 * 0! = 1 * 1 = 1
4’ 2! = 2 * 1! = 2 * 1 = 2
3’ 3! = 3 * 2! = 3 * 2 = 6
2’ 4! = 4 * 3! = 4 * 6 = 24
1’ 5! = 5 * 4! = 5 * 24 = 120
� Se levamos esse processo a um algoritmo 
teremos
 if (n == 0) 
 fact = 1;
else {
x = n -1;
ache o valor de x!. Chame-o de y;
fact = n * y;}
Definição recursiva do processo do cálculo do 
fatorial
int main(void)
{ int NUMERO, RESULTADO;
scanf("%d", &NUMERO);
RESULTADO = FAT(NUMERO);
printf("%d\n", RESULTADO); }
int FAT(int N)
{ int AUX;
if(N == 1) // condição de parada
return 1;
AUX = N * FAT(N - 1);
return AUX; }
� LEMBRE-SE!! N é variável local da função FAT. 
� É melhor a definição recursiva de fatorial?
� Programa principal:
main
� NUMERO = 3
RESULTADO = 
FAT(3)
� Função FAT:
PRIMEIRA 
CHAMADA
� N = 3
AUX = 3 * FAT(2)
1
� Função FAT:
PRIMEIRA CHAMADA
� N = 3
AUX = 3 * FAT(2)
� Função FAT:
SEGUNDA CHAMADA
� N = 2
AUX = 2 * FAT(1)
1 2
� Função FAT:
SEGUNDA CHAMADA
� N = 2
AUX = 2 * FAT(1)
� Função FAT:
TERCEIRA CHAMADA
� N = 1
condição de parada
atingida!!!
if (N = = 1)
return 1;
2 3
� Função FAT:
SEGUNDA CHAMADA
� N = 2
AUX = 2 * FAT(1)
AUX = 2
� Função FAT:
TERCEIRA CHAMADA
� N = 1
condição de parada
atingida!!!
if (N = = 1)
return 1;
1
2 3
� Função FAT:
PRIMEIRA CHAMADA
� N = 3
AUX = 3 * FAT(2)
AUX = 6
� Função FAT:
SEGUNDA CHAMADA
� N = 2
AUX = 2 * FAT(1)
AUX = 2
12
21
� Programa principal:
main
� NUMERO = 3
RESULTADO = FAT(3)
RESULTADO = 6
� Função FAT:
PRIMEIRA CHAMADA
� N = 3
AUX = 3 * FAT(2)
AUX = 6
2
6
1
Problemas associados a 
recursividade
� ����������	���
���
����
�����
� �����	����
����
����
���� 	��� �� �������
���������� ��
���� �����
�� � ���� ��
������
������
� 	�����������
����
��������
��
��� ��� 
��
�� ������ �� 
��� ����� �
����� ��
�������� ���
����� ���������� !
� ��� ������"����� ���������� ����� 
��
����"�
������
��������
������	�����
�����
��� �#������� ��� 
����
�$� ���� ��
�� ���
�����%������ �����
������
����
����!
Multiplicação de números 
naturais
� Outro exemplo de definição recursiva
� O produto A*B em que a e b são inteiros 
positivos pode ser definido como A somado a 
si mesmo b vezes. Essa definição é
ITERATIVA
� Definição recursiva
a * b = a se b == 1
a * b = a * (b - 1) + a se b > 1
� Exemplo:
6 * 3 = 6 * 2 + 6 = 6 * 1 + 6 + 6 = 6 + 6 + 6 = 18
Exercício: Converter num algoritmo recursivo.
Observe padrão de definições recursivas (caso 
simples e avaliação de casos mais simples)
Por que não podemos usar definições como...?
n! = (n + 1)! / (n + 1)
a * b = a * (b + 1) - a
A seqüência de Fibonacci
� Seqüência de inteiros do tipo
� 0, 1, 1, 2, 3, 5, 8, 13, 21, 34
� Cada elemento da seqüência é a soma dos dois 
elementos anteriores. Se permitimos que fib(0) = 0 
e fib(1) = 1
� fib(n) = n se n == 0 ou n == 1
� fib(n) = fib(n-2) + fib(n-1) se n >= 2
� Qual a diferença entre a definição da seqüência de 
Fibonacci e a do fatorial e da multiplicação dos 
números naturais?
A seqüência de Fibonacci
� Note que:
� fib(6) = fib(5) + fib(4) 
� = fib(4) + fib(3) + fib(3) + fib(2) 
� = fib(3) + fib(2) + fib(3) + fib(3) + fib(2)
E assim por diante. Que há de errado?
Seria mais eficiente lembrar quanto é fib(3) na primeira 
vez que ele for chamado
Solução iterativa:
if (n <= 1)
return(n);
lofib = 0;
hifib = 1;
for (i = 2; i <= n; i++)
{
x = lofib;
lofib = hifib;
hifib = x + lofib;
}
return hifib;
Solução recursiva
FIB(5)
FIB(5)
FIB(3)FIB(4)
FIB(5)
FIB(3)FIB(4)
FIB(3) FIB(2)
FIB(5)
FIB(3)FIB(4)
FIB(3) FIB(2) FIB(2) FIB(1)
FIB(5)
FIB(3)FIB(4)
FIB(3) FIB(2) FIB(2) FIB(1)
FIB(1)FIB(2)
FIB(5)
FIB(3)FIB(4)
FIB(3) FIB(2) FIB(2) FIB(1)
FIB(1)1
FIB(5)
FIB(3)FIB(4)
FIB(3) FIB(2) FIB(2) FIB(1)
11
FIB(5)
FIB(3)FIB(4)
2 FIB(2) FIB(2) FIB(1)
11
FIB(5)
FIB(3)FIB(4)
2 FIB(2) FIB(1)
11
1
FIB(5)
FIB(3)FIB(4)
2 FIB(1)
11
1 1
FIB(5)
FIB(3)FIB(4)
2
11
1 1 1
FIB(5)
FIB(3)3
2
11
1 1 1
23
2
11
1 1 1
FIB(5)
5
23
2
11
1 1 1
Resposta: O 5º termo da sérieé 5.
Torres de Hanoi
� Problema criado pelo matemático francês Edouard
Lucas, em 1883;
� 3 torres;
� x discos de vários tamanhos na primeira torre;
� Objetivo: transportar os discos, 1 a 1, para a terceira
torre;
� Regras:
� nunca colocar um disco maior sobre um disco menor; 
� pode-se mover um único disco por vez; 
� nunca colocar um disco noutro lugar que não numa das 
três hastes.
Torres de Hanoi
Torres de Hanoi
� Lucas também criou uma “lenda” que dizia que em
Benares, durante o reinado do imperador Fo Hi, 
existia um templo que marcaria o centro do 
universo. Dentro deste templo, alguns monges
moviam discos de ouro entre 3 torres de diamante. 
Deus colocou 64 discos de ouro em uma das torres
na hora da criação do universo. Diz-se que, quando
os monges completarem a tarefa de transportar
todos os discos para a terceira torre, o universo
terminará. 
� (como vai levar pelo menos 264 - 1 movimentos para
completar a tarefa, estamos a salvo por enquanto. 
Assumindo que os monges realizem 1 movimento
por segundo, e não cometam erros, eles irão levar
um total de 585,000,000,000 anos.)
Como resolver?
� Sejam 4 discos na torre 1.
� Problema principal: Mover 4 discos da torre 1 
para a torre 3.
Recursão!
� Mover 4 discos da torre 1 para a torre 3:
� mover 3 discos da torre 1 para a torre 2;
� mover 1 disco da torre 1 para a torre 3;
� mover 3 discos da torre 2 para a torre 3. 
Recursão!
� Mover 4 discos da torre 1 para a torre 3:
• mover 3 discos da torre 1 para a torre 2;
• mover 1 disco da torre 1 para a torre 3;
• mover 3 discos da torre 2 para a torre 3. 
Recursão!
� Mover 4 discos da torre 1 para a torre 3:
• mover 3 discos da torre 1 para a torre 2;
• mover 1 disco da torre 1 para a torre 3;
• mover 3 discos da torre 2 para a torre 3. 
Recursão!
� Mover 4 discos da torre 1 para a torre 3:
• mover 3 discos da torre 1 para a torre 2;
• mover 1 disco da torre 1 para a torre 3;
• mover 3 discos da torre 2 para a torre 3. 
Divisão do problema
� Logo o problema principal:
� Mover 4 discos da torre 1 para a torre 3
� Se transforma em um problema menor:
� mover 3 discos da torre 1 para a torre 2;
� mover 1 disco da torre 1 para a torre 3;
� mover 3 discos da torre 2 para a torre 3. 
� Mas, como mover 3 discos?
Divisão do problema
� Mover 3 discos da torre 1 para a torre 2:
� mover 2 discos da torre 1 para a torre 3;
� mover 1 disco da torre 1 para a torre 2;
� mover 2 discos da torre 3 para a torre 2. 
Divisão do problema
� Mover 3 discos da torre 1 para a torre 2:
• mover 2 discos da torre 1 para a torre 3;
• mover 1 disco da torre 1 para a torre 2;
• mover 2 discos da torre 3 para a torre 2. 
Divisão do problema
� Mover 3 discos da torre 1 para a torre 2:
• mover 2 discos da torre 1 para a torre 3;
• mover 1 disco da torre 1 para a torre 2;
• mover 2 discos da torre 3 para a torre 2.
Divisão do problema
� Mover 3 discos da torre 1 para a torre 2:
• mover 2 discos da torre 1 para a torre 3;
• mover 1 disco da torre 1 para a torre 2;
• mover 2 discos da torre 3 para a torre 2. 
Algoritmo
� Mover x discos, da torre a para a torre b:
� mover (x-1) discos, da torre a para a torre c
� mover 1 disco da torre a para a torre b
� mover (x-1) discos, da torre c para a torre b
� Função de parada:
� Se o número de discos = 1, move direto.
Observações
� Sejam 3 torres, com os números 1, 2 e 3.
� Dadas 2 torres, como descobrir qual a 
terceira?
� Isto é, dadas as torres 1 e 3, como descobrir
que a outra torre é a 2?
� Dadas as torres 2 e 3, como descobrir que a 
outra torre é a 1?
Observação
� Note: 1 + 2 + 3 = 6
� Logo: A outra torre é
6 - (soma das torres indicadas)
� Exemplos:
� torres 1 e 2
� Outra torre: 6 - (1 + 2) = 6 - 3 = 3
� torres 2 e 3
� Outra torre: 6 - (2 + 3) = 6 - 5 = 1
Solução
void HANOI(int ND, int DE, int PARA)
{
int OUTRA_TORRE = 6 - (DE + PARA);
if(ND == 1)
{
printf("Mover disco da torre %d para a
torre %d.\n", DE, PARA);
return;
}
HANOI(ND-1, DE, OUTRA_TORRE);
HANOI(1, DE, PARA);
HANOI(ND-1, OUTRA_TORRE, PARA);
return;
}
Solução
Digite o numero de discos: 4
Mover disco da torre 1 para a torre 2.
Mover disco da torre 1 para a torre 3.
Mover disco da torre 2 para a torre 3.
Mover disco da torre 1 para a torre 2.
Mover disco da torre 3 para a torre 1.
Mover disco da torre 3 para a torre 2.
Mover disco da torre 1 para a torre 2.
Mover disco da torre 1 para a torre 3.
Mover disco da torre 2 para a torre 3.
Mover disco da torre 2 para a torre 1.
Mover disco da torre 3 para a torre 1.
Mover disco da torre 2 para a torre 3.
Mover disco da torre 1 para a torre 2.
Mover disco da torre 1 para a torre 3.
Mover disco da torre 2 para a torre 3.
Pressione qualquer tecla para continuar . . .
� Mover disco da torre 1 para a torre 2.
� Mover disco da torre 1 para a torre 3.
� Mover disco da torre 2 para a torre 3.
� Mover disco da torre 1 para a torre 2.
� Mover disco da torre 3 para a torre 1.
� Mover disco da torre 3 para a torre 2.
� Mover disco da torre 1 para a torre 2.
� Mover disco da torre 1 para a torre 3.
� Mover disco da torre 2 para a torre 3.
� Mover disco da torre 2 para a torre 1.
� Mover disco da torre 3 para a torre 1.
� Mover disco da torre 2 para a torre 3.
� Mover disco da torre 1 para a torre 2.
� Mover disco da torre 1 para a torre 3.
� Existem linguagens de programação que não 
suportam recursividade como FORTRAN, COBOL e 
muitas linguagens de máquina
� Soluções recursivas podem ser simuladas se 
entendermos o conceito e funcionamento da 
recursividade
� Não é raro que um programador consiga enunciar 
uma solução recursiva para um problema. Às vezes 
a solução recursiva é a mais natural e simples, 
mas as soluções recursivas são com freqüência 
mais dispendiosas que a solução não recursiva.
� Em geral uma solução não recursiva de um programa executará
com mais eficiência em termos de espaço e tempo. Isso 
acontece porque a solução não recursiva evita o trabalho extra 
de entrar e sair de um bloco e o empilhamento de desnecessário 
de variáveis 
� Contudo, verificaremos que a solução recursiva é às vezes o 
método mais natural e lógico de desenvolver, como é o caso das 
torres de Hanoi, e menos propenso a erros
� Conflito EFICIÊNCIA DA MÁQUINA X EFICIÊNCIA DO 
PROGRAMADOR
� Nestes casos, versões simuladas dos casos recursivos são uma 
excelente solução
� Que acontece quando uma função é chamada?
1. Passar argumentos: para um parâmetro em C 
uma cópia é criada localmente dentro da função e 
qualquer mudança é feita nessa cópia local. O 
original não é alterado
2. Alocar e inicializar variáveis locais: depois que os 
argumentos forem passados, as variáveis locais da 
função serão alocadas (as diretamente 
declaradas na função e as temporárias)
3. Transferir o controle para a função: deve ser 
passado o endereço de retorno como parâmetro
� Quando retorna, que acontece?
1. O endereço de retorno é recuperado e 
armazenado num lugar seguro
2. A área de dados da função é liberada
3. Usa-se um desvio para o endereço de 
retorno salvo anteriormente; deve-se também 
salvar os valores de retorno para que o 
chamador possa recuperar esse valor.
Chamada de b Chamada de c
Endereço de
retorno
Chamada de d
Endereço de
retorno
Endereço de
retorno
controle
Programa principal Procedimento b Procedimento c Procedimento d
Chamada de b Chamada de c
Endereço de
retorno
Chamada de d
Endereço de
retorno
controle
Programa principal Procedimento b Procedimento c
� Observe que a seqüência de endereços de retorno 
forma uma pilha, isto é, o mais recente endereçode 
retorno a ser incluído na cadeia é o primeiro a ser 
removido. Em qualquer ponto só poderemos 
acessar o endereço de retorno a partir da função 
atualmente em execução, que representa o topo da 
pilha. Quando uma pilha for esvaziada (isto é, quando 
a função retornar), será revelado um novo topo 
dentro da rotina de chamadas.
� Chamar uma função tem o efeito de incluir um 
elemento numa pilha; retornar da função, de 
eliminá-lo
� Cada vez que uma função recursiva chama a 
si mesma, uma área de dados totalmente 
nova para essa chamada precisa ser 
alocada. Essa área contem todos os 
parâmetros, variáveis locais, temporárias e 
endereços de retorno. Todo retorno acarreta a 
liberação da atual área de dados. Sugere-se 
o uso de uma pilha
� Poderemos usar uma estrutura do tipo
#define MAXPILHA 50;
struct pilha{
int topo;
struct dados item[MAXPILHA]
}
� Passos da conversão
� Desenvolver caso recursivo
� Desenvolver simulação com todas as pilhas e temporários
� Eliminar todas as pilhas e variáveis supérfluas
� Quando uma pilha não pode ser eliminada da versão 
não recursiva e quando a versão recursiva não 
contém nenhum dos parâmetros adicionais ou variáveis 
locais, a versão recursiva pode ser tão ou mais veloz 
que a não recursiva, sob um compilador eficiente. 
Exemplo: Torres de Hanoi
� O fatorial que não precisa pilha na 
implementação não recursiva e a geração 
de números de fibonacci onde temos uma 
chamada desnecessária e também não 
precisa de pilha a solução recursiva deve ser 
evitada na prática
� Até onde uma solução recursiva pode ser 
transformada em direta dependerá do 
problema e da engenhosidad do 
programador