A pilha de chamadas: como o computador não se perde

A pilha de anotações do computador

Quando uma função A chama uma função B, a função A fica pausada, esperando B terminar para continuar de onde parou. Mas como o computador lembra onde A parou, ainda mais quando há uma cadeia de chamadas, A chama B, que chama C, que chama D? A resposta é uma estrutura chamada pilha de chamadas. Imagine uma pilha de pratos: cada função que começa é um prato colocado no topo, com a anotação de onde ela parou. Quando essa função termina, o prato é retirado do topo e o computador volta para a função do prato de baixo, exatamente no ponto em que ela havia pausado. A regra da pilha é rígida: só se mexe no topo. A última função a ser chamada é a primeira a terminar, e só então a de baixo pode continuar.

Essa pilha é a peça que faltava para entender a recursão de verdade. Cada chamada recursiva empilha um prato novo. Na contagem do fatorial de 4, empilha-se fatorial(4), que chama e empilha fatorial(3), que empilha fatorial(2), que empilha fatorial(1). Nesse ponto a pilha tem quatro pratos, e fatorial(1) é o do topo. Como fatorial(1) é o caso base, ele responde 1 sem empilhar mais nada e sai da pilha. Aí fatorial(2), que estava esperando, recebe esse 1, calcula 2 vezes 1, responde 2 e sai. Depois fatorial(3) recebe o 2, faz 3 vezes 2, responde 6 e sai. Por fim fatorial(4) faz 4 vezes 6 e entrega 24. A recursão desce empilhando e sobe desempilhando, e a pilha é quem guarda cada cálculo em espera.

O último a entrar é o primeiro a sair

A pilha de chamadas segue uma regra que aparece em muitos lugares da computação: o último a entrar é o primeiro a sair. É o comportamento natural de qualquer pilha física, uma pilha de pratos, de livros, de bandejas: você tira de cima, e a última coisa colocada é a primeira retirada. Nas chamadas de função, isso significa que a chamada mais recente, a que está no topo, é a que precisa terminar primeiro para que as anteriores continuem. Faz todo sentido: A pausou para esperar B; B não pode continuar A, só pode terminar e devolver o controle. Essa ordem estrita é o que permite ao computador administrar cadeias de chamadas profundas sem se perder, sabendo sempre para onde voltar: para o prato imediatamente abaixo do topo.

Quando a pilha estoura

Agora dá para entender de onde vem o famoso erro de estouro de pilha. A pilha de chamadas tem um limite de tamanho: cabem muitas chamadas empilhadas, mas não infinitas. Numa recursão saudável, os pratos empilham até o caso base e depois desempilham, então a pilha nunca cresce demais. Mas numa recursão infinita, a função chama a si mesma sem parar, empilhando prato após prato sem nunca desempilhar, porque nenhuma chamada chega ao fim. A pilha enche, bate no limite e o programa estoura, com uma mensagem que em muitas linguagens fala em stack overflow, ou pilha estourada. Por isso, quando você vê esse erro, o suspeito número um é uma recursão sem caso base ou com caso base inalcançável. O erro é chato, mas é honesto: ele avisa exatamente qual foi o descuido.