Recursão

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:

  1. se a instância que queremos resolver é pequena, resolva-o diretamente, como puder;
  2. se a instância é grande, reduza-a a uma instância menor do mesmo problema;
  3. depois de resolvida a instância menor, volte à instância original.

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!

Exemplo 1: soma recursiva

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:

  1. Qual a entrada e qual a saída de nosso algoritmo? Resposta: nosso algoritmo deve receber um número n e um vetor A e deve devolver um único número, que deve ser igual à soma dos elementos de A[1 .. n].
  2. Para quais valores da entrada o problema faz sentido? Resposta: nosso problema faz sentido para n ≥ 0 e qualquer A[1 .. n]. (Se n = 0, a solução é 0.)

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

Exemplo 2: máximo de um vetor

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] }.

Exemplo 3: busca sequencial

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 in 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)

Exercício 1

  1. Escreva e analise um algoritmo recursivo que receba dois vetores A[1 .. n] e B[1 .. n] e decida se existe um índice i tal que A[i] = B[i].
  2. ★ Escreva um algoritmo recursivo eficiente para decidir se um vetor B[1 .. k] é uma subsequência de um vetor A[1 .. n]. (Por exemplo, (5, 6, 4) é subsequência de (9, 5, 6, 3, 9, 6, 4, 7).)

Exemplo 4: busca em vetor ordenado

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] < xA[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 jn 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.

Exercício 2

  1. Escreva e analise um algoritmo de busca binária para o problema discutido acima. Faça duas versões: uma iterativa e uma recursiva.
  2. ★ Escreva e analise um algoritmo recursivo que calcule ⌊lg n.
  3. Escreva e analise um algoritmo recursivo que calcule ⌈lg n. Quanto tempo seu algoritmo consome?
  4. Escreva uma função recursiva eficiente que receba um número natural k ≥ 1 e um número natural n e calcule kn.  Quantas multiplicações sua função executa aproximadamente?
  5. Escreva um algoritmo recursivo que receba um número natural positivo n e devolva o quociente de 11n − 6 por 5. (Antes, prove por indução matemática que 11n − 6 é divisível por 5 qualquer que seja o natural positivo n. Veja um dos exercícios do Apêndice.)