Recursão

Caso base, redução e retorno

Uma função recursiva usa a solução de uma versão mais pequena do problema.

1. Define um caso base resolvido diretamente.
2. Reduz a entrada numa medida que avança para esse caso.
3. Combina e devolve o resultado da chamada recursiva.

Para inteiro $n\geq0$, $0!=1$ e $n!=n(n-1)!$ quando $n>0$.

def fatorial(n):
    if n < 0:
        raise ValueError("n deve ser não negativo")
    if n == 0:
        return 1
    return n * fatorial(n - 1)

print(fatorial(4))  # 24

• 4 * (3 * (2 * (1 * fatorial(0)))) deixa multiplicações pendentes: a pilha de chamadas conserva parâmetros e trabalho pendente, resolvidos de dentro para fora.
• Esquecer o return exterior pode produzir None.

Terminação e custo

• Ter um caso base não basta: cada chamada tem de se aproximar dele. fatorial(n) chamar fatorial(n) não reduz nada.
• Nos dígitos de um inteiro não negativo, n % 10 é o último dígito e n // 10 é o prefixo. A base é n == 0, não um dígito zero: soma_digitos(502) soma 2 + 0 + 5 = 7.
• Com entrada -1, -1 // 10 continua -1. Essa redução não termina; valida a pré-condição ou normaliza com abs.
• Python limita a profundidade e não elimina chamadas em posição terminal. Uma recursão matematicamente terminante pode lançar RecursionError.

Estruturas aninhadas e resultados compostos

Contrato: números e listas finitas sem referências cíclicas. Uma lista que se contém a si própria viola a redução estrutural.

def soma_aninhada(xs):
    total = 0
    for elemento in xs:
        if isinstance(elemento, list):
            total += soma_aninhada(elemento)
        else:
            total += elemento
    return total

• A lista vazia soma zero; um número soma-se diretamente; uma lista exige outra chamada. isinstance(elemento, list) decide o ramo.
• Se a chamada interior devolve frequências, soma cada contagem à da mesma chave no resultado exterior; substituir o dicionário perde ocorrências de ramos anteriores. Uma sublista vazia contribui com {}.
• Uma expressão é um inteiro ou (esquerda, operador, direita), com operandos da mesma forma e operador em +, - e *. Avalia ambos os operandos e aplica o operador exterior na ordem recebida; ((8, '-', 3), '*', (2, '+', 1)) dá $5\times3=15$.

Combinar resultados. Expressões como árvores.

Explorar escolhas e evitar repetição

Para somar exatamente um alvo com preços inteiros positivos:

1. Cada posição é escolhida ou ignorada.
2. Ambos os ramos retiram essa posição; só o primeiro subtrai o seu preço ao alvo.
3. Combina-os com or.

• Alvo zero permite a escolha vazia; alvo negativo, ou preços esgotados com alvo positivo, é falha.
• [6, 4, 3] forma 7 com 4 e 3; começar sempre pelo maior falharia.
• O número de posições diminui, garantindo terminação, mas há até $2^n$ subconjuntos. Terminar não implica ser eficiente.
• A recursão direta de Fibonacci repete subproblemas (fib(2) corre duas vezes para fib(4)). Um ciclo com os dois valores anteriores evita a repetição; escolhe recursão pela estrutura e verifica profundidade, repetição e cópias.