Ao tentar resolver o problema,
encontrei obstáculos dentro de obstáculos.
Por isso, adotei uma solução recursiva.
— aluno S.Y., 1998
To understand recursion,
we must first understand recursion.
— anônimo
A ideia de qualquer algoritmo recursivo para um problema é igual à de uma prova por indução matemática:
Para que essa ideia possa ser aplicada com sucesso,
é preciso que o problema tenha uma certa
estrutura recursiva
,
ou seja,
que a solução de cada instância contenha soluções
de instâncias menores.
(Mais precisamente,
soluções de subinstâncias
da instância.)
Muitos problemas computacionais
têm essa estrutura recursiva
.
Um programa recursivo precisa apenas mostrar duas coisas ao computador: 1. como reduzir uma instância a uma subinstância e 2. como obter uma solução da instância a partir da solução da subinstância. O computador cuida do resto!
Escreva um algoritmo recursivo que calcule a soma dos elementos de um vetor A[1 .. n]. Antes de escrever código, é preciso responder a duas perguntas:
Respondidas essas perguntas, é fácil escrever o algoritmo. (Note como a instância n = 0 é tratada com naturalidade.)
| Soma (n, A) |
| 1 . se n = 0 |
| 2 .ooo s := 0 |
| 3 . senão s := Soma (n−1, A) + A[n] |
| 4 . devolva s |
Este algoritmo calcula a soma da-esquerda-para-a-direita,
ou seja, as subinstâncias relevantes da instância A[1 .. n] são A[1 .. n−1],
A[1 .. n−2], etc.
A solução da instância A[1 .. n],
que é a soma A[1] + ⋅⋅⋅ + A[n−1] + A[n],
contém
a solução da instância A[1 .. n−1],
que é a soma A[1] + ⋅⋅⋅ + A[n−1],
e assim por diante.
Poderíamos fazer a soma da-direita-para-a-esquerda,
ou seja, poderíamos dizer que as subinstâncias relevantes
da instância A[1 .. n] são A[2 .. n],
A[3 .. n], etc.
Nesse caso, a solução
da instância A[1 .. n]
contém
a solução
da instância A[2 .. n],
e assim por diante.
Para fazer isso, é preciso tornar o problema mais general.
O problema generalizado tem dados
n, A, e k ≥ 1
e pede a soma A[k] + ··· + A[n].
Eis um algoritmo para o problema generalizado:
| Soma-Dir-Esq (k, n, A) |
| 1 . se k > n |
| 2 .ooo s := 0 |
| 3 . senão s := A[k] + Soma-Dir-Esq (k+1, n, A) |
| 4 . devolva s |
Escreva um algoritmo
para o seguinte problema:
encontrar o valor do maior elemento de um vetor A[1 .. n]
de
inteiros.
(A rigor, eu deveria ter dito
encontre o valor de um elemento máximo
,
pois o vetor pode ter mais que um elemento de valor máximo.)
É claro que o problema só faz sentido se
n ≥ 1.
Nosso primeiro algoritmo é iterativo:
| Max (A, n) |
| 1 . x := A[1] |
| 2 . para i := 2 até n |
| 3 .ooo se A[i] > x |
| 4 .oooooo x := A[i] |
| 5 . devolva x |
Agora, uma versão recursiva do mesmo algoritmo:
| Max-R (A, n) |
| 1 . se n = 1 |
| 2 .ooo devolva A[1] |
| 3 . senão x := Max-R (A, n−1) |
| 4 . senão se x < A[n] |
| 5 . senão; ooo devolva A[n] |
| 6 . senão senão devolva x |
O erro dos parâmetros misteriosos: Ao escrever um algoritmo recursivo, algumas pessoas cometem o erro dos parâmetros misteriosos. Essas pessoas inventam parâmetros que não estão no enunciado do problema, e escrevem
| Max-Misterioso (A, max, i, n) |
| 1 . se i > n |
| 2 .ooo devolva max |
| 3 . senão se A[i] > max |
| 4 . senão ooo max := A[i] |
| 4 . senão devolva Max-Misterioso (A, max, i+1, n) |
Para piorar, essas pessoas tentam explicar as coisas dizendo que
a primeira chamada deve ser Max-Misterioso (A,
A[1], 2, n)
.
Ora, um algoritmo não tem primeira chamada,
nem segunda chamada,
nem última chamada!
Só há uma maneira de salvar alguma coisa desse desastre: explicar ao leitor o que o algoritmo faz. Eis uma explicação correta:
O algoritmo Max-Misterioso recebe um vetor A e números max, i ≥ 1 e n, e devolve o valor de um elemento máximo do conjunto { max, A[i], A[i+1], … , A[n] }.
Escreva um algoritmo iterativo e um recursivo para o seguinte problema: verificar se um dado inteiro x é elemento do vetor A[1 .. n].
O seguinte algoritmo devolve SIM se x está em A[1 .. n] e devolve NÃO em caso contrário. Note que o problema faz sentido com qualquer n ≥ 0 (e o algoritmo trata da instância n = 0 com naturalidade):
| Decide (A, n, x) |
| 1 . i := 1 |
| 2 . enquanto i ≤ n e A[i] ≠ x |
| 3 .ooo i := i+1 |
| 4 . se i > n devolva NÃO |
| 5 . senão devolva SIM |
Eis uma versão recursiva do mesma algoritmo:
| Decide-R (A, n, x) |
| 1 . se n = 0 |
| 2 .ooo devolva NÃO e pare |
| 3 . se A[n] = x |
| 4 . ooo devolva SIM |
| 5 . senão devolva Decide-R (A, n−1, x) |
What I hear, I forget.
What I see, I remember.
What I do, I understand.
— Confucius
Escreva um algoritmo iterativo e um recursivo para o seguinte problema: dado um número x e um vetor crescente A[1 .. n], encontrar j tal que
A[j−1] < x ≤ A[j].
(Note o <
e o ≤
, cada um em seu lugar;
se tivéssemos dois <
, nem toda instância do problema teria solução.)
A solução j pode ter qualquer valor
no intervalo 1 .. n+1,
uma vez que x pode ser menor que A[1]
e maior que A[n].
(Se isso ajudar,
você pode imaginar que A[0] = −∞ e A[n+1] = +∞.)
O seguinte algoritmo resolve o problema e cuida dos valores extremos
j = 1 e j = n+1
de maneira natural e indolor:
| Encontra (A, n, x) |
| 1 . j := 1 |
| 2 . enquanto j ≤ n e A[j] < x |
| 3 .ooo j := j+1 |
| 4 . devolva j |
Eis uma versão recursiva do algoritmo:
| Encontra-R (A, n, x) |
| 1 . se n = 0 |
| 2 .ooo devolva 1 e pare |
| 3 . se A[n] < x |
| 4 . ooo devolva n+1 |
| 5 . senão devolva Encontra-R (A, n−1, x) |
Como muita gente sabe, o algoritmo de busca binária é muito mais eficiente que qualquer dos algoritmos acima.