"Para fazer um procedimento recursivo é preciso ter fé."
—prof. Siang Wun Song
"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
(Veja o verbete Recursion na Wikipedia.)
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 um tal problema podemos aplicar o seguinte método:
A aplicação desse método produz um algoritmo recursivo. Para mostrar como isso funciona, esta página analisa o seguinte problema:
Determinar o valor de um elemento máximo de um vetor v[0 .. n-1] .
É 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:
int maximo (int n, int v[])
{
int j, x;
x = v[0];
for (j = 1; j < n; j += 1)
if (x < v[j]) x = v[j];
return x;
}
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;
}
Eis uma função recursiva que resolve o problema:
int maximo1 (int n, int v[])
{
if (n == 1)
return v[0]; /* problema pequeno */
else {
int x;
x = maximo1 (n-1, v); /* instância menor do problema */
if (x > v[n-1])
return x;
else
return v[n-1];
}
}
A análise do algoritmo tem a mesma forma que uma prova por indução. Se n é 1 então v[0] é o único elemento relevante do nosso vetor e portanto v[0] é o máximo. Agora suponha que n vale mais que 1. Então nosso vetor tem duas partes: v[0..n-2] e v[n-1] e portanto o valor que procuramos é o maior dentre
v[n-1] e o máximo de v[0..n-2].
Eis um roteiro que pode ajudar a verificar se a função está correta. 1. Escreva o que a função deve fazer. 2. Verifique que a função de fato faz o que deveria quando n é pequeno, ou seja, quando n=1. 3. Agora imagine que n é grande, ou seja, n ≥ 1; suponha que a função faria a coisa certa se no lugar de n tivessemos algo menor que n; verifique que a função faz o que dela se espera.
Para que uma função recursiva seja compreensível é muito importante que o autor da função diga, explicitamente, o que a função faz. Portanto, eu deveria escrever o seguinte comentário antes do código:
/* Ao receber v e n >= 1, a função devolve o valor */ /* de um elemento máximo de v[0..n-1]. */
[A pergunta "Como o computador executa um algoritmo recursivo?" é relevante, mas será ignorada por enquanto. Veja a página sobre pilhas.]
Algumas pessoas acham que funções recusivas consomem muito tempo. Mas isso é apenas uma lenda propagada por programadores que não sabem usar recursão.
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;
}
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);
}
A função maximo1 discutida acima "puxa pra 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 pra direita" o início do vetor?
/* Ao receber v e n >= 1, esta função devolve o valor */ /* de um elemento máximo do vetor v[0..n-1]. */ int maximo2 (int n, int v[]) { return mx (0, n, v); } /* Recebe v, ini e fim tais que ini < fim. Devolve o */ /* valor de um elemento máximo do vetor v[ini..fim-1]. */ int mx (int ini, int fim, int v[]) { if (ini == fim-1) return v[ini]; else { int x; x = mx (ini + 1, fim, v); if (x > v[ini]) return x; else return v[ini]; } }
Observe que maximo2 é apenas uma "embalagem": o serviço pesado é executado pela funcã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.
A título de curiosidade, eis outra maneira, talvez surpreendente, de implementar o "empurra pra direita". Ela usa aritmética de endereços:
int maximo2 (int n, int v[]) {
int x;
if (n == 1) return v[0];
x = maximo2 (n - 1, v + 1);
if (x > v[0]) return x;
return v[0];
}
int X (int n) {
if (n == 1 || n == 2) return n;
else return X (n-1) + n * X (n-2);
}
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));
}
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);
}
int main (void) {
printf ("%d", ff (7));
return EXIT_SUCCESS;
}
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) ;
}
int XX (int n) {
if (n == 0) return 0;
else return XX (n/3+1) + n;
}
int Euclides (int m, int n) {
int r;
do {
r = m % n;
m = n;
n = r;
} while (r != 0);
return m;
}