Recursão

Recursão é uma técnica de programação na qual a solução de um problema é definida em termos de soluções de subproblemas mais simples do mesmo problema, e a execução envolve chamadas a si mesma. Para evitar loops infinitos, é necessário um caso base bem definido que encerre a cadeia de chamadas.

A estrutura típica envolve um caso base, que retorna o resultado sem chamar a si mesma, e um caso recursivo, que reduz o problema para um subproblema equivalente. Cada chamada empilha informações até atingir o caso base, momento em que as chamadas são desfeitas conforme os valores são retornados.

Recursão pode ser direta (uma função se chama sozinha) ou indireta (uma função A chama B, que chama A). A recursão de cauda ocorre quando o resultado da chamada recursiva é a única operação restante, permitindo, em algumas linguagens, otimizações de espaço de pilha.

Exemplos clássicos incluem o fatorial, a sequência de Fibonacci, a busca binária em listas ordenadas ou a travessia de estruturas de dados como árvores e grafos. Outros problemas naturalmente recursivos aparecem em algoritmos de divide e conquistar, como a ordenação merge sort.

Desempenho e considerações: a complexidade depende do problema e da implementação. Recursões simples podem ter sobrecarga de chamadas e, sem memoização ou programação dinâmica, podem ter complexidade exponencial. Técnicas como memoização (armazenar resultados de subproblemas) ou recursão de cauda podem melhorar o desempenho. Algumas linguagens oferecem tail call optimization, permitindo uso constante de espaço; outras não.

Recursão é útil pela clareza e pela expressão direta de algoritmos que se estruturam naturalmente por subdivisão, mas nem sempre é a opção mais eficiente em termos de tempo ou memória.