Recursão

"To understand recursion, we must first understand recursion." (Anônimo)

Recursão é um método de resolver um problema dividindo-o em instâncias menores do mesmo problema. As soluções dos problemas menores são então combinadas para obter a solução do problema original. Em programação, isso acontece quando uma função chama a si mesma.

Pense em uma matriosca, a boneca russa que guarda outra boneca dentro de si, que guarda outra, e assim por diante. Para encontrar a menor boneca, abrimos a maior; se dentro dela houver outra, abrimos essa também, e repetimos até chegar a uma boneca que não abre. A recursão funciona da mesma forma: cada chamada "abre" um problema um pouco menor, até chegar a um problema tão simples que se resolve diretamente.

Uma função pode chamar a si mesma?

Antes de escrever código, pense nas perguntas abaixo. Tente responder antes de abrir cada resposta.

Caso base e passo recursivo

Toda função recursiva tem dois ingredientes:

• Caso base: a versão mais simples do problema, resolvida diretamente, sem nova chamada recursiva. É o que garante que a recursão termina.
• Passo recursivo (ou etapa de redução): a função resolve uma versão menor do mesmo problema, chamando a si mesma, e usa esse resultado para resolver o problema original.

Sem caso base, ou com um caso base que o passo recursivo nunca alcança, temos uma recursão infinita, o equivalente recursivo de um laço infinito.

Fatorial

O fatorial de um inteiro é o produto dos inteiros de a , com . Por exemplo, . Repare que e, em geral,

A definição já é recursiva: o fatorial de é definido a partir do fatorial de um número menor. Para escrever a função, começamos pelo passo recursivo:

int fatorial(int n) {
    return n * fatorial(n - 1);   /* passo recursivo */
}

Essa versão nunca para: fatorial(0) chamaria fatorial(-1), que chamaria fatorial(-2)... Falta o caso base, o problema mais simples, que sabemos resolver diretamente: .

Ida e volta

Este é o ponto central para entender recursão. Uma função recursiva tem um caminho de ida, em que as chamadas se empilham, uma dentro da outra, e um caminho de volta, em que as chamadas terminam na ordem inversa, à medida que a pilha é desempilhada.

1. 1

   Código antes da chamada#

   Execute como está e observe a saída: 5 4 3 2 1 0. O printf vem antes da chamada recursiva, então executa na ida.

2. 2

   Código depois da chamada#

   Comente o primeiro printf e descomente o segundo. Antes de executar, preveja a saída. Agora ela é 0 1 2 3 4 5: o printf vem depois da chamada, então executa na volta.

3. 3

   Antes e depois#

   Deixe os dois printf ativos. Antes de executar, escreva a saída que você espera e depois confira.

No fatorial, a multiplicação n * fatorial(n - 1) só pode ser feita depois que fatorial(n - 1) devolve seu valor. Por isso, na ida, as chamadas apenas se empilham; as multiplicações acontecem todas na volta:

O programa abaixo mostra o mesmo processo, com um recuo por nível de recursão:

Exemplos

Antes de olhar cada solução, tente responder:

1. O que a função precisa receber para funcionar (quais parâmetros)?
2. O que ela deve devolver?
3. Qual é o caso mais simples (caso base)? Como reduzir o problema a um menor (passo recursivo)?

Soma de 1 a n

É quase o mesmo problema do fatorial, mas somando em vez de multiplicar:

Com a definição matemática em mãos, o código é direto:

int soma(int n) {
    if (n == 0)                  /* caso base */
        return 0;
    else                         /* passo recursivo */
        return n + soma(n - 1);
}

São feitas chamadas, e a pilha chega a ter quadros ao mesmo tempo: a função é em tempo e em memória.

Soma dos pares de 2 até n

Para :

int f(int n) {
    if (n == 2)                  /* caso base */
        return 2;
    else if (n % 2 == 1)         /* ímpar: não soma */
        return f(n - 1);
    else                         /* par: soma */
        return n + f(n - 1);
}

Quantidade de dígitos

O caso base é um número com um único dígito (), que tem 1 dígito. Caso contrário, retiramos um dígito e contamos mais um. Para retirar o último dígito, basta a divisão inteira por 10:

int contaDigitos(int n) {
    if (n < 10)                          /* caso base */
        return 1;
    else                                 /* passo recursivo */
        return 1 + contaDigitos(n / 10);
}

Cada chamada divide por 10: o número de chamadas é o número de dígitos, cerca de . A função é .

Encontre o erro

A função somaDigitos abaixo deveria devolver 10 para 1234. Antes de executar, tente prever o que ela devolve.

Qual é o mistério?

O que a função abaixo calcula?

int misterio(int n) {
    if (n == 1)
        return 0;
    else
        return 1 + misterio(n / 2);
}

Recursão com vetores

Procurar um valor y no vetor x de n elementos, devolvendo seu índice ou :

int procura(int x[], int y, int n) {
    if (n == 0)                  /* vetor vazio: não está */
        return -1;
    if (y == x[n - 1])           /* está na última posição */
        return n - 1;
    return procura(x, y, n - 1); /* procura nos n - 1 primeiros */
}

Imprimir os elementos do vetor:

void escreve(int x[], int n) {
    if (n == 0)
        return;
    printf("%d ", x[0]);
    escreve(x + 1, n - 1);
}

Somar os elementos do vetor, em duas versões:

int soma(int x[], int n) {
    if (n == 0)
        return 0;
    else
        return x[0] + soma(x + 1, n - 1);   /* primeiro + soma do resto */
}

A segunda versão tem um erro. Execute e leia a mensagem:

Fibonacci: duas chamadas recursivas

A sequência de Fibonacci começa com 0 e 1, e cada termo seguinte é a soma dos dois anteriores:

int fib(int n) {
    if (n == 0 || n == 1)         /* caso base */
        return n;
    return fib(n - 1) + fib(n - 2);
}

Diferente dos exemplos anteriores, o passo recursivo faz duas chamadas. As chamadas deixam de formar uma linha e passam a formar uma árvore, e os mesmos valores são calculados várias vezes, de forma independente:

O programa conta as chamadas para valores crescentes de :

A cada 5 unidades de , o número de chamadas fica cerca de 11 vezes maior: o crescimento é exponencial (aproximadamente ). Uma versão com um laço, que guarda os dois últimos termos, calcula o mesmo em .

Recursão e a pilha

Cada chamada ainda não terminada ocupa um quadro na pilha de execução. Uma recursão muito profunda (ou infinita) esgota a pilha e o programa termina com um estouro de pilha, o mesmo problema de um vetor local grande demais (veja Alocação de Memória). Por isso, além do tempo, vale perguntar quantas chamadas ficam empilhadas ao mesmo tempo.

Exercícios

Encontre e corrija o erro

Cada programa tem um erro. Execute, leia a mensagem (inclusive os avisos do compilador), corrija e execute de novo.

Programa 1

if (exp % 2 == 1)
    return base * potencia(base, exp - 1);

Programa 2

Programa 3

Volte ao programa da soma dos dígitos e ao da soma do vetor, se ainda não os corrigiu.

Rastreie

O que a função abaixo imprime para f(13)? E para f(8)?

void f(int n) {
    if (n == 0)
        return;
    f(n / 2);
    printf("%d", n % 2);
}

Implemente

Soma dos dígitos. Implemente somaDigitos de forma recursiva.

Palíndromo. Uma palavra é um palíndromo se for igual lida da esquerda para a direita e da direita para a esquerda (como arara e osso). Implemente palindromo(s, ini, fim), que verifica o trecho s[ini..fim]: compare as pontas e, se forem iguais, verifique recursivamente o trecho sem elas.

Potência rápida. Calcular multiplicando por ele mesmo vezes custa . Com recursão, dá para fazer muito melhor:

Como o expoente cai pela metade a cada chamada (como na busca binária), são cerca de chamadas. Os testes usam expoentes da ordem de : reduzir o expoente de um em um estoura a pilha, e calcular duas vezes (com duas chamadas) estoura o tempo. As contas são feitas módulo , para os valores caberem em long long.

Referências

• P. Feofiloff. Recursão e algoritmos recursivos. IME-USP.
• Recursividade. Wikipedia.
• Recursion basics. Hyperskill.