Introdução às funções recursivas

Na introdução às funções você viu que, em computação, a definição de uma função pega emprestada a definição matemática. Também viu que, assim como na matemática, uma função pode chamar outra função. Como você deve ter imaginado, uma função pode chamar a si mesma, é quando tratamos da chamada recursividade. A questão do desempenho de algoritmos recursivos v.s. algoritmos não recursivos não é estudada na introdução, isso é visto em disciplinas mais avançadas. Por enquanto vamos nos concentrar apenas em o que é recursão e como utilizá-la.

A lógica de um algoritmo recursivo é muito similar à lógica da indução matemática. Dependendo da turma e do professor, exercícios de recursividade não são explorados ou são mas muito brevemente. A recomendação é que se resolvam muitos exercícios que possam ser resolvidos tanto de maneira iterativa quanto recursiva para aprender bem o conceito. Opcionalmente você pode resolver alguns exercícios de indução matemática para ver a relação da indução com a recursividade.

Na apostila do IME-USP os exercícios de recorrência tratam de soluções recursivas.

A lógica básica é: se um termo de uma sequência pode ser expresso em função de outro termo, por exemplo uma progressão aritmética ou geométrica, então podemos escrever um algoritmo recursivo. Em outras palavras: se um passo seguinte pode ser expresso em função do passo anterior ou de um dos passos anteriores, então podemos transformar um algoritmo iterativo num algoritmo recursivo.

Erros de lógica:

• Confundir iteração com recursão;
• Confundir uma função que chama a si mesma com chamar a função com si própria como argumento;
• Recursão infinita ou excessiva.

O que vem abaixo depende dos conhecimentos sobre funções

• Soma dos n primeiros números naturais, agora com função recursiva:

int soma_n(int n) {

    if (n == 0) return n;

    return n + soma_n(n - 1);
}

Considere a seguinte lógica:

1. A soma de n números é igual a somar n com a soma de todos os anteriores a n;
2. Matematicamente, a soma é n + S(n - 1);
3. Mas a soma S(n - 1) por sua vez, recorrendo a ela própria, é S(S(n - 1) - 1);
4. Até onde isso continua? Até S(1) ou S(0), não há mais para onde ir, a soma é igual a ela própria nesses casos.

Veja como escrever isso em notação de função matemática:

[math]\displaystyle{ f(n) = \begin{cases} n & \text{se} & n = 0 \\ n + f(n - 1) & \text{se} & n \gt 0 \end{cases} }[/math]

Perceba que isso é totalmente diferente de usar um laço. Há repetição? Não, o que há é uma sucessão de chamadas da função de si própria até que um limite é atingido, o caso base. Num laço há uma operação de soma que é repetida até que uma variável acumule a soma desejada. Na função recursiva o que ocorre é uma série de chamadas em que o resultado de uma depende do resultado da seguinte, até que no caso base a chamada pára em si própria. Em outras palavras, o que era um laço com um contador de iterações, passa a ser uma função recursiva com um contador de níveis da função dentro de si mesma.

Veja como isso ocorre no computador:

1. n = 10. É o caso base? Não. Então 10 + f(9);
2. 9 é o caso base? Não. Então 9 + f(8);
3. Continue na sucessão até que atinja 1 + f(0);
4. Ao final, o teremos: soma = 10 + 9 + ... + 1 + f(0);
5. No papel, o resultado seria este: f(10) = 10 + f(9) = 9 + f(8) = ... = 1 + f(0) = 0.

Uma analogia: coloque um espelho em frente ao outro, os reflexos tornam-se progressivamente menores, convergindo para um pequeno ponto no infinito.

• Calcule o enésimo termo da sequência de Fibonacci

int fibonacci(int n) {

    if (n == 0) return 0;
    if (n == 1) return 1;

    return fibonacci(n - 1) + fibonacci(n - 2);
}

Em notação de função matemática:

[math]\displaystyle{ f(n) = \begin{cases} n & \text{se} & n = 1 \\ n = 0 & \text{se} & n = 0 \\ n + f(n - 1) + f(n - 2) & \text{se} & n \gt 2 \end{cases} }[/math]

Atenção! o n se refere à posição do número na sequência, não ao próprio número da sequência.

A simulação segue a mesma lógica do caso da soma dos n primeiros inteiros. Como exercício, tente fazer para o cálculo do fatorial de n. Outro exercício: escreva uma função recursiva que calcula xⁿ.

O caso da sequência de Fibonacci ilustra um caso onde a implementação da recursão é mais prática, mas em troca a execução é muito pior do que a versão não recursiva. Isto não é uma regra. Dependendo do problema e da implementação um algoritmo recursivo pode ser melhor, pior ou mesmo indiferente em relação à versão iterativa. Pior e melhor aqui referem-se à custo de memória e tempo de execução.

Versão com função iterativa:

int fibonacci(int n) {

    int i, auxiliar,
        atual = 1, 
        anterior = 0;
    
    if (n == 0) return 0;
    if (n == 1) return 1;

    for (i = 2; i <= n; i++) {
         auxiliar = atual;
         atual = atual + anterior;
         anterior = auxiliar;
    }
    return atual;  
}

A versão iterativa é muito mais eficiente por uma simples razão: uma variável armazena a soma parcial da série para o próximo termo. A versão recursiva não faz isso, recorre a si mesma para recalcular a série inteira desde o começo a cada novo termo.

• Imprima um vetor com função recursiva

/* recebe o vetor v e o índice do último elemento */
int imprima (int vetor[], int indice) {

    printf("\n%d", vetor[indice]);
    if (n == 0) return 0;
    return imprima (vetor, indice - 1);
}

A função imprime em ordem decrescente, do último para o primeiro índice. Cuidado! Os índices começam do n - 1. Portanto, se o vetor tiver 10 elementos e a chamada da função for feita com indice = 10, o primeiro elemento será v[10], enquanto o último elemento, v[0], não será impresso.

Como exercício, tente modificar a função de tal forma que n seja o número de elementos a serem impressos e não o índice do último elemento.

Mesma impressão, mas em ordem crescente:

/* recebe um vetor e o índice do último elemento para imprimir
   nivel é um contador de recorrências da função */
int imprima (int v[], int indice, int nivel) {

    printf("\n%d", v[indice]);
    if (nivel == 0) return 0;
    return imprima (v, indice + 1, nivel - 1);
}

Para imprimir em ordem crescente a função precisa de um parâmetro extra, um contador de níveis da função dentro de si mesma. Para imprimir os 10 primeiros elementos do vetor, 'n' precisa começar do zero e nível começar do nove. Perceba que a chamada da função acabará se traduzindo literalmente em "imprima v do 0 (índice) até o 9 (níveis da função dentro de si mesma)".

Repita o exercício anterior, mas agora tente fazer a função ser lida como "imprima v do primeiro elemento até o último".

Uma analogia: pense num prédio. Na impressão em ordem decrescente, começamos no nono (nível mais alto) andar e fomos descendo até o nível zero (caso base), o nível do solo. Cada nível correspondia ao índice do vetor. Com a impressão em ordem crescente, ainda começamos do nível mais alto e descemos até o zero, mas a cada nível, ao invés de contarmos "nono andar, oitavo andar, ..." estamos contando "avançando um degrau, dois degraus, ...".

• Leia um vetor e devolva um se todos os valores forem iguais ou zero se não forem

/* Recebe dois valores, se forem iguais devolve 1.
   Se não forem, devolve 0. */
int compare (int a, int b) {
    if (a == b) return 1;
    return 0;
}

/* Recebe um vetor e o índice do último elemento.
   Se dois elementos consecutivos forem diferentes, devolve 0.
   Se o índice chegar a 1, significa que todos os elementos são iguais.
   Caso contrário, função entra em mais um nível da recursão */
int procure (int v[], int i) {

    if (compare(v[i], v[i - 1]) == 0) return 0;
    if (i == 1) return 1;
    return procure(v, i - 1);
}

São duas funções, uma comum e outra recursiva. Isso é devido à própria definição de uma função: a função não pode devolver dois valores ao mesmo tempo, ela própria e mais um ou zero dependendo de se todos os elementos do vetor são iguais ou não. Daí a necessidade de se dividir o problema entre duas funções, uma que faz a comparação e outra que faz a busca recursiva. Perceba que existem duas formas da recursão ser interrompida: dois elementos consecutivos são diferentes ou chegou ao fim do vetor (caso base); as duas condicionais nesta ordem! Resolvendo o problema de modo iterativo teremos as mesmas duas formas de interromper a iteração do laço.