Recursão

Definição

Recursão é uma técnica em que uma função chama a si mesma, direta ou indiretamente, para resolver um problema dividido em subproblemas menores. Cada chamada subsequente deve aproximar-se de uma condição base que determina quando parar.

Por que é importante

A recursão permite expressar soluções de forma mais concisa e elegante, principalmente em estruturas de dados como árvores e algoritmos como busca, ordenação e cálculo de combinações. Ela é uma alternativa à iteração e pode facilitar o raciocínio em certos tipos de problema.

No entanto, seu uso exige cuidado com a condição de parada e o consumo de memória, já que cada chamada ocupa uma posição na pilha de execução.

Linguagens em que é comum

Recursão é suportada na maioria das linguagens modernas, incluindo Python, JavaScript, Java, C, Haskell e outras. Em linguagens funcionais como Haskell, o uso de recursão é preferido em vez de loops imperativos.

Exemplo em código (Python)

# Função recursiva para calcular fatorial
def fatorial(n):
if n == 0:
    return 1
else:
    return n * fatorial(n - 1)

print(fatorial(5))  # 120

Neste exemplo, a função fatorial chama a si mesma com n - 1 até atingir a condição base n == 0. Isso caracteriza uma função recursiva.