Aula13 - Funções Recursivas

Prévia do material em texto

ECT1203 Linguagem de Programação 
2014.2 
Prof. Caroline Rocha 
 
Aula 13 – 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 
• Responde as seguintes perguntas: 
▫ Vimos que a função main() chama uma função, 
mas essa função que foi chamada pela main() 
pode chamar outra função? 
▫ Uma função pode chamar a si mesmo? 
 
 
 
Objetivo da aula 
• Definição 
• Elementos 
• Exemplos 
• Exercícios em Sala 
• Torre de Hanoi 
Recursão 
Em uma abordagem recursiva, a solução de um 
problema depende das soluções de instâncias 
menores do mesmo problema. 
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 funcao(int a){ 
 int x = a-1; 
 if(x == 0) 
 return 1; 
 else 
 return funcao(x); 
} 
Fatorial 
𝑛! = 
1 𝑠𝑒 𝑛 = 0
𝑛 ∗ 𝑛 − 1 ! 𝑠𝑒 𝑛 > 0
 
𝑓𝑎𝑡𝑜𝑟𝑖𝑎𝑙(𝑛) = 
1 𝑠𝑒 𝑛 = 0
𝑛 ∗ 𝑓𝑎𝑡𝑜𝑟𝑖𝑎𝑙 𝑛 − 1 𝑠𝑒 𝑛 > 0
 
Função Fatorial Recursiva 
#include <iostream> 
using namespace std; 
 
int fatorial (int n){ 
 if (n == 0) return 1; 
 else return n * fatorial(n-1); 
} 
 
int main(){ 
 int n; 
 cout <<"Entre com um numero positivo: "; 
 cin >> n; 
 cout <<"Fatorial de "<< n <<" = "<< fatorial(n); 
 return 0; 
} 
Função Fatorial Recursiva 
1a chamada: fatorial(6) 
2a chamada: 6 * fatorial(5) 
3a chamada: 6 * 5 * fatorial(4) 
4a chamada: 6 * 5 * 4 * fatorial(3) 
5a chamada: 6 * 5 * 4 * 3 * fatorial(2) 
6a chamada: 6 * 5 * 4 * 3 * 2 * fatorial(1) 
1o retorno: 6 * 5 * 4 * 3 * 2 * 1 
2o retorno: 6 * 5 * 4 * 3 * 2 
3o retorno: 6 * 5 * 4 * 6 
4o retorno: 6 * 5 * 24 
5o retorno: 6 * 120 
6o retorno: 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 n){ 
 int fat = 1; 
 for(int i=2; i<=n; i++) fat = fat * i; 
 return fat; 
} 
Funções Recursivas 
• Em todas as funções recursivas existe: 
▫ Um passo básico (ou mais) cujo resultado é 
imediatamente conhecido. 
 Por exemplo: fatorial(0) = 1 
 
▫ Um passo recursivo em que se tenta resolver um 
sub-problema do problema inicial. 
 Por exemplo: fatorial(n) = n * fatorial(n-1) 
Potência 
𝑥𝑦 = 
1 𝑠𝑒 𝑦 = 0
𝑥 ∗ 𝑥𝑦−1 𝑠𝑒 𝑦 > 0
 
𝑝𝑜𝑡𝑒𝑛𝑐𝑖𝑎(𝑥, 𝑦) = 
1 𝑠𝑒 𝑦 = 0
𝑥 ∗ 𝑝𝑜𝑡𝑒𝑛𝑐𝑖𝑎 𝑥, 𝑦 − 1 𝑠𝑒 𝑦 > 0
 
Função Potência Recursiva 
#include <iostream> 
using namespace std; 
 
int pot(int x, int y){ 
 if (y == 0) return 1; 
 else return x * pot(x, y-1); 
} 
 
int main(){ 
 cout << pot(3, 4) << endl; 
 return 0; 
} 
Função Potência Iterativa 
#include <iostream> 
using namespace std; 
 
int pot(int x, int y){ 
 int res = 1; 
 while(y > 0){ 
 res = res * x; 
 y--; 
 } 
 return fat; 
} 
 
int main(){ 
 cout << pot(3, 4) << endl; 
 return 0; 
} 
 
Série de Fibonacci 
• É uma sequência de números naturais, na qual os dois 
primeiros termos são 1 e 1 e cada termo subsequente 
corresponde à soma dos dois precedentes: 
1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ... 
• Em termos matemáticos, a sequência é definida 
recursivamente pela fórmula abaixo: 









2 para),2fib()1fib(
2 para,1
1 para,1
)fib(
nnn
n
n
n
Série de Fibonacci: função iterativa 
int fib (int n){ 
 int num1 = 0, num2 = 1, num3; 
 for(int i=2; i<=n; i++){ 
 num3 = num2+num1; 
 num1 = num2; 
 num2 = num3; 
 } 
 if(n==0) return num1; 
 else if(n==1) return num2; 
 else return num3; 
} 
Série de Fibonacci: função recursiva 
int fib (int n){ 
 if (n==0) 
 return 0; 
 else if (n==1) 
 return 1; 
 else 
 return fib(n-1) + fib(n-2); 
} 
Par ou ímpar 
• Como seria uma solução recursiva pra determinar se um 
número natural é par ou ímpar? 
Par ou ímpar 
bool par(int n){ 
 if (n == 0) 
 return true; 
 else 
 return impar(n-1); 
} 
 
bool impar(int n){ 
 if (n == 0) 
 return false; 
 else 
 return par(n-1); 
} 
 
 
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. 
• Exemplo: 
 main() chama f() 
 f() chama g() 
 g() chama recursivamente g() 
main() 
f() 
g() 
g() 
Funções recursivas x iterativas 
• 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; 
 nenhum 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.