10.Recursividade

Exercí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.