Recursividade
Professor Luiz José Hoffmann Filho
[email protected]
1
Tópicos Principais
• Recursão
o Definições recursivas
• Funções Recursivas
o Implementação
o Comportamento
2
Motivação
Recursividade é uma idéia inteligente que desempenha um papel central na
programação funcional e na ciência da computação em geral.
Recursividade é o mecanismo de programação no qual uma definição de
função ou de outro objeto refere-se ao próprio objeto sendo definido.
Assim função recursiva é uma função que é definida em termos de si mesma.
Recursividade é o mecanismo básico para repetições nas linguagens funcionais.
São sinônimos: recursividade, recursão, recorrência.
4/39
Estratégia
Estratégia para a definição recursiva de uma função:
1
• dividir o problema em problemas menores do mesmo tipo
2
resolver
os problemas menores (dividindo-os em problemas
ainda menores, se necessário) combinar as soluções dos
3
problemas
menores para formar a solução final
• Ao dividir o problema sucessivamente em problemas menores
eventualmente os casos simples são alcançados:
o não podem ser mais divididos suas soluções são definidas
explicitamente
5/39
Definições Recursivas
• Em uma definição recursiva um item é definido em termos
de si mesmo, ou seja, o item que está sendo definido
aparece como parte da definição;
• Em todas as funções recursivas existe:
– Caso base (um ou mais) cujo resultado é imediatamente
conhecido.
– Passo recursivo em que se tenta resolver um sub-problema do
problema inicial.
3
Definições Recursivas
• Exemplo: o fatorial de um número
Caso BASE
n! =
1, se n = 0
n× (n  1)!, se n > 0
Passo
Recursivo
4
Definições Recursivas
• Exercício: forneça a definição recursiva para a operação
de potenciação
Caso BASE
xn =
1, se n = 0
x * x(n-1), se n > 0
Passo
Recursivo
5
Funções Recursivas
• Definição:
– Uma função recursiva é aquela que faz uma chamada para si
mesma. Essa chamada pode ser:
• direta: uma função A chama a ela própria
• indireta: função A chama uma função B que, por sua vez, chama A
/* Recursao direta */
void func_rec(int n)
{
...
func_rec(n-1);
...
}
6
Funções Recursivas
• Exemplo: função recursiva para cálculo de fatorial
n! =
1, se n = 0
n * (n  1)!, se n > 0
/* Função recursiva para cálculo do fatorial */
int fat (int n)
{
Caso BASE
if (n==0)
return 1;
else
Passo
return n*fat(n-1);
Recursivo
}
7
Funções Recursivas
• Exemplo: função recursiva para cálculo de potenciação
xn =
1, se n = 0
x * x(n-1), se n > 0
/* Função recursiva para cálculo de potenciacao */
int pot (int x, int n)
{
Caso BASE
if (n==0)
return 1;
else
Passo
return x*pot(x,n-1);
Recursivo
}
8
Funções Recursivas
• Comportamento:
– quando uma função é chamada recursivamente,
cria-se um ambiente local para cada chamada
– as variáveis locais de chamadas recursivas são independentes
entre si, como se estivéssemos chamando funções diferentes
9
Funções Recursivas
#include <stdio.h>
int fat (int n);
int main (void)
{
int n = 3;
int r;
r = fat ( n );
printf("Fatorial de %d = %d \n", n, r);
return 0;
}
/* Função recursiva para cálculo do fatorial */
int fat (int n)
{
int f;
if (n==0)
f=1;
else
f= n*fat(n-1);
return f;
}
f
-
fat(3)n
3
r
-
main n
3
Funções Recursivas
#include <stdio.h>
int fat (int n);
int main (void)
{
int n = 3;
int r;
r = fat ( n );
printf("Fatorial de %d = %d \n", n, r);
return 0;
}
/* Função recursiva para cálculo do fatorial */
int fat (int n)
{
int f;
if (n==0)
f=1;
else
f= n*fat(n-1);
return f;
}
fat(2)n
2
f
-
fat(3)n
3
r
-
main n
3
f
Funções Recursivas
#include <stdio.h>
int fat (int n);
int main (void)
{
int n = 3;
int r;
r = fat ( n );
printf("Fatorial de %d = %d \n", n, r);
return 0;
}
/* Função recursiva para cálculo do fatorial */
int fat (int n)
{
int f;
if (n==0)
f=1;
else
f= n*fat(n-1);
return f;
}
f
1
-
fat(2)n
2
f
-
fat(3)n
3
r
-
main n
3
f
fat(1)n
Funções Recursivas
#include <stdio.h>
int fat (int n);
int main (void)
{
int n = 3;
int r;
r = fat ( n );
printf("Fatorial de %d = %d \n", n, r);
return 0;
}
/* Função recursiva para cálculo do fatorial */
int fat (int n)
{
int f;
if (n==0)
f=1;
else
f= n*fat(n-1);
return f;
}
f
fat(0)n
0
f
1
-
fat(2)n
2
f
-
fat(3)n
3
r
-
main n
3
f
fat(1)n
Funções Recursivas
#include <stdio.h>
int fat (int n);
int main (void)
{
int n = 3;
int r;
r = fat ( n );
printf("Fatorial de %d = %d \n", n, r);
return 0;
}
/* Função recursiva para cálculo do fatorial */
int fat (int n)
{
int f;
if (n==0)
f=1;
else
f= n*fat(n-1);
return f;
}
f
fat(0)n
1
0
f
1
-
fat(2)n
2
f
-
fat(3)n
3
r
-
main n
3
f
fat(1)n
Funções Recursivas
#include <stdio.h>
int fat (int n);
int main (void)
{
int n = 3;
int r;
r = fat ( n );
printf("Fatorial de %d = %d \n", n, r);
return 0;
}
/* Função recursiva para cálculo do fatorial */
int fat (int n)
{
int f;
if (n==0)
f=1;
else
f= n*fat(n-1);
return f;
}
f
1
1
-
fat(2)n
2
f
-
fat(3)n
3
r
-
main n
3
f
fat(1)n
Funções Recursivas
#include <stdio.h>
int fat (int n);
int main (void)
{
int n = 3;
int r;
r = fat ( n );
printf("Fatorial de %d = %d \n", n, r);
return 0;
}
/* Função recursiva para cálculo do fatorial */
int fat (int n)
{
int f;
if (n==0)
f=1;
else
f= n*fat(n-1);
return f;
}
fat(2)n
2
2
f
-
fat(3)n
3
r
-
main n
3
f
Funções Recursivas
#include <stdio.h>
int fat (int n);
int main (void)
{
int n = 3;
int r;
r = fat ( n );
printf("Fatorial de %d = %d \n", n, r);
return 0;
}
/* Função recursiva para cálculo do fatorial */
int fat (int n)
{
int f;
if (n==0)
f=1;
else
f= n*fat(n-1);
return f;
}
f
6
fat(3)n
3
r
-
main n
3
Funções Recursivas
#include <stdio.h>
int fat (int n);
int main (void)
{
int n = 3;
int r;
r = fat ( n );
printf("Fatorial de %d = %d \n", n, r);
return 0;
}
/* Função recursiva para cálculo do fatorial */
int fat (int n)
{
int f;
if (n==0)
f=1;
else
f= n*fat(n-1);
return f;
}
r
6
main n
3
Funções Recursivas
• Exemplo: Série de fibonacci
19
Funções Recursivas
• Exemplo: série de Fibonacci
/* Calculo da serie de Fibonacci */
int fib (int n)
{
if (n==0)
return 0;
else if (n==1)
return 1;
else
return (fib(n-1) + fib(n-2));
}
20
Exercícios
1. Crie a função recursiva para calcular o terminal
de um número n, definido da seguinte maneira:
ì
ï
term(n) í
ï
î
0, se n = 0
n +.... + 3+ 2 +1, se n > 0
1. A multiplicação de números naturais pode ser
definida da segunte forma:
ì
ï
í
ï
î
a * b = a, se b = 1
a * b = a *(b -1) + a, se b > 1
21
Exercícios
3. Determine o que o seguinte procedimento
recursivo computa. Escreva um procedimento não
recursivo (ou iterativo) para para solucionar o
• mesmo problema.
Funcao(n) {
se n = 0 entao
retorne 0
senao
retorne n + Funcao (n-1)
21
Exercícios
4. Implemente um algoritmo para calcular o fatorial
•
21
Exercícios - Desafio
• Elaborar um algoritmo iterativo para o Problema da
Torre de Hanói.
• Elaborar um algoritmo recursivo para o Problema
• da Torre de Hanói.
21