Indução matemática e recursão

Indução é a versão matemática da recursão. Para provar que P(n) vale para todo n ≥ 0, você prova duas coisas:

1. Caso base:   P(0)
2. Passo:       P(k) → P(k+1), para todo k ≥ 0

É exatamente como uma função recursiva correta: o caso base termina e o passo reduz o problema para um caso menor que já “funciona”.

Exemplo: soma dos n primeiros naturais

1 + 2 + … + n = n(n+1) / 2

Base: para n = 1, os dois lados valem 1. Passo: suponha que vale para k. Então 1 + … + k + (k+1) = k(k+1)/2 + (k+1) = (k+1)(k+2)/2, que é a fórmula para k+1. ∎

def soma(n):
    if n == 0:          # caso base
        return 0
    return soma(n - 1) + n   # passo: confia em soma(n-1)

assert all(soma(n) == n * (n + 1) // 2 for n in range(500))

Indução forte

Na indução forte, o passo pode usar P(0), P(1), …, P(k), e não só P(k). É a forma natural para algoritmos de divisão e conquista, como o merge sort, que recursa em metades e não em n − 1.