Depende de cómo estrictamente definas "recursión".
Si exigimos estrictamente que incluya la pila de llamadas (o cualquier mecanismo para mantener el estado del programa), siempre podemos reemplazarlo con algo que no lo haga. De hecho, los lenguajes que conducen naturalmente al uso intensivo de la recursión tienden a tener compiladores que hacen un uso intensivo de la optimización de la llamada de cola, por lo que lo que escribe es recursivo, pero lo que ejecuta es iterativo.
Pero consideremos un caso en el que hacemos una llamada recursiva y usamos el resultado de una llamada recursiva para esa llamada 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));
}
Hacer la primera llamada recursiva iterativa es 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));
}
Luego podemos limpiar y eliminar goto
para evitar velociraptors y la 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;
}
Pero para eliminar las otras llamadas recursivas, tendremos que almacenar los valores de algunas llamadas en una pila:
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;
}
Ahora, cuando consideramos el código fuente, ciertamente hemos convertido nuestro método recursivo en uno iterativo.
Teniendo en cuenta para qué se ha compilado esto, hemos convertido el código que utiliza la pila de llamadas para implementar la recursión en un código que no lo hace (y al hacerlo, el código convertido que generará una excepción de desbordamiento de pila para valores incluso muy pequeños en el código eso solo tomará un tiempo extremadamente largo para regresar [ver ¿Cómo puedo evitar que mi función Ackerman se desborde en la pila? para algunas optimizaciones adicionales eso lo hace realmente volver para muchas más entradas posibles]).
Teniendo en cuenta cómo se implementa la recursión en general, hemos convertido el código que usa la pila de llamadas en un código que usa una pila diferente para mantener las operaciones pendientes. Por lo tanto, podríamos argumentar que aún es recursivo, cuando se considera en ese nivel bajo.
Y a ese nivel, de hecho no hay otras formas de evitarlo. Entonces, si consideras que ese método es recursivo, entonces hay cosas que no podemos hacer sin él. En general, aunque no etiquetamos dicho código recursivo. El término recursión es útil porque cubre un cierto conjunto de enfoques y nos da una forma de hablar sobre ellos, y ya no estamos usando uno de ellos.
Por supuesto, todo esto supone que tienes una opción. Hay dos idiomas que prohíben las llamadas recursivas, y los idiomas que carecen de las estructuras de bucle necesarias para la iteración.