Recursão C++ - Prof. Fernando Marson

Prévia do material em texto

08/08/2013 
1 
Recursão 
Algoritmos e Estruturas de Dados em C++ 
Fernando Marson 
Recursão 
• Uma imagem vale mil palavras... 
08/08/2013 
2 
Recursão 
• Uma imagem vale mil palavras... 
Recursão 
• Propriedade daquilo que se pode repetir um 
número indefinido de vezes; 
• Fractais, L-Systems 
 
• Em programação: é a capacidade de uma função 
invocar a si mesma. 
 
08/08/2013 
3 
Recursão 
Exercício 
• Escrever um programa com uma função que receba 
um número e escreva na tela o número mais 1. 
08/08/2013 
4 
Recursão 
• A recursão precisa de dois termos para ser definida: 
• Definição de um critério de parada; 
• Sem critério de parada ocorre erro de estouro da pilha – stack 
overflow 
• Definição usando a própria definição. 
Recursão x Iteração 
• Funções com o mesmo propósito podem ser 
implementadas tanto da forma iterativa, como da 
forma recursiva. Ambos métodos se baseiam em 
uma estrutura de controle. 
 
• A forma iterativa usa uma estrutura de repetição 
(for, while, do-while). 
• Já a forma recursiva usa uma estrutura de seleção 
 (if - else). 
 
08/08/2013 
5 
Recursão x Iteração 
• Tanto uma como a outra envolvem repetições: a 
iteração usa explicitamente este recurso, enquanto 
que a recursão obtém este comportamento por 
intermédio das chamadas de função repetidas. 
 
• No entanto, é preciso estar certo de que o uso de 
recursão trará benefícios ao seu código e à 
aplicação como um todo. 
Recursão x Iteração 
• Uma abordagem recursiva pode ser escolhida em 
casos onde o problema é refletido de modo mais 
natural, resultando em um programa mais fácil de 
compreender e depurar. 
 
• Outra razão para se optar por uma solução 
recursiva é quando uma solução iterativa não é fácil 
de ser encontrada. Evite usar a recursão em 
situações que exigem um alto desempenho. 
08/08/2013 
6 
Recursão 
• Cálculo de potência: 
• 30 = 1 
• 31 = 3 * (30)  3 
• 32 = 3 * (3 * (30) )  9 
• 33 = 3 * (3 * (3 * (30) ) )  27 
Potência(y) 2y 3y 4y 
0 1 1 1 
1 2 3 4 
2 4 9 16 
3 8 27 64 
Recursão 
• Cálculo de potência: 
• x0 = 1 
• x1 = x * Potência(x, 0) 
• x2 = x * Potência(x, 1)  x * (x * Potência(x, 0)) 
• x3 = x * Potência(x, 2)  x * (x * (x * Potência(x,0))) 
Potência(y) 2y 3y 4y 
0 1 1 1 
1 2 3 4 
2 4 9 16 
3 8 27 64 
08/08/2013 
7 
Recursão 
• Calcular o resultado de xy 
 
 
 
 
 
 
 
• Se a potência for 0 (zero), resultado é 1. 
• Este é o critério de parada. 
Potência(y) 2y 3y 4y 
0 1 1 1 
1 2 3 4 
2 4 9 16 
3 8 27 64 
Recursão 
 Calcular o resultado de xy 
 
 
 
 
 
 
 
 
int potencia(int x, int y) 
{ 
if(y == 0) 
return 1; // Critério de parada 
else 
return x * potencia(x, y – 1); // Chamada recursiva 
} 
Potência(y) 2y 3y 4y 
0 1 1 1 
1 2 3 4 
2 4 9 16 
3 8 27 64 
08/08/2013 
8 
Usos da Recursão 
• Fatorial 
• Árvores binárias 
• Máximo divisor comum (mdc) 
• Pesquisa em uma lista encadeada 
• Caminhamento em uma árvore 
• Algoritmos de Inteligência Artificial 
• Algoritmos de Ordenação 
Usos da Recursão em Jogos 
• Código mais elegante (poucas linhas) – Difícil entender 
a essência...  
• Em dispositivos com poucos recursos (PDAs, 
celulares,...) deve ser evitado. 
• Aloca muita memória (consome muito espaço) 
• Funções recursivas são usadas para efetuar buscas 
(listas e árvores) 
• Fractais são usados na Computação Gráfica 
• Texturas 
• Nuvens 
• Montanhas, relevo, ilhas,... 
08/08/2013 
9 
Exercício 
• Escreva um procedimento recursivo que lê um string de 
comprimento N e o imprime na tela na ordem inversa 
de entrada. Utilize o seguinte protótipo: 
• void inverte(string texto, int n); 
• onde n é a quantidade de caracteres da string. 
• Exemplo: 
• inverte(“abc”, 3) 
• entrada: abc 
• saída: cba 
• Escreva uma função recursiva que computa o fatorial 
de um número inteiro N. 
Exercício 
• Palíndromos são palavras, frases ou qualquer tipo 
de unidade que é igual se for lido da esquerda para 
a direita como da direita para a esquerda. 
• Escrever um programa para verificar se uma palavra 
é um palíndromo.