It depends on how strictly you define "recursion".
If we strictly require it to involve the call-stack (or whatever mechanism for maintaining program state is used), then we can always replace it with something that doesn't. Indeed, languages that lead naturally to heavy use of recursion tend to have compilers that make heavy use of tail-call optimisation, so what you write is recursive but what you run is iterative.
But lets consider a case where we make a recursive call and use the result of a recursive call for that recursive call.
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));
}
Making the first recursive call iterative is easy:
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));
}
We can then clean-up remove the goto
to ward off velociraptors and the shade of 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;
}
But to remove the other recursive calls we're going to have to store the values of some calls into a stack:
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;
}
Now, when we consider the source code, we have certainly turned our recursive method into an iterative one.
Considering what this has been compiled to, we have turned code that uses the call stack to implement recursion into code that does not (and in doing so turned code that will throw a stack-overflow exception for even quite small values into code that will merely take an excruciatingly long time to return [see How can I prevent my Ackerman function from overflowing the stack? for some further optimisations that make it actually return for many more possible inputs]).
Considering how recursion is implemented generally, we have turned code that uses the call-stack into code that uses a different stack to hold pending operations. We could therefore argue that it is still recursive, when considered at that low level.
And at that level, there are indeed no other ways around it. So if you do consider that method to be recursive, then there are indeed things we cannot do without it. Generally though we do not label such code recursive. The term recursion is useful because it covers a certain set of approaches and gives us a way to talk about them, and we are no longer using one of them.
Of course, all of this assumes you have a choice. There are both languages that prohibit recursive calls, and languages that lack the looping structures necessary for iterating.
INC (r)
,JZDEC (r, z)
can implement a Turing machine. It has no 'recursion' - thats a Jump if Zero else DECrement. If the Ackermann function is computable (it is), that register machine can do it.