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{if} & n = 0 \\ n + f(n - 1) & \text{if} & 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{if} & n = 0 \\ n + f(n - 1) & \text{if} & n \gt 0 \end{cases} }[/math]