Depende de quão estritamente você define "recursão".
Se exigimos estritamente que envolva a pilha de chamadas (ou qualquer mecanismo para manter o estado do programa usado), então podemos sempre substituí-lo por algo que não o faça. De fato, as linguagens que levam naturalmente ao uso pesado da recursão tendem a ter compiladores que fazem uso pesado da otimização da cauda, então o que você escreve é recursivo, mas o que você executa é iterativo.
Mas vamos considerar um caso em que fazemos uma chamada recursiva e usamos o resultado de uma chamada recursiva para essa chamada recursiva.
public static BigInteger Ackermann(BigInteger m, BigInteger n)
{
if (m == 0)
return n+1;
if (n == 0)
return Ackermann(m - 1, 1);
else
return Ackermann(m - 1, Ackermann(m, n - 1));
}
Fazer a primeira chamada recursiva iterativa é fácil:
public static BigInteger Ackermann(BigInteger m, BigInteger n)
{
restart:
if (m == 0)
return n+1;
if (n == 0)
{
m--;
n = 1;
goto restart;
}
else
return Ackermann(m - 1, Ackermann(m, n - 1));
}
Podemos, então, limpar remover o goto para afastar velociraptors e a sombra de Dijkstra:
public static BigInteger Ackermann(BigInteger m, BigInteger n)
{
while(m != 0)
{
if (n == 0)
{
m--;
n = 1;
}
else
return Ackermann(m - 1, Ackermann(m, n - 1));
}
return n+1;
}
Mas, para remover as outras chamadas recursivas, teremos que armazenar os valores de algumas chamadas em uma pilha:
public static BigInteger Ackermann(BigInteger m, BigInteger n)
{
Stack<BigInteger> stack = new Stack<BigInteger>();
stack.Push(m);
while(stack.Count != 0)
{
m = stack.Pop();
if(m == 0)
n = n + 1;
else if(n == 0)
{
stack.Push(m - 1);
n = 1;
}
else
{
stack.Push(m - 1);
stack.Push(m);
--n;
}
}
return n;
}
Agora, quando consideramos o código-fonte, certamente transformamos nosso método recursivo em um método iterativo.
Considerando para o que isso foi compilado, transformamos o código que usa a pilha de chamadas para implementar a recursão no código que não faz (e ao fazer isso transformou o código que lançará uma exceção de estouro de pilha para valores até mesmo pequenos no código que vai demorar um tempo muito longo para voltar [ver Como posso evitar que minha função Ackerman transborde a pilha? para algumas otimizações adicionais que realmente retornam para muitas outras entradas possíveis].
Considerando como a recursão é implementada em geral, transformamos o código que usa a pilha de chamadas em um código que usa uma pilha diferente para manter as operações pendentes. Poderíamos, portanto, argumentar que ainda é recursivo, quando considerado nesse nível baixo.
E a esse nível, não existem outras maneiras de contornar isso. Então, se você considerar esse método como recursivo, então, de fato, não podemos fazer nada sem ele. Geralmente, porém, não rotulamos esse código como recursivo. O termo recursão é útil porque abrange um certo conjunto de abordagens e nos dá uma maneira de falar sobre elas, e não estamos mais usando uma delas.
Claro, tudo isso pressupõe que você tenha uma escolha. Há duas linguagens que proíbem chamadas recursivas e idiomas que não possuem as estruturas de loop necessárias para iterar.