A pilha de chamadas

A stack como uma pilha de pratos

Imagine uma pilha de pratos: você só coloca e tira do topo. A call stack funciona igual. Quando main() chama fat(4), um "prato" (frame) é empilhado com n=4 e um endereço de retorno. fat(4) chama fat(3) — mais um prato. E assim por diante até o caso base, quando os pratos começam a sair pela ordem inversa, devolvendo os valores computados.

Cada frame é isolado: a variável n de fat(4) é completamente diferente da variável n de fat(3), mesmo tendo o mesmo nome. Quando fat(3) retorna, seu frame é destruído e aquele n some — é por isso que variáveis locais existem apenas enquanto a função existe.

fat(4) passo a passo

Acompanhe cada chamada empilhando um frame e cada return destruindo o frame do topo. Observe como o valor de retorno "sobe" pelos frames até chegar em main().

Anatomia de um frame

// O que um frame de stack contém:
//  ┌─────────────────────────────┐  ← topo (stack pointer)
//  │ variáveis locais            │
//  │ parâmetros                  │
//  │ registradores salvos        │
//  │ endereço de retorno         │  ← onde continuar após return
//  │ frame pointer anterior      │  ← para restaurar o frame do chamador
//  └─────────────────────────────┘  ← base deste frame

// Em Python podemos inspecionar a call stack em runtime:
import inspect

def quem_me_chamou():
    frame = inspect.currentframe().f_back
    print(frame.f_code.co_name)   // nome da função chamadora
    print(frame.f_locals)         // variáveis locais do chamador

Stack overflow e como evitar

// Stack overflow — recursão sem caso base ou muito profunda

def infinita(n):
    return infinita(n + 1)   // nunca termina → stack estoura

// Python levanta RecursionError (limite padrão ~1000 chamadas)
// C/C++ → SIGSEGV (segmentation fault) silencioso

// Solução 1: tornar iterativo (O(1) espaço na stack)
def fat_iter(n):
    r = 1
    while n > 1: r *= n; n -= 1
    return r

// Solução 2: tail call (se a linguagem otimizar)
// fat_tail(4, acc=1) → fat_tail(3, acc=4) → fat_tail(2, acc=12)
// → fat_tail(1, acc=24) → 24
// Cada chamada reutiliza o mesmo frame — sem crescimento.
// Scheme, Erlang, Haskell otimizam automaticamente. Python, não.

Explorando a call stack

Mini projeto: em Python, implemente um decorador @trace que, ao entrar e sair de cada função decorada, imprime o nome da função, os argumentos e o valor de retorno com indentação proporcional à profundidade da call stack. Use inspect.stack() para medir a profundidade atual.

Projeto principal: implemente em C uma versão de quicksort recursivo e depois uma versão iterativa com uma stack explícita (usando um array de pares início/fim). Meça a profundidade máxima de recursão com um array ordenado (pior caso do quicksort) e confirme que a versão iterativa usa O(log n) de espaço na stack com uma boa estratégia de partição.

Desafio extra: escreva um interpretador de expressões aritméticas (como "3 + 4 * (2 - 1)") usando duas stacks explícitas: uma para operadores e uma para operandos (algoritmo Shunting Yard). Compare a pilha explícita com a call stack implícita de um parser recursivo descendente para a mesma gramática.

Teste sua intuição

Onde você encontra isso