Upload
ngongoc
View
225
Download
0
Embed Size (px)
Citation preview
Recursividade
Estrutura de Dados
Prof. Kleber Rezende
Considerações Iniciais
Em aulas anteriores fizemos uma função
que permite calcular o fatorial de um
número.
Naquela função, a cada nova iteração o
resultado da iteração anterior era
multiplicado pelo valor do contador atual,
da seguinte maneira:
Considerações Iniciais
int fatorial(int n)
{
int result, cont;
result = 1;
for (cont = 1; cont <= n; cont++)
result = result * cont;
return result;
}
Considerações Iniciais
Se observarmos atentamente veremos
que o fatorial de cada iteração é sempre
calculado pelo contador daquela iteração
multiplicado pelo resultado do fatorial do
número anterior a ele, ou seja, o fatorial
de 5 está sendo calculado pela
multiplicação do número 5 pelo resultado
do fatorial de 4 (o valor 24).
Considerações Iniciais
O fatorial do número 4 está sendo
calculado pela multiplicação do número
4 pelo resultado do fatorial de 3 (o valor
6), e assim sucessivamente.
Considerações Iniciais
Tentando abstrair esse raciocínio para
uma formulação mais apropriada
poderíamos inferir que o fatorial de um
número n é sempre calculado pela
multiplicação desse número pelo fatorial
do número anterior a ele (n-1), ou se
preferirmos:
fatorial(n) = n * fatorial(n-1)
Considerações Iniciais
Note que estamos definindo a função
fatorial utilizando a própria função
fatorial.
Sempre que, ao resolver um dado
problema, o desmembramos em
instâncias menores do mesmo problema
estamos trabalhando com a
recursividade.
O cálculo do FATORIAL utilizando
recursividade
Retomando o problema do fatorial,
percebemos ainda que existe uma exceção
para o cálculo do mesmo quando utilizamos a
formulação anterior.
Essa exceção se refere ao momento em que
estamos calculando o fatorial do número 0,
pois para esse valor o resultado do fatorial é
diretamente o valor 1, tornando-se
desnecessário qualquer tipo de cálculo.
O cálculo do FATORIAL utilizando
recursividade
Sendo assim, podemos refinar a
formulação anterior da seguinte maneira:
se n = 0, fatorial(n) = 1
se n > 0, fatorial(n) = n * fatorial(n-1)
O cálculo do FATORIAL utilizando
recursividade
A função fatorial utilizando a
recursividade ficaria:
int fatorial(int n)
{
if (n == 0)
return 1;
else
return n * fatorial (n-1);
}
O cálculo do FATORIAL utilizando
recursividade
Na solução anterior a dimensão do
problema vai sendo sucessivamente
reduzida até o momento em que atinge-
se um caso base (n = 0) em que a
recursividade termina.
Para melhor se perceber o modo como a
função funciona, é útil vermos o modo
como a computação é executada
internamente no computador.
O cálculo do FATORIAL utilizando
recursividade
Para calcular o fatorial de 5, o
computador tem de calcular primeiro o
fatorial de 4 e só depois é que faz a
multiplicação de 5 pelo resultado (24).
Por sua vez, para calcular o fatorial de 4,
vai ter de calcular o fatorial de 3.
E assim por diante, até esbarrar no caso
base, onde n é igual a 0. Veja a
execução a seguir:
O cálculo do FATORIAL utilizando
recursividade
fatorial(5)
5 * fatorial(4)
5 * 4 * fatorial(3)
5 * 4 * 3 * fatorial(2)
5 * 4 * 3 * 2 * fatorial(1)
5 * 4 * 3 * 2 * 1 * fatorial(0)
5 * 4 * 3 * 2 * 1 * 1
5 * 4 * 3 * 2 * 1
5 * 4 * 3 * 2
5 * 4 * 6
5 * 24
120
Outro exemplo:
Números de Fibonacci
Desenvolver um algoritmo recursivo que
calcule um número da série de Fibonacci
localizado na posição n.
Cada número da série de Fibonacci é
calculado a partir da soma dos dois
números anteriores, da seguinte
maneira:
Fibonacci = 1, 1, 2, 3, 5, 8, 13, 21, 34, ...
Outro exemplo:
Números de Fibonacci
Um algoritmo iterativo que resolve esse problema é
apresentado a seguir:
int fib (int n)
{
int cont, anterior, atual, sucessor;
if ((n == 1) || (n == 2))
return 1;
else {
cont = 3;
anterior = 1;
//continua
Outro exemplo:
Números de Fibonacci
else {
//continuação
atual = 1;
sucessor = anterior + atual;
while (cont < n) {
anterior = atual;
atual = sucessor;
sucessor = anterior + atual;
cont = cont + 1;
}
return sucessor;
Outro exemplo:
Números de Fibonacci
Por exemplo, supondo que o usuário tenha fornecido
como entrada o número 6, o sexto número da série de
Fibonacci deve ser o 8 (1, 1, 2, 3, 5, 8).
Se pensarmos em termos recursivos, vemos que o
valor de Fibonacci para os 2 primeiros elementos é
igual a 1, e que cada sucessor tem o valor da soma
dos resultados de fibonacci de seus antecessores.
Sendo assim podemos definir o valor de Fibonacci
para uma determinada posição a partir da seguinte função recursiva:
Outro exemplo:
Números de Fibonacci
int fib (int n)
{
if ((n == 1) || (n == 2))
return 1;
else
return fib (n-1) + fib (n-2)
}
Exercícios
1. O que irá ser escrito na tela caso seja
executado o seguinte procedimento?
void explode (int n)
{
if (n == 0)
printf(“BUMMM!!!”);
else {
printf(“%d”, n);
explode(n-1);
}
}
Exercícios
2. Faça uma função recursiva para
calcular o Máximo Divisor Comum
(MDC) entre dois números.
Uma forma de se calcular o MDC entre
dois número x e y é: MDC ( X, Y) =>
(a) Y se Y <= X e X mod Y = 0
(b) MDC (Y, X) se X < Y
(c) MDC (Y, X mod Y) se caso contrário
Exercícios
3. Desenvolva uma função recursiva que
calcule a potência de um número inteiro
elevado a um expoente também inteiro.
Exercícios
4. Escreva um procedimento chamado de
menu que oferece ao usuário 2 opções
de escolha da seguinte forma: 1 – Digite 1 para que seja escrito na tela a palavra “um”
2 – Digite 2 para que seja escrito na tela a palavra “dois”
Caso o usuário digitar qualquer valor que não seja 1
ou 2, ou seja, que não faça parte das opções
disponibilizadas, o procedimento menu deve avisar
para o usuário que a opção digitada não é válida e
executar-se novamente.