Como reconhecer o que é e o que não é recursão de cauda?
Às vezes, é bastante simples (se a auto-chamada é a última declaração, é recursão final), mas ainda há casos que me confundem. Um professor me disse que "se não há instruções a serem executadas após a auto-chamada, é recursão final". Que tal esses exemplos (desconsidere o fato de que eles não fazem muito sentido):
a) Este deve ser recursivo, vendo como a chamada interna é a última declaração, e não há mais nada a ser executado após ela.
function foo(n)
{
if(n == 0)
return 0;
else
return foo(n-2);
}
b) Mas e esse? Deve ser uma chamada final, porque se a condição for verdadeira, nada, exceto que será executado, mas não é a última declaração?
function foo(n)
{
if(n != 0)
return foo(n-2);
else
return 0;
}
c) Que tal este? Nos dois casos, a auto-chamada será a última coisa executada:
function foo(n)
{
if(n == 0)
return 0;
else
{
if(n > 100)
return foo(n - 2);
else
return foo(n - 1);
}
}