Recursão — como funciona, exemplos e casos base

Recursão na matemática significa definir uma função, sequência ou processo usando casos menores da mesma ideia. Uma definição recursiva só funciona se incluir um caso base e uma regra que leve cada novo caso em direção a esse caso base.

Se você só precisa da ideia central, ela é esta: a recursão deixa de ser útil no momento em que a regra de redução já não alcança um ponto de parada válido.

O que recursão significa na matemática

Uma definição recursiva não lista cada caso separadamente. Em vez disso, ela fornece um ponto de partida e uma regra para construir casos maiores a partir de casos menores.

Isso é diferente de uma fórmula direta. Uma fórmula direta dá a resposta a partir da entrada em uma única expressão. Já uma definição recursiva reduz o problema passo a passo até chegar a um caso que já é conhecido.

Por que um caso base é necessário

O caso base é o ponto de parada. Sem ele, a definição continua se referindo a casos cada vez menores sem nunca terminar.

O caso base também precisa ser compatível com a regra escolhida. Se o passo recursivo reduz de $n$ para $n-1$, então o caso base precisa ser alcançável por esse padrão para as entradas permitidas.

Exemplo resolvido: recursão do fatorial

Fatorial é uma definição recursiva padrão. Para números inteiros não negativos $n \ge 0$, defina o fatorial por

$$0! = 1$$

e, para $n \ge 1$,

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

Aqui, $0! = 1$ é o caso base, e $n! = n(n-1)!$ é o passo recursivo.

Para encontrar $4!$, continue reduzindo até que o caso base apareça:

$$4! = 4 \cdot 3! = 4 \cdot 3 \cdot 2! = 4 \cdot 3 \cdot 2 \cdot 1! = 4 \cdot 3 \cdot 2 \cdot 1 \cdot 0!$$

Agora aplique o caso base $0! = 1$:

$$4! = 4 \cdot 3 \cdot 2 \cdot 1 \cdot 1 = 24$$

Esse é o padrão completo da recursão: reduzir para um caso menor, atingir o caso base e depois calcular de volta até a pergunta original.

Recursão vs. relação de recorrência

Recursão é a ideia mais ampla. Uma relação de recorrência é uma regra recursiva para uma sequência, em que cada termo depende de termos anteriores.

Por exemplo, a sequência de Fibonacci é dada por uma recorrência porque cada termo é definido a partir de termos anteriores. O fatorial também é recursivo, mas geralmente é apresentado como uma definição recursiva de uma função, e não como uma recorrência para uma sequência.

Erros comuns em recursão

Deixar de fora o caso base

Se não houver caso base, a definição não termina.

Usar um passo que não diminui

Se o passo recursivo não avança em direção ao caso base, o processo pode entrar em loop para sempre ou ficar indefinido para algumas entradas.

Esquecer a condição da regra

No exemplo do fatorial, a regra $n! = n(n-1)!$ é usada para $n \ge 1$. Essa condição importa. Sem ela, você poderia tentar aplicar a regra onde a definição não foi pensada para valer.

Supor que recursão é apenas uma ideia de programação

A recursão aparece na matemática muito antes do código. Ela é uma forma de definir funções, sequências e conjuntos por referência a casos menores. Depois, a indução é frequentemente usada para provar afirmações sobre essas definições recursivas.

Quando a recursão é útil

A recursão é útil quando um problema naturalmente se divide em versões menores de si mesmo. Você a vê em fatoriais, sequências do tipo Fibonacci, conjuntos definidos recursivamente e muitos algoritmos.

Ela é especialmente útil quando o caso menor tem a mesma estrutura do caso original. Se o caso menor não for realmente o mesmo tipo de problema, a recursão geralmente não é a ferramenta certa.

Um teste rápido para uma definição recursiva consistente

Faça duas perguntas:

1. Eu tenho um caso base?
2. Cada passo recursivo me aproxima dele?

Se alguma das respostas for não, a definição precisa ser corrigida.

Tente um problema semelhante

Defina uma sequência por

$$a_1 = 2, \qquad a_n = a_{n-1} + 3 \quad \text{for } n \ge 2$$

Depois, encontre $a_2$, $a_3$ e $a_4$. É uma forma rápida de praticar como identificar o caso base e o passo recursivo em um novo contexto.