Recursão – pilha de chamadas e árvore de chamadas

O que mostra

Uma função recursiva resolve um problema chamando a si mesma com uma versão menor do mesmo problema. Cada chamada empilha um novo quadro na pilha de chamadas; o caso base retorna sem chamar de novo, e então os quadros são desempilhados enquanto os valores sobem. A árvore de chamadas mostra todas as chamadas: o fatorial e a soma de lista formam uma única cadeia, enquanto Fibonacci, a ordenação por intercalação e a torre se ramificam. O Fibonacci simples repete as mesmas chamadas, e o número delas cresce exponencialmente; a memoização guarda os resultados. Sem caso base, a pilha estoura.

Como usar

Escolha uma Função e ajuste n (ou o Alvo na busca binária). Clique em Passo para fazer uma chamada ou um retorno de cada vez, Voltar para desfazer um passo ou Executar para reproduzir na Velocidade escolhida. Observe o código, a pilha e a árvore; toque em um nó para ver detalhes. Marque Memo no Fibonacci ou desmarque Com caso base para ver um estouro de pilha.

Parâmetros que você pode mudar

• Função recursiva Fatorial n!, Números de Fibonacci, Soma de uma lista, Busca binária, Torre de discos (quebra-cabeça), Ordenação por intercalação
• n (tamanho do problema) 0–8
• Valor procurado (busca binária) 0–100
• Memoização (Fibonacci)
• Incluir o caso base
• Linguagem Python, Pseudocódigo
• Velocidade 0,5–10 passos/s

Perguntas para explorar

1. Quantas vezes fib(2) é chamada ao calcular fib(6) sem memoização, e quantas vezes com ela?
2. Qual é a profundidade máxima da pilha para factorial(5), e quanta pilha a versão com laço precisa?
3. Por que retirar o caso base causa um estouro de pilha e não uma resposta errada?