ECT1203 - Aula08 - Funções Recursivas

Prévia do material em texto

ECT1203 Linguagem de Programação 
 
 
Prof. Luiz Eduardo Cunha Leite 
 
 
Funções Recursivas 
Universidade Federal do Rio Grande do Norte 
Escola de Ciências e Tecnologia 
Hora de silenciar o celular 
• Manter o celular sempre desligado/silencioso quando 
estiver em sala de aula 
• Nunca atender o celular em sala de aula 
Objetivo da Aula 
• Mostrar o que são funções recursivas como funcionam e 
para que servem. 
 
 
Funções Recursivas 
• Definição 
• Elementos 
• Exemplos 
• Exercícios em Sala 
• Torre de Hanoi 
Funções Recursivas 
Uma função recursiva é uma função que se refere a si 
própria. A idéia consiste em utilizar a própria função que 
estamos a definir na sua definição. 
Int funcaoa(int b){ 
int x; 
 x = b-1; 
 if(x==0) 
 return 1; 
 else 
 return funcaoa(x); 
} 
Funções Recursivas 
6 
• Alocação de memória 
▫ Quando uma função é chamada, memória é 
alocada para todos os seus parâmetros e 
variáveis locais. 
▫ Toda função ativa tem memória na pilha(com 
a função atual no topo) 
▫ Quando uma função termina a memória é 
desalocada 
• Ex: main() chama f(), 
 f() chama g() 
 g() chama recursivamente g() 
main() 
f() 
g() 
g() 
Funções Recursivas 
• Em todas as funções recursivas existe: 
▫ Um passo básico (ou mais) cujo resultado é imediatamente 
conhecido. 
 Por exemplo: fatorial(0) = fatorial(1) = 1 
 
▫ Um passo recursivo em que se tenta resolver um sub-
problema do problema inicial. 
 Por exemplo: fatorial(n) = n * fatorial(n-1) 
Função Fatorial Recursiva 
#include <iostream> 
Using namespace std; 
int fatorial (int); 
 
int main(){ 
 int n; 
 cout << “Entre com um numero positivo:"; 
 cin >> n; 
 cout <<“Fatorial de “ << n <<“ = ”<< fatorial(n); 
 return 0; 
} 
 
int fatorial (int num){ 
 if (num == 1 || num == 0) return 1; 
 else return num * fatorial (num-1); 
} 
Função Fatorial Recursiva 
 fatorial(6) 
 6 * fatorial(5) 
 6 * 5 * fatorial(4) 
 6 * 5 * 4 * fatorial(3) 
 6 * 5 * 4 * 3 * fatorial(2) 
 6 * 5 * 4 * 3 * 2 * fatorial(1) 
 6 * 5 * 4 * 3 * 2 * 1 
 6 * 5 * 4 * 3 * 2 
 6 * 5 * 4 * 6 
 6 * 5 * 24 
 6 * 120 
 720 
Função Fatorial Iterativa 
#include <iostream> 
Using namespace std; 
int fatorial (int); 
 
int main(){ 
 int n; 
 cout << “Entre com um numero positivo:"; 
 cin >> n; 
 cout <<“Fatorial de “ << n <<“ = ”<< fatorial(n); 
 return 0; 
} 
 
int fatorial (int num){ 
 int fat = 1; 
 for (int i=2; i <=num; i++) fat = fat * i; 
 return fat; 
} 
Exemplo: série de Fibonnaci 
• A série de Fibonacci é dada por: 
 
 
 
 
 
 
1, 1, 2, 3, 5, 8, 13, 21, ... 









2 para),2fib()1fib(
2 para,1
1 para,1
)fib(
nnn
n
n
n
Exemplo: série de Fibonnaci 
// 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 
• Em geral, a todo procedimento recursivo corresponde 
um outro não recursivo (iterativo). 
• Vantagens da recursão: 
▫ algoritmos mais concisos; 
▫ simplifica a solução de alguns problemas; 
▫ facilidade de implementação e compreensão; 
▫ algoritmos de divisão e conquista (Quicksort, etc) 
• Desvantagens: 
▫ tendem a ser mais lentos e consumir mais memória 
▫ erros de implementação podem levar a estouro de 
memória. 
Jogo da Torre de Hanoi 
Consiste de três posições (A, B e C) e 
N discos de diferentes tamanhos. 
Inicialmente, todos os discos se 
encontram empilhados na posição A 
em ordem decrescente de tamanho, 
de baixo para cima. 
O objetivo é empilhar todos os discos na posição C, atendendo às 
seguintes restrições: 
 apenas um disco pode ser movido de cada vez; 
 qualquer disco pode ser jamais colocado sobre outro de tamanho 
menor 
Faça um programa para resolver o Problema da Torre de Hanoi, dado o 
número de discos N.