Recursão ou iteração: qual escolher

Duas ferramentas para o mesmo fim

Uma verdade que liberta: tudo que se faz com recursão se faz com laço, e vice-versa. Elas não competem por poder, competem por clareza e custo. A escolha, então, não é sobre o que é possível, e sim sobre o que fica mais legível e mais barato para cada problema. A recursão se sai bem quando o problema tem uma estrutura que se repete dentro de si: percorrer uma árvore, onde cada galho é uma árvore menor; dividir para conquistar, onde cada metade é o mesmo problema; explorar caminhos com backtracking, onde a volta vem de graça no retorno das chamadas. Nesses casos, a recursão praticamente escreve o código na forma do problema, e um laço equivalente ficaria cheio de pilhas manuais e mais confuso.

O laço, por sua vez, vence quando a repetição é linear e direta: percorrer uma lista, somar valores, contar ocorrências, repetir uma ação um número fixo de vezes. Se você desenhasse a árvore de recursão desses casos, veria um fio reto, uma chamada por nível, sinal de que a recursão está só imitando um laço, e um laço de verdade faz o mesmo sem gastar a pilha de chamadas. O peso extra da recursão é justamente esse: cada chamada aberta ocupa espaço na pilha, e em profundidade grande isso pode estourar. Um laço mantém o estado em poucas variáveis e roda em profundidade constante. Para repetição simples e possivelmente longa, o laço é a escolha segura.

O custo de pilha e a recursão em cauda

O maior contra da recursão é o custo de pilha. Cada chamada que ainda não terminou fica guardada, esperando as de baixo, e essa espera ocupa memória proporcional à profundidade. Somar de um até um milhão com recursão simples abriria um milhão de chamadas e estouraria a pilha; o mesmo com um laço usa uma variável e vai tranquilo. Existe uma exceção elegante chamada recursão em cauda: quando a chamada recursiva é a última coisa da função, sem nenhuma conta pendente depois dela, não há o que guardar da chamada atual. Algumas linguagens percebem isso e transformam a recursão num laço nos bastidores, com profundidade constante. Nem toda linguagem faz essa otimização, então não dá para contar com ela sempre, mas entender a ideia ajuda a escrever recursões mais leves.

Regras práticas para decidir

Na hora de escolher, algumas perguntas resolvem quase tudo. O problema se divide em subproblemas do mesmo tipo, ou tem forma de árvore? Se sim, comece pensando recursivo, porque o código vai sair mais limpo. A repetição é linear e pode ficar muito profunda? Prefira o laço, para não arriscar a pilha. Você precisa de desempenho máximo num trecho crítico e a recursão não traz clareza extra? O laço costuma ser um pouco mais rápido, por evitar o custo das chamadas. E, se a recursão ficou mais legível mas você teme a profundidade, lembre que dá para converter: toda recursão pode virar laço com uma pilha explícita, e muitas bibliotecas fazem isso justamente para juntar a clareza do raciocínio recursivo com a segurança do laço. Clareza primeiro, custo depois, e a conversão como carta na manga.