Estrutura de Dados – Básica
Professor: Osvaldo Kotaro Takai.
Aula 7: Recursividade
O objetivo desta aula é apresentar o conceito de recursão para solução de problemas.
A recursão é uma técnica de programação em que uma rotina (função) chama a si mesma. A
recursão é uma das técnicas mais interessantes e surpreendentemente eficazes em
programação. Ela não só funciona, mas também oferece um quadro conceitual única para
resolver muitos problemas.
Demonstrando a recursão com números triangulares
Diz-se que os pitagóricos, um bando de matemáticos da Grécia antiga que trabalhavam com o
Pitágoras (do famoso teorema de Pitágoras), sentiram uma conexão mística com a seguinte
seqüência de números: 1, 3, 6, 10, 15, 21, ...
O termo da n-ésima seqüência é obtido acrescentando-se n ao termo anterior. Dessa forma, o
segundo termo é encontrado adicionando-se 2 ao primeiro termo (que é 1), dando 3. O terceiro
é 3 adicionando ao segundo termo (que é 3) dando 6, etc. Os números da seqüência são
chamados números triangulares porque eles podem ser visualizados como uma organização
triangular de objetos, ilustrados como pequenos quadrados como na figura a seguir:
Suponha que você quisesse encontrar o valor de algum termo na seqüência; digamos o quarto
termo (cujo valor é 10). Você poderá perceber que o valor de qualquer termo pode ser obtido
somando todas as colunas verticais de quadrados. Veja a figura abaixo:
No quarto termo, a primeira coluna tem quatro pequenos quadrados, a segunda coluna tem
três, etc. Adicionando, 4 + 3 + 2 + 1, temos 10.
A seguinte função triangular() utiliza esta técnica, baseada em colunas, para encontrar um
número triangular. Ela soma todas as colunas, da altura de n até a altura 1.
1
É claro que você poderia resolver o problema da seguinte forma:
A abordagem anterior pode parecer direta, mas há outra forma de ver este problema. O valor
do n-ésimo termo pode ser pensado como uma soma de duas coisas, em vez de uma
seqüência. São elas:
1. A primeira coluna (mais alta), que tem n quadrados.
2. A soma de todos os quadrados das colunas restantes.
Isto é:
Se conhecêssemos uma função que descobrisse a soma de todas as colunas restantes,
poderíamos escrever nossa função triangulo(), que retorna o valor do n-ésimo número
triangular, da seguinte forma:
Note que a função somaDasColunasRestantes() fará exatamente a mesma coisa que a função
triangulo(). Ou seja, somando todas as colunas para algum número n passado como
argumento. Então, por que não usar a própria função triangulo(), em vez de alguma outra
função? Isso se pareceria com:
Pode parecer surpreendente que uma função possa chamar a si mesma, mas por que ela não
deveria ser capaz de fazê-lo?
Uma chamada da função é (entre outras coisas) uma transferência de controle para o início da
função.
Tudo isso se parece como uma transferência de responsabilidade para outro, só que reduzindo
o tamanho do problema. Alguém me diz para encontrar o nono número triangular. Sei que ele é
9 mais o oitavo número triangular; então eu chamo o João e lhe peço para encontrar o oitavo
número triangular. Quando o João me devolver o oitavo número triangular, acrescento 9 a esse
valor e devolvo o resultado.
2
O João sabe que o oitavo número triangular é 8 mais o sétimo número triangular; então ele
chama a Maria e pede para encontrar o sétimo número triangular. Esse processo continua com
cada pessoa passando a responsabilidade para o outro.
Onde este processo de transferência de responsabilidade acaba? Alguém em algum ponto
deve ser capaz de descobrir uma resposta sem precisar pedir a uma outra pessoa para ajudálo. Se isso não ocorresse, haveria uma cadeia infinita de pessoas transferindo
responsabilidades uma para as outras.
Para evitar isso, a pessoa que receber a incumbência de encontrar o primeiro número
triangular da seqüência (quando n é igual a 1), deve saber, sem perguntar a qualquer pessoa,
que a resposta é 1. Não há números menores para perguntar a outras pessoas, não há nada
para adicionar a qualquer outra coisa, então a transferência pára aqui.
A condição que leva à função recursiva retornar sem fazer outra chamada recursiva é
conhecida como caso base. É importante que cada função recursiva tenha um caso base para
evitar recursão infinita e a conseqüente finalização da função.
Método para solução de problemas de estrutura recursiva
Muitos problemas têm a seguinte propriedade: cada instância — ou seja, cada exemplo
concreto — do problema contém uma instância menor do mesmo problema. Dizemos que
esses problemas têm estrutura recursiva. Para resolver tais problemas podemos aplicar o
seguinte método:
1) Se o problema é pequeno (caso base).
a) Resolva-o diretamente (use força bruta se necessário);
2) Se o problema é grande,
a) Reduza-o a uma versão menor do mesmo problema,
b) Aplique o método ao problema menor e
c) Volte ao problema original.
A aplicação desse método produz um algoritmo recursivo. Para mostrar como isso funciona,
considere o seguinte problema:
Determinar o valor do maior elemento de um vetor v que tem n elementos.
É claro que o problema só faz sentido se o vetor não é vazio, ou seja, se n > 1. Para preparar o
terreno, examine uma tradicional solução iterativa do problema:
3
Agora vamos usar o método para encontrar soluções recursivas. Imagine que n = 8 e o vetor v
contenha os seguintes valores {5, 10, 3, 7, 2, 1, 30, 25}
1) Se o problema é pequeno (caso base)
a) Resolva-o diretamente (use força bruta se necessário).
O problema pequeno para o problema de encontrar o maior elemento de um vetor de n
posições é quando o vetor tem apenas um único número (n==1). Neste caso, o máximo
é v[0].
2) Se o problema é grande,
a) Reduza-o a uma versão menor do mesmo problema.
Como n é grande (n==8), reduzimos o problema dividindo o vetor em duas partes.
Ultima posição do vetor: v[n-1]
0
1
2
3
4
5
6
7
5
10
3
7
2
1
30
25
Vetor sem a última posição (possui n-1 posições)
Assim, o máximo será o maior entre o v[n-1] e o máximo do vetor que possuir n-1
posições.
b) Aplique o método ao problema menor.
Se n-1 == 1, então aplicamos 1a. e retornamos v[0]. Se n-1 > 1 aplicamos novamente
2a. ao vetor com n-2 posições. Esse processo é aplicado sucessivamente até que o
vetor tenha apenas uma posição.
•
•
•
•
•
•
•
•
maximo (8, v) Å maior entre 25 e maximo(7, v)
maximo (7, v) Å maior entre 30 e maximo(6, v)
maximo (6, v) Å maior entre 1 e maximo(5, v)
maximo (5, v) Å maior entre 2 e maximo(4, v)
maximo (4, v) Å maior entre 7 e maximo(3, v)
maximo (3, v) Å maior entre 3 e maximo(2, v)
maximo (2, v) Å maior entre 10 e maximo(1, v)
maximo (1, v) Å 5
c) Volte ao problema original.
•
•
•
•
•
•
•
•
maximo(1, v) Æ 5
maximo(2, v) Æ maior entre 10 e 5
maximo(3, v) Æ maior entre 3 e 10
maximo(4, v) Æ maior entre 7 e 10
maximo(5, v) Æ maior entre 2 e 10
maximo(6, v) Æ maior entre 1 e 10
maximo(7, v) Æ maior entre 30 e 10
maximo(8, v) Æ maior entre 25 e 30
Logo maximo(8, v) Æ 30.
4
A implementação dessa solução recursiva é a seguinte:
Nota: Algumas pessoas acham que funções recursivas consomem muito tempo. Mas isso é
apenas uma lenda propagada por programadores que não sabem usar a recursão.
As função maximo recursiva discutida acima "puxa para a esquerda" o fim do vetor, ou seja,
troca v[0..n-1] pelo vetor v[0..n-2]. É possível escrever uma versão que "empurre para a direita"
o início do vetor.
Observe que essa nova versão da função maximo é apenas uma "embalagem": o serviço
pesado é executado pela função recursiva mx. A função mx resolve um problema mais geral
que o original. Isso ocorre freqüentemente na construção de algoritmos recursivos: é preciso
generalizar o problema para que uma solução recursiva se torne possível.
5
Exercícios
1. Faça um trabalho sobre “As Torres de Hanói”. Apresente o problema, a análise do
algoritmo que soluciona o problema e implemente a solução.
2. Considere a função iterativa maximo exemplificado anteriormente. Faz sentido trocar "x
= v[0]" por "x = 0", como fazem alguns programadores descuidados? Faz sentido trocar
"x = v[0]" por "x = INT_MIN"? Faz sentido trocar "x < v[j]" por "x <= v[j]"?
3. A função abaixo promete encontrar o valor de um elemento máximo de v[0..n-1]. A
função cumpre a promessa?
int maxi (int n, int v[]) {
int j, m = v[0];
for (j = 1; j < n; j++)
if (v[j-1] < v[j]) m = v[j];
return m;
}
4. Critique a seguinte função recursiva; ela promete encontrar o valor de um elemento
máximo de v[0..n-1].
int maximo1A (int n, int v[]) {
int x;
if (n == 1) return v[0];
if (n == 2) {
if (v[0] < v[1])
return v[1];
else return v[0];
}
x = maximo1A (n-1, v);
if (x < v[n-1]) return v[n-1];
else return x;
}
5. Critique a seguinte função recursiva; ela promete encontrar o valor de um elemento
máximo de v[0..n-1].
int maximo1B (int n, int v[]) {
if (n == 1) return v[0];
if (maximo1B (n-1, v) < v[n-1]) return v[n-1];
else return maximo1B (n-1, v);
}
6. Escreva uma função recursiva maxmin que calcule o valor de um elemento máximo e o
valor de um elemento mínimo de um vetor v[0..n-1]. Quantas comparações envolvendo
os elementos do vetor a sua função faz?
7. Escreva uma função recursiva que calcule a soma dos elementos positivos do vetor de
inteiros v[0..n-1]. O problema faz sentido quando n é igual a 0? Quanto deve valer a
soma nesse caso?
8. Escreva uma função recursiva que calcule a soma dos dígitos de um inteiro positivo n.
A soma dos dígitos de 132, por exemplo, é 6.
9. Qual o valor de X (4)?
int X (int n) {
if (n == 1 || n == 2) return n;
else return X(n-1) + n * X(n-2);
}
10. Qual é o valor de f (1,10)? Escreva uma função equivalente que seja mais simples.
double f(double x, double y) {
if (x >= y) return (x + y)/2;
else return f(f(x+2, y-1), f(x+1, y-2));
}
6
11. Qual o resultado da execução do programa abaixo?
int main (void) {
printf ("%d", ff(7));
return 0;
}
int ff(int n) {
if (n == 1) return 1;
if (n % 2 == 0) return ff(n/2);
return ff((n-1)/2) + ff((n+1)/2);
}
12. Execute fusc(7,0).
int fusc (int n, int profund) {
int i;
for (i = 0; i < profund; i++)
printf (" ");
printf ("fusc (%d,%d)\n", n, profund);
if (n <= 1) return 1;
if (n % 2 == 0) return fusc (n/2, profund+1);
return fusc((n-1)/2, profund+1) + fusc((n+1)/2, profund+1);
}
13. A função de Fibonacci é definida assim: F (0) = 0, F (1) = 1 e F (n) = F(n-1) + F(n-2)
para n > 1. Descreva a função F em linguagem C. Faça uma versão iterativa e uma
recursiva.
14. A seguinte função calcula o maior divisor comum dos inteiros positivos m e n. Escreva
uma função recursiva equivalente.
int Euclides(int m, int n) {
int r;
do {
r = m % n;
m = n;
n = r;
} while (r != 0);
return m;
}
15. Escreva uma função recursiva eficiente que receba inteiros positivos k e n e calcule kn.
(Suponha que kn cabe em um int.) Quantas multiplicações sua função executa
aproximadamente?
16. Faça um programa recursivo, em C, que calcule o n-ésimo número:
• Quadrado.
• Fatorial.
7