Recursividade
Programação II
Recursividade
Recursividade
1. O objeto é definido a partir dele mesmo
2. Uma computação pode ser definida a
partir dela mesma
3. Uma função pode ser definida a partir dela
mesma.
4. Recursividade pode repetir uma mesma
computação sobre um conjunto de dados
menor
O objeto é definido a partir dele
mesmo
• Exemplo - Números
Naturais:
0 está em N;
Se n está em N, então n +
1 está em N.
Uma computação pode ser
definida a partir dela mesma
• Seqüência de Fibonacci:
F(1) = F(0) = 1
F(n) = F(n − 1) + F(n − 2).
Uma função pode ser definida a
partir dela mesma
função fatorial(n){
se (n <= 1)
retorne 1;
senão
retorne n * fatorial(n-1);
}
Recursividade pode repetir uma mesma
computação sobre um conjunto de dados
menor
• A função chama a si mesma recursivamente em
uma versão menor da entrada (n - 1):
funcao procura(x, v, n) {
se (v[n] == x)
retorne n
senao
retorne procura (x,v,n-1)
}
Recursividade
•Toda função recursiva pode ser construída de maneira
não recursiva;
•Não melhora o desempenha de programas
–Uma ativação de uma função tem custo computacional mais
alto que uma interação de um laço equivalente (por exemplo).
•Ocupa mais espaço que soluções não recursivas
–Quando uma função chama a si mesmo, cada ativação recebe
um conjunto novo de todos os dados locais, incluindo os
parâmetros, independente do conjunto anterior.
•Geralmente as soluções recursivas são algoritmos
menores, mais elegantes e mais fáceis de entender;
Mais exemplos
• Número de Fibonacci de ordem n
int fibRec(int n)
{if (n == 0) return 0;
if (n == 1) return 1;
return fibRec(n - 1) + fibRec(n - 2);
}
Imprimir um número como uma cadeia de
caracteres
imprdecRecursivo(n)
int n;
{
int i;
printf("%d\n",n);
if (n<0) {
putchar('-');
n = -n;
}
if ((i=n/10)!=0) {
imprdecRecursivo(i);
}
putchar(n%10 + '0');
}
Exercícios
•
•
•
Construa uma versão não recursiva para as
funções fibRec e imprdecRecursivo.
Adapte a idéia da função imprdecRecursivo para
escrever uma versão recursiva da função itoa(n),
que converte um inteiro para uma cadeia de
caracteres.
Escreva uma versão recursiva da função
inverte(s), que inverte a cadeia de caracteres s.