A árvore de recursão: enxergar o trabalho total

Cada chamada vira um galho

Uma função recursiva raramente age sozinha. Ela chama a si mesma, e cada uma dessas chamadas pode chamar de novo, formando uma cadeia ou uma ramificação. Para entender o que a recursão realmente faz, o melhor é desenhar. A chamada que você fez vira a raiz, no topo. Cada chamada que ela dispara vira um galho descendo. Se cada chamada dispara duas, a árvore se abre em dois a cada nível; se dispara uma, a árvore é um fio reto descendo. O desenho não é enfeite: ele responde às duas perguntas que decidem o custo, quantas chamadas acontecem no total e quão fundo elas vão.

A altura da árvore é a profundidade da recursão. Ela conta quantas chamadas ficam abertas ao mesmo tempo, uma esperando a outra terminar. Isso importa porque cada chamada aberta ocupa espaço na pilha de chamadas do programa, e uma profundidade absurda estoura essa pilha. A largura, por outro lado, conta quantas chamadas existem em cada nível. Multiplicar a largura pela quantidade de níveis dá uma ideia do número total de chamadas, e é aí que mora a diferença entre uma recursão que voa e uma que trava. Uma árvore alta e fina é barata; uma árvore que dobra de largura a cada nível pode ter um número gigantesco de chamadas.

Prever o custo antes de rodar

A grande utilidade da árvore é prever o custo sem executar o código. Compare dois casos. Uma função que soma de n até zero se chama uma vez por passo: a árvore é um fio de altura n, com n chamadas no total, barato. Agora a função clássica de Fibonacci ingênua, em que fib de n chama fib de n menos um e fib de n menos dois: cada chamada dispara duas, e a árvore quase dobra de tamanho a cada nível. Para um n pequeno já são centenas de chamadas; para um n médio, milhões, muitas delas repetindo exatamente o mesmo cálculo. Ao desenhar a árvore você vê o desastre antes de rodar e percebe que dá para consertar guardando resultados, ideia que volta no módulo de memoização.

contador <- 0
FUNÇÃO f(n)
  contador <- contador + 1
  SE n <= 1 ENTÃO
    RETORNE 1
  FIM
  RETORNE f(n - 1) + f(n - 2)
FIM
f(4)
escreva(contador)

Quando a árvore explode

Ler a árvore ensina a farejar dois perigos. O primeiro é a árvore que se ramifica e repete: quando o mesmo subproblema aparece em vários galhos, a recursão recalcula a mesma coisa de novo e de novo, e o custo dispara. O sinal é ver o mesmo rótulo se repetindo pela árvore, como os vários fib de 2. O segundo perigo é a árvore alta demais, mesmo que fina: se a profundidade chega a dezenas de milhares, a pilha de chamadas do programa pode estourar antes de a resposta sair. Nos dois casos a solução não é abandonar a recursão, e sim reconhecê-la a tempo, seja guardando resultados repetidos, seja trocando a recursão profunda por um laço, tema da última aula deste módulo.