Algoritmo e Estrutura de
Dados I
Aulas 17 – Recursividade
Márcia Marra
[email protected]
Recursividade
•
•
•
•
Simplificam a solução de alguns problemas
Geralmente deixam o código mais conciso
São mais lentas que as funções iterativas
Erros na implementação podem levar a
“estouro” de pilha
• Exemplos clássicos:
– Cálculo de fatorial;
– Série de Fibonacci;
– Jogo da Torre de Hanoi
2
Fatorial
• Ex: Fatorial de 4
3
Fatorial - Solução
#include <stdio.h>
int fat (int n) {
if ( n =0) return 1;
else return n * fat (n-1);
}
int main() {
int num;
printf("\nDigite um valor para n: ");
scanf("%d", &num);
printf("\nO fatorial de %d é %d", num,
fat(num));
return 0;
}
4
Execução
5
Fibonacci
• A série de Fibonacci é formada de
maneira que o elemento seguinte é
composto pela soma dos dois elementos
anteriores.
1, 1, 2, 3, 5, 8, 13, 21 ...
• Fib (0) = 0
• Fib (1) = 1
• Fib (n) = Fib (n-1) + Fib (n-2)
6
Fibonacci - Solução
#include <stdio.h>
int fib (int n) {
if ( n==0) return 0;
else if (n==1) return 1;
else return fib(n-1)+ fib(n-2);
}
int main() {
int num;
printf("\nEntre com um valor para n: ");
scanf("%d", &num);
printf("\nFibonacci é %d", fib(num));
return 0;
}
7
Execução
8
Torre de Hanoi
• Considere três hastes, A, B e C.
• Na haste A encontram-se n discos, com tamanhos
diferentes, arrumados do menor maior, de cima baixo;
• Deve-se passar todos os discos da haste A para a haste
B, usando a haste C como auxiliar e seguindo algumas
regras.
9
Torre de Hanoi
• Regras do Jogo:
1. Somente um disco pode ser movido de
cada vez.
2. Nenhum disco pode ser colocado
sobre um disco menor.
3. Qualquer disco pode ser movido de
qualquer haste para qualquer outra
haste, desde que respeitada a regra 2.
10
Torre de Hanoi - Recursividade
• Suponha 4 discos, como no desenho abaixo.
Monte a pilha de execução para este exemplo.
11
Torre de Hanoi – pilha de execução
Disco 1 de A para C
Disco 2 de A para B
Disco 1 de C para B
Disco 3 de A para C
Disco 1 de B para A
Disco 2 de B para C
Disco 1 de A para C
Disco 4 de A para B
Disco 1 de C para B
Disco 2 de C para A
Disco 1 de B para A
Disco 3 de C para B
Disco 1 de A para C
Disco 2 de A para B
Disco 1 de C para B
12
Torre de Hanoi - Solução
#include <stdio.h>
int torre (int disco, char de, char para, char aux){
if (disco == 1)
printf ("\nMover disco %d da torre %c para a
torre %c", disco, de, para);
else {
torre (disco-1, de, aux, para);
printf ("\nMover disco %d da torre %c para a
torre %c", disco, de, para);
torre (disco-1, aux, para, de);
}
return(0);
}
13
Torre de Hanoi - Solução
int main () {
int num;
printf ("Digite a quantidade de
discos da torre A: ");
scanf ("%d", &num);
torre (num, 'A', 'B', 'C');
return(0);
}
14
Execução
15
Execução 2
16
Teste Surpresa
•
Use a função puzzle abaixo para responder as perguntas:
int puzzle(int base, int limit) {
//base and limit are nonnegative numbers
if ( base > limit ) return -1;
else if ( base == limit ) return 1;
else return base * puzzle(base + 1, limit);
}
1) Identifique os casos base da função puzzle();
2) Identifique o caso recursivo da função puzzle();
3) Mostre a pilha de execução e o que será impresso pelas seguintes
chamadas:
1) printf(“%d\n”, puzzle(14,10));
2) printf(“%d\n”, puzzle(4,7));
3) printf(“%d\n”, puzzle(0,0));
17