Existem diversas estratégias para resolver problemas computacionais. Em muitos casos, um problema aparentemente complexo pode ser simplificado quando o dividimos em partes menores e mais fáceis de resolver. Essa abordagem é conhecida como dividir para conquistar (divide and conquer) e é amplamente utilizada no desenvolvimento de algoritmos.

A recursão é uma técnica de programação baseada nessa ideia. Em vez de resolver um problema diretamente, a solução é construída a partir de versões menores do próprio problema.

De forma geral, dizemos que uma definição é recursiva quando ela é expressa em função dela mesma. Na programação, a recursão ocorre quando uma função realiza chamadas para si própria durante sua execução.

Figura 1 – Exemplo de estrutura recursiva. Em um fractal, o mesmo padrão geométrico é repetido em diferentes escalas, ilustrando a ideia de uma definição construída a partir de versões menores de si mesma.

Um exemplo matemático

Considere o cálculo do fatorial de um número. O fatorial de um número inteiro positivo corresponde ao produto de todos os números inteiros de 1 até ele.

Por exemplo:

$5! = 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1 = 120$

Observe que podemos reescrever essa expressão da seguinte forma:

$5! = 5 \cdot 4!$

De maneira geral:

$n! = n \cdot (n-1)!$

Essa definição é recursiva, pois o cálculo do fatorial de um número utiliza o próprio conceito de fatorial para um valor menor.

Recursão em programação

Ao transportar essa ideia para a programação, podemos implementar uma função que segue exatamente essa definição matemática:

long long int fatorial(int n){
    return n * fatorial(n - 1);
}

Embora essa função seja recursiva, ela possui um problema importante: ela nunca para de executar. A cada chamada, um novo valor é calculado e uma nova chamada é realizada indefinidamente.

Se tentarmos calcular fatorial(5), teremos uma sequência semelhante à seguinte:

fatorial(5)
→ fatorial(4)
→ fatorial(3)
→ fatorial(2)
→ fatorial(1)
→ fatorial(0)
→ fatorial(-1)
→ fatorial(-2)
→ ...

Como não existe uma condição que interrompa o processo, a execução continuará até que a memória disponível para as chamadas de função seja esgotada.