A otimização da chamada de cauda está presente em muitos idiomas e compiladores. Nesta situação, o compilador reconhece uma função do formulário:
int foo(n) {
...
return bar(n);
}
Aqui, o idioma é capaz de reconhecer que o resultado que está sendo retornado é o resultado de outra função e alterar uma chamada de função com um novo quadro de pilha em um salto.
Perceba que o método fatorial clássico:
int factorial(n) {
if(n == 0) return 1;
if(n == 1) return 1;
return n * factorial(n - 1);
}
é não chamada de cauda otimizável por causa da inspeção necessária no retorno. ( Exemplo de código-fonte e saída compilada )
Para tornar essa chamada otimizável,
int _fact(int n, int acc) {
if(n == 1) return acc;
return _fact(n - 1, acc * n);
}
int factorial(int n) {
if(n == 0) return 1;
return _fact(n, 1);
}
Compilando este código com gcc -O2 -S fact.c
(o -O2 é necessário para permitir a otimização no compilador, mas com mais otimizações de -O3 fica difícil para um ser humano ler ...)
_fact(int, int):
cmpl $1, %edi
movl %esi, %eax
je .L2
.L3:
imull %edi, %eax
subl $1, %edi
cmpl $1, %edi
jne .L3
.L2:
rep ret
( Exemplo de código-fonte e saída compilada )
Pode-se ver no segmento .L3
, o jne
em vez de um call
(que faz uma chamada de sub-rotina com um novo quadro de pilha).
Por favor, note que isso foi feito com C. A otimização da chamada tail em Java é difícil e depende da implementação da JVM (que disse, eu não vi nenhum que faça isso, porque é difícil e implicações do modelo de segurança Java necessário requerer quadros de pilha - que é o que o TCO evita) - tail-recursion + java e tail-recursion + optimization são bons conjuntos de tags para navegar. Você pode descobrir que outras linguagens JVM são capazes de otimizar a recursão de cauda (tente clojure (que requer o recorrente para otimizar a chamada de retorno), ou scala).
Dito isto,
Háumacertaalegriaemsaberquevocêescreveualgocorreto-damaneiraidealqueissopodeserfeito.
Eagora,
Para a questão geral de "métodos para evitar um estouro de pilha em um algoritmo recursivo" ...
Outra abordagem é incluir um contador de recursão. Isso é mais para detectar loops infinitos causados por situações além do controle (e códigos ruins).
O contador de recursão assume a forma de
int foo(arg, counter) {
if(counter > RECURSION_MAX) { return -1; }
...
return foo(arg, counter + 1);
}
Cada vez que você faz uma chamada, você incrementa o contador. Se o contador ficar muito grande, você cometeu um erro (aqui, apenas um retorno de -1, embora em outras linguagens você possa preferir lançar uma exceção). A ideia é evitar que coisas piores aconteçam (erros de falta de memória) ao fazer uma recursão que é muito mais profunda do que o esperado e, provavelmente, um loop infinito.
Em teoria, você não deveria precisar disso. Na prática, vi um código mal escrito que atingiu isso por causa de uma infinidade de pequenos erros e más práticas de codificação (problemas de simultaneidade multithread onde algo muda algo fora do método que faz com que outro thread entre em um loop infinito de chamadas recursivas).
Use o algoritmo correto e resolva o problema certo. Especificamente para a conjectura Collatz, aparece que você está tentando resolvê-lo da maneira xkcd :
Vocêestácomeçandoemumnúmeroefazendoumatravessiadeárvore.Issolevarapidamenteaumespaçodepesquisamuitogrande.Umaexecuçãorápidaparacalcularonúmerodeiteraçõesparaarespostacorretaresultaemcercade500etapas.Issonãodeveserumproblemapararecursãocomumpequenoquadrodepilha.
Emboraconhecerasoluçãorecursivanãosejaumacoisaruim,tambéméprecisoperceberquemuitasvezesasoluçãoiterativa