Aula 12 Recursividade em C

Prévia do material em texto

Recursividade
Profa Mariá Cristina Vasconcelos Nascimento
Baseada na aula de Monael Pinheiro Ribeiro, IME-USP
Fatorial
#include <stdio.h>
 
 /* calcula o fatorial de n. Assume que n>=0 */
 int fatorial( int n )
 {
 int i,p;
 
 p = 1;
 for( i=2; i<=n; i++ )
 p = p * i;
 return p;
 } 
 Este problema também pode ser resolvido de maneira 
recursiva. 
 O fatorial de um número n pode ser definido como n! = 1 
x 2 x 3 x ... x n, mas também pode ser definido 
recursivamente (ou por recorrência) através das seguintes 
duas regras: 
n! = 1 , se n=0 
n! = n(n-1)! , se n>0 
 Neste caso, definimos a função fatorial em termos da própria 
função fatorial. Este é o conceito fundamental da 
recursividade.
 Trata-se de uma maneira especial de resolver problemas em 
que a ideia chave é resolver o problema em termos de uma 
instância menor do próprio problema.
 A dimensão do problema vai sendo sucessivamente reduzida e 
eventualmente atinge-se um caso base em que a recursividade 
pára. 
 /* calcula o fatorial de n. Assuma que n>=0 */
 int fatorial( int n )
 {
 if( n==0 ) 
 return 1;
 else
 return n * fatorial(n-1);
 }
 O modo como está programado é uma tradução 
direta das duas regras que definem o fatorial. 
 A primeira é o caso base, a segunda é o caso 
recursivo. 
 Para melhor se perceber o modo como a função 
funciona, é útil vermos o modo como a computação 
é executada internamente no computador. 
 Para cada chamada de uma função, recursiva ou não, 
os parâmetros e as variáveis locais são empilhados 
na pilha de execução.
 Internamente, quando qualquer chamada de função é feita 
dentro de um programa, é criado um Registro de Ativação na 
Pilha de Execução do programa.
 O registro de ativação armazena os parâmetros e variáveis 
locais da função bem como o “ponto de retorno” no 
programa ou subprograma que chamou essa função.
 Ao final da execução dessa função, o registro é desempilhado 
e a execução volta ao subprograma que chamou a função.
 No caso da função ser definida de modo não 
recursivo, são necessárias duas variáveis, i e p para 
armazenar o estado da computação. 
 Por exemplo, ao calcular o fatorial de 6, o 
computador vai passar sucessivamente pelos 
seguintes estados: 
 i p
 === ===
 1 1
 2 2
 3 6
 4 24
 5 120
 6 720
 Para calcular o fatorial de 6 utilizando uma função 
recursiva, o computador tem:
1. Calcular o fatorial de 5 e só depois é que faz a 
multiplicação de 6 pelo resultado (120).
2. Por sua vez, para calcular o fatorial de 5, vai ter de 
calcular o fatorial de 4. 
3. E por aí fora até esbarrar no caso base. 
/* calcula o fatorial de n. Assuma que n>=0 */
 int fatorial( int n )
 {
 if( n==0 ) 
 return 1;
 else
 return n * fatorial(n-1);
 }
void main(){
 double fat=fatorial(6);
}
/* calcula o fatorial de n. Assuma que n>=0 */
 int fatorial( int n ) //n=6
 {
 if( n==0 ) 
 return 1;
 else
 return n * fatorial(n-1);
 }
/* calcula o fatorial de n. Assuma que n>=0 */
 int fatorial( int n ) //n=6
 {
 if( n==0 ) 
 return 1;
 else
 return 6* fatorial(5);/* -> empilha na pilha de execução 
as variáveis, o ponto de retorno (esta linha da função)*/
 }
Pilha de execução
6*fatorial(5)
/* calcula o fatorial de n. Assuma que n>=0 */
 int fatorial( int n ) //n=5
 {
 if( n==0 ) 
 return 1;
 else
 return n * fatorial(n-1);
 }
/* calcula o fatorial de n. Assuma que n>=0 */
 int fatorial( int n ) //n=5
 {
 if( n==0 ) 
 return 1;
 else
 return 5* fatorial(4);/* -> empilha na pilha de execução 
as variáveis, o ponto de retorno (esta linha da função)*/
 }
Pilha de execução
5*fatorial(4)
6*fatorial(5)
/* calcula o fatorial de n. Assuma que n>=0 */
 int fatorial( int n ) //n=4
 {
 if( n==0 ) 
 return 1;
 else
 return n * fatorial(n-1);
 }
/* calcula o fatorial de n. Assuma que n>=0 */
 int fatorial( int n ) //n=4
 {
 if( n==0 ) 
 return 1;
 else
 return 4* fatorial(3);/* -> empilha na pilha de execução 
as variáveis, o ponto de retorno (esta linha da função)*/
 }
Pilha de execução
4*fatorial(3)
5*fatorial(4)
6*fatorial(5)
/* calcula o fatorial de n. Assuma que n>=0 */
 int fatorial( int n ) //n=3
 {
 if( n==0 ) 
 return 1;
 else
 return n * fatorial(n-1);
 }
/* calcula o fatorial de n. Assuma que n>=0 */
 int fatorial( int n ) //n=3
 {
 if( n==0 ) 
 return 1;
 else
 return 3* fatorial(2);/* -> empilha na pilha de execução 
as variáveis, o ponto de retorno (esta linha da função)*/
 }
Pilha de execução
3*fatorial(2)
4*fatorial(3)
5*fatorial(4)
6*fatorial(5)
/* calcula o fatorial de n. Assuma que n>=0 */
 int fatorial( int n ) //n=2
 {
 if( n==0 ) 
 return 1;
 else
 return n * fatorial(n-1);
 }
/* calcula o fatorial de n. Assuma que n>=0 */
 int fatorial( int n ) //n=2
 {
 if( n==0 ) 
 return 1;
 else
 return 2* fatorial(1);/* -> empilha na pilha de execução 
as variáveis, o ponto de retorno (esta linha da função)*/
 }
Pilha de execução
2*fatorial(1)
3*fatorial(2)
4*fatorial(3)
5*fatorial(4)
6*fatorial(5)
/* calcula o fatorial de n. Assuma que n>=0 */
 int fatorial( int n ) //n=1
 {
 if( n==0 ) 
 return 1;
 else
 return n * fatorial(n-1);
 }
/* calcula o fatorial de n. Assuma que n>=0 */
 int fatorial( int n ) //n=1
 {
 if( n==0 ) 
 return 1;
 else
 return 1* fatorial(0);/* -> empilha na pilha de execução 
as variáveis, o ponto de retorno (esta linha da função)*/
 }
Pilha de execução
1*fatorial(0)
2*fatorial(1)
3*fatorial(2)
4*fatorial(3)
5*fatorial(4)
6*fatorial(5)
/* calcula o fatorial de n. Assuma que n>=0 */
 int fatorial( int n ) //n=0
 {
 if( n==0 ) 
 return 1;
 else
 return n * fatorial(n-1);
 }
/* calcula o fatorial de n. Assuma que n>=0 */
 int fatorial( int n ) //n=0
 {
 if( n==0 ) 
 return 1;
 else
 return n * fatorial(n-1);
 }
Pilha de execução
1*fatorial(0)
2*fatorial(1)
3*fatorial(2)
4*fatorial(3)
5*fatorial(4)
6*fatorial(5)
1*1
Pilha de execução
2*fatorial(1)
3*fatorial(2)
4*fatorial(3)
5*fatorial(4)
6*fatorial(5)
2*(1*1)
Pilha de execução
3*fatorial(2)
4*fatorial(3)
5*fatorial(4)
6*fatorial(5)
3*(2*(1*1))
Pilha de execução
4*fatorial(3)
5*fatorial(4)
6*fatorial(5)
4*(3*(2*(1*1)))
Pilha de execução
5*fatorial(4)
6*fatorial(5)
5*(4*(3*(2*(1*1))))
Pilha de execução
6*fatorial(5)
6*(5*(4*(3*(2*(1*1))))) = 720
/* calcula o fatorial de n. Assuma que n>=0 */
 int fatorial( int n )
 {
 if( n==0 ) 
 return 1;
 else
 return n * fatorial(n-1);
 }
void main(){
 double fat=fatorial(6)=720;
}
 Seja uma função que calcule o n-ésimo número de Fibonacci. 
 Uma solução possível é fazerem-no de forma iterativa. 
 Uma outra alternativa é programarem a função de modo 
recursivo.
Fibonacci iterativo
 Implementar o Fibonacci iterativo.
#include <stdio.h>
int Fibonacci(){
int ni=1,ni1=1, ni2=0;
if(n==1) 
 return(ni);
else{
 for (i=1;i<=n;i++){
 ni=ni1+ni2;
 ni2=ni1;
 ni1=ni;
 }
}
return(ni);
}/* calcula o n-ésimo número de Fibonacci. */
 int fib( int n )
 {
 if( n==1 || n==2 ) 
 return 1;
 else
 return fib(n-1) + fib(n-2);
 }
 Esta solução é muito mais simples de programar do que a versão 
iterativa. 
 Contudo, esta versão é muitíssimo ineficiente. 
 Porque? Cada vez que a função fib é chamada, a dimensão do 
problema reduz-se apenas de uma unidade (de n para n-1), mas 
são feitas duas chamadas recursivas. 
 Isto dá origem a uma explosão combinatorial e o computador 
acaba por ter de calcular a mesma coisa várias vezes. 
Para verificar ineficiência
 Para calcular o quinto número de Fibonacci até nem 
é um grande problema, mas para números maiores 
torna-se muito ineficiente. 
 Experimentem calcular os primeiros 50 números de 
Fibonacci utilizando o método iterativo e o método 
recursivo. 
Quando vale a pena usar recursividade
 Recursividade vale a pena para Algoritmos 
complexos, cuja a implementação iterativa é 
complexa e normalmente requer o uso explícito de 
uma pilha
◦ Dividir para Conquistar (Ex. Quicksort)
◦ Caminhamento em Árvores (pesquisa, backtracking)
Torre de Hanói
O problema consiste em passar todos os discos de um pino 
para outro qualquer, usando um dos pinos como auxiliar, de 
maneira que um disco maior nunca fique em cima de outro 
menor em nenhuma situação. O número de discos pode 
variar sendo que o mais simples contém apenas três.
Solução
void hanoi(int n, int O, int D, int T) { 
 if (n > 0) { 
 hanoi(n - 1, O, T, D); /*executa hanoi para mover n-1 discos da origem 
para o trabalho*/
 mover(O, D); /*mover disco do "pino O" (origem atual) para o "pino D" 
(destino atual)*/
 hanoi(n - 1, T, D, O); //executa hanoi para mover n-1 discos do trabalho 
para destino 
}
Exercícios
1. Desenvolver uma função recursiva para calcular a soma 
dos primeiros n inteiros positivos: soma(n) = n + 
soma(n-1). Qual é o caso Base?
2. Desenvolver uma função recursiva e uma iterativa para 
calcular a função de Ackerman, Ack(m,n), definida, para 
m>= 0 e n>=0 por:
.a) Ack(0,n) = n + 1
.b) Ack(m,0) = Ack(m-1,1)
.c) Ack(m,n) = Ack(m-1,Ack(m,n-1)), m>0, n>0
.d) Qual o valor de Ack(3,2)? (Faça o teste de mesa)
Soluções
int A(int m, int n) {
int param;
 if (m == 0) 
 return n+1; 
 else if (n == 0) 
 return A(m-1,1); 
 else{
 param = A(m, n-1); 
 return A(m-1, param); 
 }
}
	Slide 1
	Fatorial
	Slide 3
	Slide 4
	Slide 5
	Slide 6
	Slide 7
	Slide 8
	Slide 9
	Slide 10
	Slide 11
	Slide 12
	Slide 13
	Slide 14
	Pilha de execução
	Slide 16
	Slide 17
	Pilha de execução
	Slide 19
	Slide 20
	Pilha de execução
	Slide 22
	Slide 23
	Pilha de execução
	Slide 25
	Slide 26
	Pilha de execução
	Slide 28
	Slide 29
	Pilha de execução
	Slide 31
	Slide 32
	Pilha de execução
	Pilha de execução
	Pilha de execução
	Pilha de execução
	Pilha de execução
	Pilha de execução
	Slide 39
	Slide 40
	Fibonacci iterativo
	Slide 42
	Slide 43
	Slide 44
	Slide 45
	Para verificar ineficiência
	Quando vale a pena usar recursividade
	Torre de Hanói
	Slide 49
	Slide 50
	Solução Prática
	Exercícios
	Soluções