Recursividade - Algoritmos / Estruturas de dados (Teoria)

Recursividade: o que é, caso base e caso recursivo, exemplos de fatorial e Fibonacci em Python, pilha de chamadas, vantagens e quando evitar.

Recursividade é quando uma função chama a si mesma para resolver um problema dividindo-o em versões menores do mesmo problema.

Partes de uma função recursiva

def fatorial(n):
    if n <= 1:            # caso base
        return 1
    return n * fatorial(n - 1)   # caso recursivo

print(fatorial(5))  # 120

from functools import lru_cache

@lru_cache(maxsize=None)
def fib(n):
    return n if n < 2 else fib(n - 1) + fib(n - 2)

Sem o lru_cache (memoização), a versão ingênua repete cálculos e fica exponencialmente lenta.

Cada chamada ocupa espaço na pilha. Sem caso base ou com recursão muito profunda, ocorre stack overflow (em Python, RecursionError).

Recursão deixa o código elegante em problemas como árvores, grafos, busca binária e divide and conquer.
Iteração (laços) costuma ser mais eficiente em memória.

Para praticar recursão, algoritmos e estruturas de dados com exemplos e exercícios, estes livros ajudam.

Entendendo Algoritmos (Bhargava): algoritmos clássicos explicados com ilustrações
Lógica de Programação (Forbellone): algoritmos e estruturas de dados, com Python
Melhores livros de lógica de programação: ranking com os livros mais indicados