"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 (talvez "recorrente" esteja mais correto) é simples: se a instância em que estamos interessados é pequena, resolva-o diretamente, como puder; se a instância é grande, reduza-a a uma instância menor do mesmo problema. (Portanto, recursão é essencialmente o mesmo que indução matemática.)
Veja o verbete Recursion na Wikipedia.
Escreva um algoritmo recursivo que calcule a soma dos elementos do vetor A[1..n]. Antes de escrever código, é preciso responder duas perguntas:
Feita essa discussão, é fácil escrever o algoritmo (note como a instância n = 0 é tratada com naturalidade):
| Soma (n, A) |
| 1 _ se n = 0 |
| 2 ____ então s ← 0 |
| 3 ____ senão s ← Soma (n−1, A) + A[n] |
| 4 _ devolva s |
O algoritmo acima faz a soma "da esquerda para a direita". Como você faria a coisa para somar "da direita para esquerda"? Para fazer isso é preciso generalizar o problema. O problema generalizado tem dados
n , A e k ≥ 1
e pede a soma A[k]+...+A[n]. Eis o algoritmo:
| Soma-Dir-Para-Esq (k, n, A) |
| 1 o se k > n |
| 2 oooo então s ← 0 |
| 3 oooo senão s ← A[k] + Soma-Dir-Para-Esq (k+1, n, A) |
| 4 o devolva s |
Escreva um algoritmo iterativo e um recursivo para o seguinte problema: encontrar o valor do maior elemento do vetor A[1..n] de inteiros. (O enunciado está torto, pois o vetor pode ter mais que um elemento de valor máximo. Eu deveria ter dito "encontre o valor de um elemento 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 faça |
| 3 ____ se A[i] > x então x ← A[i] |
| 4 _ devolva x |
Agora, uma versão recursiva do mesmo algoritmo:
| Max-Rec (A, n) |
| 1 _ se n = 1 |
| 2 ____ então devolva A[1] |
| 3 ____ senão x ← Max-Rec (A, n−1) |
| 4 ____ senão se x < A[n] |
| 5 ____ senão ___ então devolva A[n] |
| 6 ____ senão ___ senão devolva x |
Ao escrever um algoritmo recursivo, algumas pessoas gostam de cometer o erro dos parâmetros misteriosos. Essas pessoas inventam parâmetros misteriosos, como i e max por exemplo, que não estão no enunciado do problema, e escrevem
| Max-Mal-Documentado (A, max, i, n) |
| 1 _ se i > n |
| 2 ____ então devolva max |
| 3 ____ senão se A[i] > max |
| 4 ____ senão ___ então max ← A[i] |
| 5 ____ senão devolva Max-Mal-Documentado (A, max, i+1, n) |
Para piorar, essas pessoas tentam explicar as coisas dizendo que "a primeira chamada deve ser Max-Mal-Documentado (A, A[1], 2, n)". Ora, não faz sentido algum falar em primeira chamada de uma função recursiva, nem em segunda chamada, nem em última chamada.
Só há uma maneira de salvar alguma coisa nesse desastre: explicar ao leitor o que a função faz. Eis uma explicação correta:
A função Max-Mal-Documentado recebe um vetor A e números max, i e n, sendo i ≥ 1. A função 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].
A seguinte função 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 ____ faça i ← i+1 |
| 4 _ se i > n |
| 5 ____ então devolva não |
| 6 ____ senão devolva sim |
Eis uma versão recursiva da mesma função:
| Decide-Rec (A, n, x) |
| 1 o se n = 0 |
| 2 oooo então devolva não |
| 3 oooo senão se A[n] = x |
| 4 oooo senão ooo então devolva sim |
| 5 oooo senão ooo senão devolva Decide-Rec (A, n−1, x) |
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 no seu lugar; se tivéssemos dois "<" nem toda instância do problema teria solução!)
A seguinte função recebe x e um vetor crescente A[1..n] e devolve j tal que A[j−1] < x ≤ A[j]. Note que x pode ser menor que A[1] ou maior que A[n].
Quais os valores possíveis de j? É fácil perceber que os valores n+1 e 1 fazem sentido. (Se isso ajudar, você pode imaginar que A[n+1] = +∞ e A[0] = −∞.) Eis uma função que faz o serviço de maneira suja, tratando desses dois casos extremos em separado:
| Encontra-Sujo (A, n, x) |
| 1 _ se x ≤ A[1] |
| 2 ____ então devolve 1 |
| 3 ____ senão se A[n] < x |
| 4 ____ senão ___ então devolve n+1 |
| 5 ____ senão ___ senão j ← 2 |
| 6 ____ senão ___ senão enquanto j < n e A[j] < x faça j ← j+1 |
| 7 ____ senão ___ senão devolva j |
É evidente que a seguinte versão do algoritmo faz a mesma coisa é muito mais simples:
| Encontra (A, n, x) |
| 1 _ j ← 1 |
| 2 _ enquanto j ≤ n e A[j] < x faça j ← j+1 |
| 3 _ devolva j |
Eis uma versão recursiva do algoritmo:
| Encontra-Rec (A, n, x) |
| 1 o se n = 0 |
| 2 oooo então devolva 1 |
| 3 oooo senão se A[n] < x |
| 4 oooo senão ooo então devolva n+1 |
| 5 oooo senão ooo senão devolva Encontra-Rec (A, n−1, x) |
Como muita gente sabe, existe um algoritmo muito mais eficiente que qualquer dos acima. Trata-se da busca binária.