Caso base e caso recursivo: onde a recursão para

As duas partes de toda recursão

Se a recursão fosse uma escada que você desce, o caso recursivo seria o gesto de descer mais um degrau, e o caso base seria o chão, o último degrau, onde você para de descer. Toda função recursiva bem construída tem os dois. O caso recursivo é a parte que chama a si mesma para um caso menor, encolhendo o problema. O caso base é o caso tão simples que a resposta é imediata, sem precisar chamar mais nada. Na contagem regressiva da aula anterior, o caso recursivo era escrever o número e chamar a contagem para o número menos um; o caso base era o número ter chegado a zero, quando a função só grita já e para. Sem o caso base, a escada não teria chão, e a função desceria degraus para sempre.

função fatorial(n)
  se n <= 1 então
    retorne 1          // CASO BASE: resposta direta, não chama mais
  senão
    retorne n * fatorial(n - 1)   // CASO RECURSIVO: chama para o caso menor
  fim
fim

fatorial(4)   // 4 * fatorial(3) = 4 * 3 * fatorial(2) = 4 * 3 * 2 * 1 = 24

As duas partes lado a lado: o caso base para em n igual a 1; o caso recursivo multiplica n pela recursão de n menos um.

O vilão: a recursão infinita

Assim como o laço tem o vilão do laço infinito, a recursão tem o dela: a recursão infinita. Ela nasce de dois descuidos. O primeiro é esquecer o caso base: a função só tem a parte que chama a si mesma, então nunca encontra um lugar para parar. O segundo é ter um caso base que nunca é alcançado, porque o problema não encolhe na direção certa. Se a contagem regressiva chamasse a si mesma com o número mais um em vez de menos um, ela se afastaria do zero para sempre, e o caso base, embora exista, jamais chegaria. Em ambos os casos, a função chama a si mesma sem parar, e o programa, diferente do laço infinito que só trava, costuma estourar com um erro específico quando a pilha de chamadas enche, assunto da próxima aula.

Escrevendo recursão com segurança

Para escrever recursão sem cair na armadilha, siga um roteiro simples que funciona sempre. Primeiro, pergunte: qual é o caso mais simples possível, aquele cuja resposta eu sei de cabeça, sem pensar? Esse é o seu caso base, e você o escreve primeiro, com a resposta direta. Depois, pergunte: como eu resolvo o caso geral usando uma versão menor do mesmo problema? Essa é a chamada recursiva, e você precisa garantir que o argumento encolha na direção do caso base. Se as duas partes estão no lugar, o caso base existe e é alcançável, a recursão funciona. É a mesma disciplina que você usa para não escrever laço infinito: garantir que exista uma condição de parada e que o programa caminhe até ela. Comece pelo fim (o caso base) e a recursão para de assustar.