Funções & Recursividade

Prévia do material em texto

ALGORITMOS E 
PROGRAMAÇÃO DE 
COMPUTADORES 
Disciplina: 113476 
 
Profa. Carla Denise Castanho 
 
Universidade de Brasília – UnB 
Instituto de Ciências Exatas – IE 
Departamento de Ciência da Computação – CIC 
13. RECURSIVIDADE 
Algoritmos e Programação de Computadores - carlacastanho@cic.unb.br 
Recursividade 
u  Depois de ter trabalhado com funções, você já 
deve ter se perguntado: uma função pode chamar 
a si mesma? 
u  Sim! Essa técnica chama-se recursividade, e 
muitas vezes facilita a resolução de certos tipos 
de problemas. 
Algoritmos e Programação de Computadores - carlacastanho@cic.unb.br 
Recursividade 
u  Um problema recursivo é aquele em que uma instância do 
problema pode ser definida em termos de instâncias 
menores ou seja, sub-instâncias do mesmo problema. 
Chamamos esse tipo de definição de recorrência. 
u  Por exemplo, o fatorial de N pode ser definido tanto de 
maneira iterativa: 
Fat(N) = N * (N-1) * ... * 1. 
u  Como de maneira recursiva, em termos do fatorial de 
N-1: 
Fat(N) = N * Fat(N-1), 
dado Fat(0) = 1. 
Algoritmos e Programação de Computadores - carlacastanho@cic.unb.br 
Recursividade 
u  Mas a pergunta é: quando parar? 
u  Se a função chama a si mesma sempre, ela entra 
em loop: faz infinitas chamadas recursivas e 
nunca para de computar! 
u  Por isso é necessário definir um caso base! No 
nosso exemplo, Fat(0) = 1. 
u  Vamos ver como funciona... 
 
Algoritmos e Programação de Computadores - carlacastanho@cic.unb.br 
Recursividade 
Algoritmos e Programação de Computadores - carlacastanho@cic.unb.br 
fat(4) 
Recursividade 
Algoritmos e Programação de Computadores - carlacastanho@cic.unb.br 
fat(4) 
chama fat(4-1) 
Recursividade 
Algoritmos e Programação de Computadores - carlacastanho@cic.unb.br 
fat(4) 
chama fat(4-1) 
chama fat(3-1) 
chama fat(2-1) 
Recursividade 
Algoritmos e Programação de Computadores - carlacastanho@cic.unb.br 
fat(4) 
chama fat(4-1) 
chama fat(3-1) 
chama fat(2-1) 
chama fat(1-1) 
Recursividade 
Algoritmos e Programação de Computadores - carlacastanho@cic.unb.br 
fat(4) 
chama fat(4-1) 
chama fat(3-1) 
chama fat(2-1) 
chama fat(1-1) 
retorna 1 
Recursividade 
Algoritmos e Programação de Computadores - carlacastanho@cic.unb.br 
fat(4) 
chama fat(4-1) 
chama fat(3-1) 
chama fat(2-1) 
chama fat(1-1) 
retorna 1 
retorna 1 * fat(0) 
Recursividade 
Algoritmos e Programação de Computadores - carlacastanho@cic.unb.br 
fat(4) 
chama fat(4-1) 
chama fat(3-1) 
chama fat(2-1) 
chama fat(1-1) 
retorna 1 
retorna 1 * fat(0) 
retorna 2 * fat(1) 
retorna 3 * fat(2) 
Recursividade 
Algoritmos e Programação de Computadores - carlacastanho@cic.unb.br 
fat(4) 
chama fat(4-1) 
chama fat(3-1) 
chama fat(2-1) 
chama fat(1-1) 
retorna 1 
retorna 1 * fat(0) 
retorna 2 * fat(1) 
retorna 3 * fat(2) 
retorna 4 * fat(3) 
Recursividade 
Algoritmos e Programação de Computadores - carlacastanho@cic.unb.br 
Exemplo – Fatorial Recursivo 
Algoritmo Fatorial 
Função Fat (n : inteiro) 
Início 
 Se (n = 0) 
 retorne 1 
 Senão 
 retorne n * Fat(n-1) 
Fim 
Variáveis 
 n : inteiro 
Início 
 Escreva (“Informe um inteiro não negativo:”) 
 Leia (n) 
 Escreva (“O fatorial de ”, n, “ é: ”, Fat(n)) 
Fim 
Recursividade 
Programa C do Exemplo Anterior 
#include <stdio.h> 
 
int fatorial (int n) { 
 if (n == 0) 
 return 1; 
 else 
 return n * fatorial(n – 1); 
} 
 
int main () { 
 int n; 
 
 printf("Informe um inteiro positivo: "); 
 scanf("%d", &n); 
 printf("O fatorial de %d eh %d.\n", n, fatorial(n)); 
 
 getchar(); 
 return 0; 
} 
Algoritmos e Programação de Computadores - carlacastanho@cic.unb.br 
Recursividade 
Algoritmos e Programação de Computadores - carlacastanho@cic.unb.br 
1a chamada 
n=3 
Retorne (3*Fatorial(2)) 2a chamada 
n=2 
Retorne (2*Fatorial(1)) 
3a chamada 
n=1 
Retorne (1*Fatorial(0)) 
4a chamada 
n=0 
Retorne (1) 1 
1 
2 
6 
Resultado da função 
Para cada nova 
chamada na função, 
mais memória é 
utilizada para guardar 
as informações 
(variáveis) daquela 
chamada. 
u  Visualmente podemos analisar o fatorial de 3, 
fat(3), da seguinte forma: 
Pilha de Execução 
u  Para entender como funciona a recursividade, 
precisamos entender o conceito de pilha de 
execução. 
u  Toda vez que nós chamamos uma função, o 
computador reserva memória para as variáveis e 
parâmetros daquela chamada específica. 
u  A função que está sendo executada no momento está 
no topo da pilha, se ela chamar alguma outra função, 
esta será empilhada e passa a ficar no topo. 
u  Vamos ver um esquema... 
Algoritmos e Programação de Computadores - carlacastanho@cic.unb.br 
Pilha de Execução 
u  No início do programa, a pilha de execução parece mais 
ou menos assim: 
Algoritmos e Programação de Computadores - carlacastanho@cic.unb.br 
main topo da pilha 
Pilha de Execução 
u  Por exemplo, se main chamar a função Func, a pilha ficará 
assim: 
Algoritmos e Programação de Computadores - carlacastanho@cic.unb.br 
main 
topo da pilha Func 
Pilha de Execução 
u  E se, dentro de Func, for chamada printf, então teremos: 
Algoritmos e Programação de Computadores - carlacastanho@cic.unb.br 
main 
Func 
topo da pilha printf 
Pilha de Execução 
u  Quando uma chamada de função termina, ela é desempilhada, e a 
função anterior continua. Por exemplo, depois printf retorna, 
voltamos a: 
Algoritmos e Programação de Computadores - carlacastanho@cic.unb.br 
main 
topo da pilha Func 
Pilha de Execução 
u  Logo, uma chamada recursiva nada mais é que uma simples chamada 
de função. Tudo que acontece é que várias instâncias da mesma 
função ficam empilhadas mais de uma vez... 
Algoritmos e Programação de Computadores - carlacastanho@cic.unb.br 
main 
Func 
Func 
... 
topo da pilha Func 
Pilha de Execução 
u  Cada vez que Func é empilhada, são reservados novos espaços para 
todas as variáveis locais de Func, inclusive seus parâmetros, que são 
e então usados pela nova instância: 
Algoritmos e Programação de Computadores - carlacastanho@cic.unb.br 
main 
topo da pilha 
Func 
param1 var1 
param2 var2 
 ... var3 
 ... 
Func 
param1 var1 
param2 var2 
 ... var3 
 ... 
Pilha de Execução 
u  Portanto, o que acontece em uma instância de 
uma função recursiva não influencia o que 
acontece em outras instâncias porque as 
variáveis, de fato, estão em locais diferentes da 
memória. 
u  Mas note que chamar funções ocupa memória! 
u  Por isso, se um algoritmo recursivo faz muitas 
chamadas, ele pode causar um estouro de pilha, 
ou seja, ficar sem memória suficiente para 
continuar! 
Algoritmos e Programação de Computadores - carlacastanho@cic.unb.br 
Cuidados com a Recursividade! 
u  Se um problema é inerentemente recursivo, o 
algoritmo recursivo normalmente é mais fácil de 
escrever e mais simples de entender. 
u  No entanto, é preciso analisar se vale a pena a 
solução recursiva: ela pode ocupar muita 
memória e é sempre mais lenta que a solução 
iterativa, pois gasta-se tempo empilhando e 
desempilhando as várias chamadas. 
Algoritmos e Programação de Computadores - carlacastanho@cic.unb.br 
Conclusões 
u  Uma solução recursiva potencialmente ocupa mais 
memória e pode ser mais lenta que a solução 
iterativa para um mesmo problema. 
u  Em cada instância, é sempre alocada memória 
para todos os parâmetros e variáveis locais, 
independentemente dos que já existiam antes. 
u  A cada nova chamada,o sistema deve guardar a 
posição de memória de onde a chamada foi feita, 
para que posteriormente possa voltar ao lugar 
certo. 
Algoritmos e Programação de Computadores - carlacastanho@cic.unb.br 
Conclusões 
u  Um programa recursivo é normalmente mais elegante 
e menor que a sua versão iterativa, além de exibir 
com maior clareza o processo utilizado, desde que o 
problema ou dados sejam naturalmente definidos 
através da recorrência. 
u  É fácil criar funções que chamem a elas mesmas. 
u  É difícil reconhecer situações apropriadas para a 
utilização de recursividade. 
u  Há certos problemas cuja natureza permite uma 
solução recursiva bem mais simples e intuitiva do que 
a solução iterativa. 
Algoritmos e Programação de Computadores - carlacastanho@cic.unb.br