Recursão: fatorial, Fibonacci e a pilha de chamadas

Uma função é recursiva quando chama a si mesma. A ideia assusta quem a vê pela primeira vez, mas segue duas regras simples, e as questões de concurso cobram sempre a mesma coisa: calcular o valor devolvido por uma função recursiva, dizer em que ordem as instruções são executadas e identificar o erro que produz estouro de pilha. Este guia resolve fatorial, Fibonacci, soma de dígitos e uma impressão de ida e volta, com todos os resultados conferidos por execução de programa.

Sem norma aplicável: é fundamento de programação. Complementa o teste de mesa e a pilha como estrutura de dados.

As duas regras

Toda recursão correta tem:

1. Caso base: uma situação simples, resolvida sem nova chamada. É a condição de parada.
2. Caso recursivo: a função chama a si mesma com um problema menor, que se aproxima do caso base.

Faltando o caso base, ou não se aproximando dele, a recursão não termina.

Fatorial

O fatorial de n é n × (n−1) × … × 1, com 0! = 1. Em pseudocódigo:

função fat(n)
    se n ≤ 1 então retorne 1
    retorne n × fat(n − 1)

A pilha de chamadas para fat(4)

Cada chamada fica “em espera” numa pilha até que a seguinte devolva um valor:

1. fat(4) precisa de fat(3): fica esperando.
2. fat(3) precisa de fat(2): fica esperando.
3. fat(2) precisa de fat(1): fica esperando.
4. fat(1) cai no caso base e devolve 1.
5. fat(2) calcula 2 × 1 = 2 e devolve.
6. fat(3) calcula 3 × 2 = 6 e devolve.
7. fat(4) calcula 4 × 6 = 24 e devolve.

Resultado: fat(4) = 24. A pilha chegou a 4 níveis de profundidade. Valores conferidos: de 0 a 7, os fatoriais são 1, 1, 2, 6, 24, 120, 720, 5040.

Fibonacci

A sequência de Fibonacci começa com 0 e 1; cada termo seguinte é a soma dos dois anteriores: 0, 1, 1, 2, 3, 5, 8, 13…

função fib(n)
    se n < 2 então retorne n
    retorne fib(n − 1) + fib(n − 2)

fib(5) = fib(4) + fib(3) = 3 + 2 = 5.

O custo escondido

Essa versão “ingênua” refaz as mesmas contas muitas vezes. Contando o número de chamadas à função:

n	fib(n)	Chamadas realizadas
0	0	1
1	1	1
2	1	3
3	2	5
4	3	9
5	5	15
6	8	25
7	13	41

O número de chamadas segue a regra chamadas(n) = 1 + chamadas(n−1) + chamadas(n−2). Cresce muito rápido (aproximadamente como uma exponencial), por isso, para n grande, usa-se a versão iterativa (um laço guardando os dois últimos termos) ou guarda-se os resultados já calculados (memoização). Em provas, a conclusão esperada é: a recursão simples do Fibonacci é correta, mas ineficiente.

Soma dos dígitos

função soma(n)
    se n = 0 então retorne 0
    retorne (n mod 10) + soma(n div 10)

Para n = 4821: 1 + soma(482) = 1 + 2 + soma(48) = 1 + 2 + 8 + soma(4) = 1 + 2 + 8 + 4 + soma(0) = 15. O mesmo resultado de uma versão com laço, que você pode comparar com o teste de mesa.

MDC de Euclides recursivo

função mdc(a, b)
    se b = 0 então retorne a
    retorne mdc(b, a mod b)

mdc(84, 36) chama mdc(36, 12), que chama mdc(12, 0), que devolve 12. Resultado: 12. Aqui o caso base é b = 0 e cada chamada reduz o segundo argumento.

Antes e depois da chamada: ida e volta

A posição do comando em relação à chamada recursiva muda a ordem de execução.

procedimento p(n)
    escreva n
    se n > 0 então p(n − 1)
    escreva n

Para p(3), a saída é: 3 2 1 0 0 1 2 3. A primeira metade é impressa na “ida” (antes da chamada recursiva, enquanto a pilha cresce) e a segunda na “volta” (depois da chamada, enquanto a pilha encolhe). Se o comando de escrita antes da chamada fosse removido, a saída seria 0 1 2 3. Essa pegadinha de ordem é muito frequente.

Potência recursiva

Para calcular 2^n: pot(n) = 1 se n = 0; senão 2 × pot(n − 1). Com n = 5: 2 × 2 × 2 × 2 × 2 × 1 = 32. Para 2^10, o resultado é 1024. Cada chamada ocupa espaço na pilha, então o consumo de memória cresce com n.

Estouro de pilha

Se a recursão não tem caso base, ou se o argumento não se aproxima dele, as chamadas se empilham até esgotar a memória reservada: o programa falha. Em Python, por exemplo, há um limite padrão de profundidade (mil, nas versões comuns), e uma função como def f(n): return f(n+1) termina com RecursionError logo que o limite é atingido. O erro tem nomes diferentes conforme a linguagem, mas a causa é a mesma.

Recursão x iteração

Aspecto	Recursão	Iteração (laço)
Estrutura	Função que chama a si mesma	Repetição com enquanto, para ou repita
Memória	Cresce com a profundidade (pilha)	Em geral constante
Clareza	Natural para problemas que se dividem (árvores)	Natural para repetições simples
Risco	Estouro de pilha	Laço infinito

Toda recursão pode ser reescrita com laço (e pilha própria, quando necessário). As árvores, como em árvore binária de busca e percursos, são o caso em que a recursão fica mais natural.

Erros comuns

• Esquecer o caso base.
• Chamar a função com argumento que não diminui.
• Confundir o valor devolvido com o texto impresso.
• Supor que o Fibonacci recursivo faz n chamadas: ele faz muito mais.
• Calcular a soma da “volta” na ordem errada.

Roteiro de resolução

1. Identifique o caso base.
2. Escreva as chamadas em pilha até chegar nele.
3. Resolva de baixo para cima, devolvendo valores.
4. Para impressões, marque quais acontecem na ida e quais na volta.

Próximos passos

Veja busca sequencial e binária, Python: funções, escopo e exceções e ordenação.

Fontes e atualização

Sem norma aplicável. Valores e contagem de chamadas conferidos por execução de programa; o limite de recursão citado vale para as versões comuns de Python e pode ser alterado. Confira o edital e veja a metodologia do site.