Aula 10 - Recursividade

Prévia do material em texto

DCC119 - Algoritmos
2
Definição de recursão
Uso de recursão
Primeiro Exemplo: Fatorial
Exercícios
3
Uma função é dita recursiva quando chama a 
si própria, direta ou indiretamente.
Propósito: expressar sua funcionalidade ou 
objetivo de maneira mais clara e concisa.
Linguagens que permitem uma função 
chamar a si própria são ditas recursivas
Linguagens que não permitem são ditas iterativas 
ou não recursivas
4
Suponha que alguém no ICE lhe pergunte: 
Como chego à Rua Oswaldo Cruz?
5
Como chego à Rua Oswaldo Cruz?
Você poderia responder com conjunto completo de direções 
e referências... mas, se as direções são muito complexas, 
ou se você não está muito certo de como chegar lá, poderia 
responder:
Vá até a esquina das ruas Olegário Maciel e Halfeld e 
então pergunte lá: Como chego à Rua Oswaldo Cruz?
6
Como chego à Rua Oswaldo Cruz?
Você poderia responder com conjunto completo de direções 
e referências... mas, se as direções são muito complexas, 
ou se você não está muito certo de como chegar lá, poderia 
responder:
Vá até a esquina das ruas Olegário Maciel e Halfeld e 
então pergunte lá: Como chego à Rua Oswaldo Cruz?
Este é um exemplo de recursão!!!
7
Seu colega queria direções para um destino
Para resolver o problema, você deu um conjunto de 
instruções indicando como seu colega poderia alcançar 
seu objetivo
Após chegar ao destino indicado por você, seu colega 
se depara com nova versão do problema original
Novo problema, idêntico em forma ao original, envolve uma 
nova localização de partida mais próxima ao destino final!
8
Cálculo do fatorial de um número n
Aprendemos que n! = n * n-1 * n-2 * * 1 
9
inteiro Fatorial (inteiro n)
{
inteiro Fat, i;
Fat 1;
para (i=2; i<=n;I=i+1) faça
{ 
Fat Fat * i;
}
retorne Fat;
}
Implementação iterativa muito simples:
10
inteiro Fatorial (inteiro n)
{
inteiro Fat, i;
Fat 1;
para (i=2; i<=n;I=i+1) faça
{ 
Fat Fat * i;
}
retorne Fat;
}
Implementação iterativa muito simples:
int Fatorial (int n)
{ 
int Fat, i;
Fat = 1;
for (i = 2; i <= n; i++)
Fat = Fat * i;
return (Fat);
}
11
Tanto a definição matemática quanto o código 
anterior são simples, porém mais elegante definir o 
fatorial como:
1, se n = 1
n! 
n * (n-1)!, se n > 1
Fatorial de n definido a partir dos fatoriais dos 
naturais menores que ele
12
Significa que para cálculo do fatorial de um 
determinado número há necessidade de que 
se recorra aos fatoriais dos números 
anteriores.
Por exemplo: Quanto é o fatorial de 4?
13
fatorial de 4!
4! =
1, se n = 1
n! 
n * (n-1)!, se n > 1
14
fatorial de 4!
4! = 4 * 3!
1, se n = 1
n! 
n * (n-1)!, se n > 1
15
fatorial de 4!
4! = 4 * 3!
3! =
1, se n = 1
n! 
n * (n-1)!, se n > 1
16
fatorial de 4!
4! = 4 * 3!
3! = 3 * 2!
1, se n = 1
n! 
n * (n-1)!, se n > 1
17
fatorial de 4!
4! = 4 * 3!
3! = 3 * 2!
2! =
1, se n = 1
n! 
n * (n-1)!, se n > 1
18
fatorial de 4!
4! = 4 * 3!
3! = 3 * 2!
2! = 2 * 1!
1, se n = 1
n! 
n * (n-1)!, se n > 1
19
fatorial de 4!
4! = 4 * 3!
3! = 3 * 2!
2! = 2 * 1!
1! =
1, se n = 1
n! 
n * (n-1)!, se n > 1
20
fatorial de 4!
4! = 4 * 3!
3! = 3 * 2!
2! = 2 * 1!
1! = 1
1, se n = 1
n! 
n * (n-1)!, se n > 1
21
fatorial de 4!
4! = 4 * 3!
3! = 3 * 2!
2! = 2 * 1! = 2 * 1 = 2
1! = 1
1, se n = 1
n! 
n * (n-1)!, se n > 1
22
fatorial de 4!
4! = 4 * 3!
3! = 3 * 2! = 3 * 2 = 6
2! = 2 * 1! = 2 * 1 = 2
1! = 1
1, se n = 1
n! 
n * (n-1)!, se n > 1
23
fatorial de 4!
4! = 4 * 3! = 4 * 6 = 24
3! = 3 * 2! = 3 * 2 = 6
2! = 2 * 1! = 2 * 1 = 2
1! = 1
1, se n = 1
n! 
n * (n-1)!, se n > 1
24
fatorial de 4!
4! = 4 * 3! = 4 * 6 = 24
3! = 3 * 2! = 3 * 2 = 6
2! = 2 * 1! = 2 * 1 = 2
1! = 1
Portanto, 4! = 24
1, se n = 1
n! 
n * (n-1)!, se n > 1
25
Condição que define parada da recursão: 
chamada base da recursão ou de caso 
base
Todo programa recursivo deve possuir 
uma condição de parada !
Condição que define recursão chamada 
passo recursivo.
26
1, se n = 1 Base da recursão
n!
n * (n-1)!, se n > 1 Passo recursivo
27
inteiro FatorialRecursivo (inteiro n)
{ 
se (n = 1) Base da recursão
{
retorne 1;
} 
senão
{ 
retorne (n * FatorialRecursivo (n 1));
}
} 
28
inteiro FatorialRecursivo (inteiro n)
{ 
se (n = 1)
{
retorne 1;
} 
senão
{ 
retorne (n * FatorialRecursivo (n 1));
}
}
Passo recursivo
29
int FatorialRecursivo (int n)
{ 
if (n == 1) Base da recursão
return (1);
else
return (n * FatorialRecursivo (n - 1));
}
Passo recursivo
30
Mas o que acontece durante a execução de uma 
função recursiva?
Suponha que função chamada em algum ponto do 
código: 
N FatorialRecursivo (4);
31
4
inteiro FatorialRecursivo (inteiro n) 
{ 
se (n = 1)
{ 
retorne 1;
} 
senão
{
retorne (n * FatorialRecursivo (n - 1));
}
}
N FatorialRecursivo (4);
4
32
inteiro FatorialRecursivo (4) 
{ 
se (4 = 1)
{ 
retorne 1;
} 
senão
{
retorne (4 * FatorialRecursivo (4 - 1));
}
}
FatorialRecursivo (4)
4
33
inteiro FatorialRecursivo (3) 
{ 
se (3 = 1)
{ 
retorne 1;
} 
senão
{
retorne (3 * FatorialRecursivo (3 - 1));
}
}
FatorialRecursivo (3)
4 3
34
inteiro FatorialRecursivo (2) 
{ 
se (2 = 1)
{ 
retorne 1;
} 
senão
{
retorne (2 * FatorialRecursivo (2 - 1));
}
}
FatorialRecursivo (2)
4 3 2
35
inteiro FatorialRecursivo (1) 
{ 
se (1 = 1)
{ 
retorne 1;
} 
senão
{
retorne (n * FatorialRecursivo (n - 1));
}
}
FatorialRecursivo (1)
4 3 2 1
36
inteiro FatorialRecursivo (2) 
{ 
se (2 = 1)
{ 
retorne 1;
} 
senão
{ // retorne (2 * FatorialRecursivo (2 - 1)); 
retorne (2 * 1));
}
}
FatorialRecursivo (2)
4 3 2 1
1
37
inteiro FatorialRecursivo (3) 
{ 
se (3 = 1)
{ 
retorne 1;
} 
senão
{ // retorne (3 * FatorialRecursivo (3 - 1)); 
retorne (3 * 2));
}
}
FatorialRecursivo (3)
4 3 2 1
12
38
inteiro FatorialRecursivo (4) 
{ 
se (4 = 1)
{ 
retorne 1;
} 
senão
{ // retorne (4 * FatorialRecursivo (4 - 1)); 
retorne (4 * 6));
}
}
FatorialRecursivo (4)
4 3 2 1
126
39
inteiro FatorialRecursivo (4) 
{ 
se (4 = 1)
{ 
retorne 1;
} 
senão
{ // retorne (4 * FatorialRecursivo (4 - 1)); 
retorne (4 * 6));
}
}
FatorialRecursivo (4)
4 3 2 1
126
N 24;
24
40
Escreva um código recursivo para calcular o 
máximo divisor comum, MDC, de dois números 
inteiros positivos N e M da seguinte maneira:
41
int MDC (int n, int m)
{ 
}
42
int MDC (int n, int m)
{ 
if ( (n>=m) && ((n%m)==0) )
return(m);
}
43
int MDC (int n, int m)
{ 
if ( (n>=m) && ((n%m)==0) )
return(m);
else
{ 
}
}
44
int MDC (int n, int m)
{ 
if ( (n>=m) && ((n%m)==0) )
return(m);
else
{ 
if (n<m) 
return (MDC(m,n));
}
}
45
int MDC (int n, int m)
{ 
if ( (n>=m) && ((n%m)==0) )
return(m);
else
{ 
if (n<m) 
return (MDC(m,n));
else
return (MDC(m,n%m));
}
}
46
1) Faça um procedimento recursivo que receba dois 
valores inteiros a e b e imprima o intervalo 
fechado entre eles. Se a for maior que b mostrar 
mensagem de erro.
2) Faça o teste de mesa do procedimento abaixo e 
informe qual será a saída do mesmo se a chamada 
for faz( 1, 4 ).
faz (inteiro a, inteiro b)
{
se (a <= b)
{
faz ( a + 1, b);
imprime( a );
}
}
47
3) Dada a função X:
int X (int n, int m)
{
if ((n==m) || (m==0) || (n==0))
return 1;
return X(n-1,m)+X(n-1,m+1);
}
a) Qual o valor de X(5,3) ?
b) Quantas chamadas serão feitas na avaliação acima?
48
4) Escreva uma função recursiva para calcular o somatório 
dos N primeiros números inteiros positivos.
5) Escreva uma função recursiva que recebe como 
parâmetros um número real X e um inteiro N e retorna o 
valor de XN. Obs.: N pode ser negativo
6) Escreva uma função recursiva para determinar o número 
de dígitos de um número N inteiro.
DCC120
Laboratório de Programação
50
1) Escreva uma função recursiva para calcular o N-ésimo
número dasequência de Fibonacci. A sequência é
dada por: 
2) Seja S um vetor de inteiros. Descreva funções recursivas para 
calcular:
a) o elemento máximo de S;
b) a soma dos elementos de S;
c) média aritmética dos elementos de S.
3) Escreva uma função recursiva que imprima na tela os números 
ímpares de 1 à um número fornecido pelo usuário.
51
4) Escreva uma função recursiva, ImprimeSerie (i, j, k), 
que imprime na tela a série de valores do intervalo [i,j], 
com incremento k (i, j e k são inteiros). 
5) Escreva uma função recursiva int SomaSerie (i, j, k), que 
devolva a soma da série de valores do intervalo [i,j], com 
incremento k (i, j e k são inteiros).
6) Faça uma função recursiva que calcule o valor da série 
S descrita a seguir para um valor n > 0 a ser fornecido 
como parâmetro para a mesma:
S = 1 + 1/2! + 1/3! + ... 1/n!
OBS: A função fatorial também deve ser recursiva.