10.Recursividade

Prévia do material em texto

Recursividade
DCC119 - Algoritmos
2
Nesta Aula
� Definição de recursão
� Uso de recursão
� Primeiro Exemplo: Fatorial
� Exercícios
3
Definição
� 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
Entendendo recursividade
Suponha que alguém no ICE lhe pergunte: 
“Como chego à Rua Oswaldo Cruz?”
5
Entendendo recursividade
“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
Entendendo recursividade
“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
Revendo o problema....
� 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
Exemplo de Algoritmo 
recursivo
Cálculo do fatorial de um número n
Aprendemos que n! = n * n-1 * n-2 * D * 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;
}
Exemplo de Algoritmo 
recursivo
Implementação iterativa muito simples:
10
Exemplo de Algoritmo 
recursivo
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);
}
inteiro Fatorial (inteiro n)
{
inteiro Fat, i;
Fat � 1;
para (i�2; i<=n;i � i+1) faça
{ 
Fat � Fat * i;
}
retorne 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
Exemplo de Algoritmo 
recursivo
12
Exemplo de Algoritmo 
recursivo
� 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! =
Exemplo de Algoritmo 
recursivo
1, se n = 1
n! 
n * (n-1)!, se n > 1
14
fatorial de 4!
4! = 4 * 3!
Exemplo de Algoritmo 
recursivo
1, se n = 1
n! 
n * (n-1)!, se n > 1
15
fatorial de 4!
4! = 4 * 3!
3! =
Exemplo de Algoritmo 
recursivo
1, se n = 1
n! 
n * (n-1)!, se n > 1
16
fatorial de 4!
4! = 4 * 3!
3! = 3 * 2!
Exemplo de Algoritmo 
recursivo
1, se n = 1
n! 
n * (n-1)!, se n > 1
17
fatorial de 4!
4! = 4 * 3!
3! = 3 * 2!
2! =
Exemplo de Algoritmo 
recursivo
1, se n = 1
n! 
n * (n-1)!, se n > 1
18
fatorial de 4!
4! = 4 * 3!
3! = 3 * 2!
2! = 2 * 1!
Exemplo de Algoritmo 
recursivo
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! =
Exemplo de Algoritmo 
recursivo
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
Exemplo de Algoritmo 
recursivo
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
Exemplo de Algoritmo 
recursivo
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
Exemplo de Algoritmo 
recursivo
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
Exemplo de Algoritmo 
recursivo
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
Exemplo de Algoritmo 
recursivo
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.
Exemplo de Algoritmo 
recursivo
26
1, se n = 1 Base da recursão
n!
n * (n-1)!, se n > 1 Passo recursivo
Exemplo de Algoritmo 
recursivo
27
inteiro FatorialRecursivo (inteiro n)
{ 
se (n = 1) Base da recursão
{
retorne 1;
} 
senão
{ 
retorne (n * FatorialRecursivo (n – 1));
}
} 
Exemplo de Algoritmo 
recursivo
28
inteiro FatorialRecursivo (inteiro n)
{ 
se (n = 1)
{
retorne 1;
} 
senão
{ 
retorne (n * FatorialRecursivo (n – 1));
}
}
Passo recursivo
Exemplo de Algoritmo 
recursivo
29
int FatorialRecursivo (int n)
{ 
if (n == 1) Base da recursão
return (1);
else
return (n * FatorialRecursivo (n - 1));
}
Passo recursivo
Exemplo de Algoritmo 
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);
Simulando o algoritmo
31
4
inteiro FatorialRecursivo (inteiro n) 
{ 
se (n = 1)
{ 
retorne 1;
} 
senão
{
retorne (n * FatorialRecursivo (n - 1));
}
}
N � FatorialRecursivo (4);
4
Simulando o algoritmo
32
inteiro FatorialRecursivo (4) 
{ 
se (4 = 1)
{ 
retorne 1;
} 
senão
{
retorne (4 * FatorialRecursivo (4 - 1));
}
}
FatorialRecursivo (4)
4
Simulando o algoritmo
33
inteiro FatorialRecursivo (3) 
{ 
se (3 = 1)
{ 
retorne 1;
} 
senão
{
retorne (3 * FatorialRecursivo (3 - 1));
}
}
FatorialRecursivo (3)
4 3
Simulando o algoritmo
34
inteiro FatorialRecursivo (2) 
{ 
se (2 = 1)
{ 
retorne 1;
} 
senão
{
retorne (2 * FatorialRecursivo (2 - 1));
}
}
FatorialRecursivo (2)
4 3 2
Simulando o algoritmo
35
inteiro FatorialRecursivo (1) 
{ 
se (1 = 1)
{ 
retorne 1;
} 
senão
{
retorne (n * FatorialRecursivo (n - 1));
}
}
FatorialRecursivo (1)
4 3 2 1
Simulando o algoritmo
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
Simulando o algoritmo
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
Simulando o algoritmo
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
Simulando o algoritmo
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
Simulando o algoritmo
40
Exercício
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
Exercício
int MDC (int n, int m)
{ 
}
42
Exercício
int MDC (int n, int m)
{ 
if ( (n>=m) && ((n%m)==0) )
return(m);
}
43Exercício
int MDC (int n, int m)
{ 
if ( (n>=m) && ((n%m)==0) )
return(m);
else
{ 
}
}
44
Exercício
int MDC (int n, int m)
{ 
if ( (n>=m) && ((n%m)==0) )
return(m);
else
{ 
if (n<m) 
return (MDC(m,n));
}
}
45
Exercício
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
Exercício
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
Exercício
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
Exercícios 
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.
Recursividade
DCC120
Laboratório de Programação
50
Definição
� 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
� A linguagem C é uma linguagem recursiva.
51
Exemplo de Algoritmo 
recursivo
Cálculo do valor de 2n para um número n:
Aprendemos que 2n = 2 * 2 * 2 * D * 2.
52
Exemplo de Algoritmo 
recursivo
Implementação iterativa muito simples:
int Potencia(int n)
{ 
int Pot, i;
Pot = 1;
for (i = 1; i <= n; i++)
Pot = Pot * 2;
return (Pot);
}
53
Calcular o valor de 2n como sendo 2 * 2n-1:
2, se n = 1
2n
2 * 2n-1, se n > 1
Exemplo de Algoritmo 
recursivo
54
Exemplo de Algoritmo 
recursivo
� Significa que, para cálculo do valor de 2n
para um determinado n, há necessidade de 
que se recorra aos cálculos anteriores.
Por exemplo: Quanto é o 24?
55
24
24 =
Exemplo de Algoritmo 
recursivo
2, se n = 1
2n
2 * 2n-1, se n > 1
56
24
24 = 2 * 23
Exemplo de Algoritmo 
recursivo
2, se n = 1
2n
2 * 2n-1, se n > 1
57
24
24 = 2 * 23
23 =
Exemplo de Algoritmo 
recursivo
2, se n = 1
2n
2 * 2n-1, se n > 1
58
24
24 = 2 * 23
23 = 2 * 22
Exemplo de Algoritmo 
recursivo
2, se n = 1
2n
2 * 2n-1, se n > 1
59
24
24 = 2 * 23
23 = 2 * 22
22 =
Exemplo de Algoritmo 
recursivo
2, se n = 1
2n
2 * 2n-1, se n > 1
60
24
24 = 2 * 23
23 = 2 * 22
22 = 2 * 21
Exemplo de Algoritmo 
recursivo
2, se n = 1
2n
2 * 2n-1, se n > 1
61
24
24 = 2 * 23
23 = 2 * 22
22 = 2 * 21
21 =
Exemplo de Algoritmo 
recursivo
2, se n = 1
2n
2 * 2n-1, se n > 1
62
24
24 = 2 * 23
23 = 2 * 22
22 = 2 * 21
21 = 2
Exemplo de Algoritmo 
recursivo
2, se n = 1
2n
2 * 2n-1, se n > 1
63
24
24 = 2 * 23
23 = 2 * 22
22 = 2 * 21 = 2 * 2 = 4
21 = 2
Exemplo de Algoritmo 
recursivo
2, se n = 1
2n
2 * 2n-1, se n > 1
64
24
24 = 2 * 23
23 = 2 * 22 = 2 * 4 = 8
22 = 2 * 21 = 2 * 2 = 4
21 = 2
Exemplo de Algoritmo 
recursivo
2, se n = 1
2n
2 * 2n-1, se n > 1
65
24
24 = 2 * 23 = 2 * 8 = 16
23 = 2 * 22 = 2 * 4 = 8
22 = 2 * 21 = 2 * 2 = 4
21 = 2
Exemplo de Algoritmo 
recursivo
2, se n = 1
2n
2 * 2n-1, se n > 1
66
24
24 = 2 * 23 = 2 * 8 = 16
23 = 2 * 22 = 2 * 4 = 8
22 = 2 * 21 = 2 * 2 = 4
21 = 2
Portanto, 24 = 16
Exemplo de Algoritmo 
recursivo
2, se n = 1
2n
2 * 2n-1, se n > 1
67
� 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.
Exemplo de Algoritmo 
recursivo
68
2, se n = 1 Base da recursão
2n
2 * 2n-1, se n > 1 Passo recursivo
Exemplo de Algoritmo 
recursivo
69
int PotenciaRecursivo (int n)
{ 
if (n == 1) Base da recursão
return (2);
else
return (2 * PotenciaRecursivo (n - 1));
}
Passo recursivo
Exemplo de Algoritmo 
recursivo
70
Exercícios 
1) Escreva uma função recursiva para calcular o N-ésimo
número da sequê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 um procedimento recursivo que imprima na tela os 
números ímpares de 1 à um número fornecido pelo usuário.
71
Exercícios 
4) Escreva um procedimento recursivo, 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.