Recursão

Mover uma Torre de Hanói de 64 discos leva 18 446 744 073 709 551 615 movimentos; uma função recursiva descreve a solução em quatro linhas.

Uma função que chama a si mesma

Alguns problemas contêm uma cópia menor de si mesmos. O fatorial de 5, escrito 5!, é 5 × 4 × 3 × 2 × 1 = 120. Olhe de novo: é 5 × (4 × 3 × 2 × 1), ou seja, 5 × 4!. Em geral n! = n × (n − 1)!, então para calcular um fatorial você pode calcular um fatorial menor e multiplicar. Uma função que resolve um problema chamando a si mesma numa versão menor é recursiva.

function factorial(n) {
  if (n <= 1) return 1;          // caso base: para aqui
  return n * factorial(n - 1);   // caso recursivo: um problema menor
}
console.log(factorial(5)); // mostra 120

Toda função recursiva precisa de duas partes. O caso base é uma entrada pequena o bastante para ser respondida direto, sem outra chamada: aqui, o fatorial de 1 é 1. O caso recursivo diminui o problema e chama a função de novo. Cada chamada precisa chegar mais perto do caso base. Se não chegar, por exemplo se você escrever factorial(n + 1) por engano, as chamadas nunca terminam.

A pilha de chamadas

Como o computador acompanha todas essas chamadas inacabadas? Quando factorial(5) roda, ele chega a 5 * factorial(4) e precisa esperar a resposta. O computador põe a chamada que espera numa pilha, um monte em que o último item colocado é o primeiro a sair. factorial(4) espera factorial(3), e assim por diante até factorial(1), que devolve 1 na hora. Aí a pilha se desfaz: factorial(2) devolve 2, factorial(3) devolve 6, factorial(4) devolve 24 e factorial(5) devolve 120.

A pilha tem tamanho limitado. Uma recursão que nunca chega ao caso base continua acrescentando chamadas até o espaço acabar, e o JavaScript para com um erro; no Chrome e no Node.js a mensagem é "RangeError: Maximum call stack size exceeded". O mesmo limite faz com que uma recursão muito profunda, de centenas de milhares de níveis, fique melhor escrita como laço.

A Torre de Hanói

A Torre de Hanói é um quebra-cabeça publicado pelo matemático francês Édouard Lucas em 1883. Há três pinos e uma pilha de discos de tamanhos diferentes no primeiro pino, o maior embaixo. O objetivo é levar a pilha inteira para o terceiro pino. Você só pode mover um disco por vez, só o disco de cima de um pino, e nunca pôr um disco maior sobre um menor.

Pensar passo a passo para onde vai cada disco fica confuso rápido. Pensar de forma recursiva deixa tudo curto. Para mover n discos de A para C: primeiro tire do caminho os n − 1 discos de cima, de A para B. Depois mova o maior disco de A para C. Depois mova os n − 1 discos de B para cima dele, em C. Mover n − 1 discos é o mesmo quebra-cabeça, um tamanho menor, e mover um disco é o caso base. Para 3 discos isso dá 7 movimentos; o laboratório mostra a pilha de chamadas esperando a cada movimento.

function hanoi(n, from, to, via) {
  if (n === 0) return;
  hanoi(n - 1, from, via, to);
  console.log("disk " + n + ": " + from + " -> " + to);
  hanoi(n - 1, via, to, from);
}
hanoi(3, "A", "C", "B");  // 7 movimentos

Quantos movimentos levam n discos? Mover n discos custa dois movimentos de n − 1 discos mais um: M(n) = 2M(n − 1) + 1, com M(1) = 1. Isso dá 1, 3, 7, 15, 31, então M(n) = 2ⁿ − 1, e nenhuma solução consegue usar menos. Dez discos levam 1023 movimentos. Sessenta e quatro discos levam 2⁶⁴ − 1 = 18 446 744 073 709 551 615 movimentos; a um movimento por segundo, isso dá cerca de 585 bilhões de anos. É o crescimento O(2ⁿ) da unidade anterior.

Recursão, laços e trabalho repetido

Tudo o que se escreve com recursão pode ser escrito com um laço e uma pilha própria, e casos simples como o fatorial muitas vezes ficam mais claros como laços. A recursão brilha quando o próprio problema tem forma de árvore: dividir uma lista no merge sort, explorar pastas dentro de pastas ou buscar num labirinto, que é o assunto da última unidade. Uma armadilha é o trabalho repetido. Os números de Fibonacci 0, 1, 1, 2, 3, 5, 8, … seguem fib(n) = fib(n − 1) + fib(n − 2). Escrito direto como recursão, fib(10) = 55 faz 177 chamadas, fib(20) faz 21 891 e fib(30) faz 2 692 537, porque os mesmos valores menores são calculados de novo e de novo. Lembrar as respostas já encontradas, ou construir de baixo para cima com um laço, acaba com esse desperdício.