"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
Muitos problemas têm a seguinte propriedade: cada instância 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:
resolva-a diretamente (use força bruta se necessário);
reduza-a a uma instância menor do mesmo problema,
aplique o método à instância menor e
volte à instância original.
A aplicação desse método produz um algoritmo recursivo. Para mostrar como isso funciona, examinaremos um exemplo concreto.
(Veja o verbete Recursion na Wikipedia.)
Considere 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 da seção anterior:
int maximo_r( int n, int v[])
{
if (n == 1)
return v[0];
else {
int x;
x = maximo_r( n-1, v); /* máximo de v[0..n-2] */
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 vale 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 tivéssemos 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 do vetor 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 acreditam que funções recursivas são inerentemente ineficientes e consomem muito tempo, mas isso é lenda. Talvez a lenda tenha nascido com uma aplicação descuidada da recursão, como num dos exercícios abaixo. (Nem tudo são flores, entretanto. É preciso lembrar do espaçao de memória que a pilha de recursão consome.)
int maximo_rA( 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 = maximo_rA( n-1, v);
if (x < v[n-1]) return v[n-1];
else return x;
}
int maximo_rB( int n, int v[]) {
if (n == 1) return v[0];
if (maximo_rB( n-1, v) < v[n-1]) return v[n-1];
else return maximo_rB( n-1, v);
}
A função maximo_r discutida acima aplica a recursão ao subvetor v[0..n-2]. É possível escrever uma versão que aplique a recursão ao subvetor v[1..n-1].
/* 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 max_r( 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 max_r( int ini, int fim, int v[]) { if (ini == fim-1) return v[ini]; else { int x; x = max_r( 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 função recursiva max_r. A função max_r resolve um problema mais geral que o original. Isso ocorre, com frequência, 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 aplicar a recursão ao subvetor v[1..n-1]. Ela usa aritmética de endereços:
int maximo2_r( int n, int v[]) {
int x;
if (n == 1) return v[0];
x = maximo2_r( 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;
}
F(3)
F(2)
F(1)
F(0)
F(1)
Qual a sequência de invocações da função
provocada por F(5)?
int Euclides( int m, int n) {
int r;
do {
r = m % n;
m = n;
n = r;
} while (r != 0);
return m;
}