Funções Recursivas
by Aquiles Burlamaqui
Construção de Algoritmos
 Funções Recursivas





Definição
Elementos
Exemplos
Exercícios em Sala
T8: Torre de Hanoi
Funções Recursivas
 Uma função recursiva é uma função
que se refere a si própria. A ideia
consiste em utilizar a própria função
que estamos a definir na sua definição.
Funções Recursivas
 Em todas as funções recursivas existe:
 Um passo básico (ou mais) cujo resultado
é imediatamente conhecido.
 Um passo recursivo em que se tenta
resolver um sub-problema do problema
inicial.
Funções Recursivas
#include <stdio.h>
int fatorial( int n )
{
int i,p;
p = 1;
for( i=2; i<=n; i++ )
p = p * i;
return p;
}
Funções Recursivas
#include <stdio.h>
int main(){
unsigned int numero;
printf("\nEntre com um numero positivo.");
scanf("%u", &numero);
printf("O fatorial de %u vale %u.", numero, factorial(numero));
getch();
}
unsigned int fatorial (unsigned int num){
unsigned int fato;
if (num == 1)
return (1);
else
fato = num * fat (num-1);
return fato;
}
Funções Recursivas
factorial(6)
6 * factorial(5)
6 * 5 * factorial(4)
6 * 5 * 4 * factorial(3)
6 * 5 * 4 * 3 * factorial(2)
6 * 5 * 4 * 3 * 2 * factorial(1)
6 * 5 * 4 * 3 * 2 * 1 * factorial(0)
6*5*4*3*2*1*1
6*5*4*3*2*1
6*5*4*3*2
6*5*4*6
6 * 5 * 24
6 * 120
720
Funções Recursivas
 Fibonacci



2
fib(1) = 1
fib(2) = 1
fib(n) = fib(n-1) + fib(n-2),
para n >
Funções Recursivas
// 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);
}
Funções Recursivas
 Recursão versus Iteração
 Quando usar um ou outro?
 Recursão
 Percurso de uma árvore;
 Função de Ackermann
 Algoritmos de divisão e conquista(Quicksort, etc)
Funções Recursivas

Linguagens de programação
modernas o espaço disponível para o
fluxo de controle é geralmente bem
menor que o espaço disponível na
heap;
Programa na Memória
Funções Recursivas
 T8:
Construir um programa
que implemente o jogo
Torre de Hanoi( para n
discos), permitindo que o
usuário tente resolvé-lo
como também permita
que ele peça a resposta
ao computador, e o
computador exiba tal
resposta visualmente.