Can every recursion be converted into iteration?

Question

A reddit thread brought up an apparently interesting question:

Tail recursive functions can trivially be converted into iterative functions. Other ones, can be transformed by using an explicit stack. Can every recursion be transformed into iteration?

The (counter?)example in the post is the pair:

(define (num-ways x y)
  (case ((= x 0) 1)
        ((= y 0) 1)
        (num-ways2 x y) ))

(define (num-ways2 x y)
  (+ (num-ways (- x 1) y)
     (num-ways x (- y 1))

Answer 1

I'd say yes - a function call is nothing but a goto and a stack operation (roughly speaking). All you need to do is imitate the stack that's built while invoking functions and do something similar as a goto (you may imitate gotos with languages that don't explicitly have this keyword too).

Answer 2

tazzego, recursion means that a function will call itself whether you like it or not. When people are talking about whether or not things can be done without recursion, they mean this and you cannot say "no, that is not true, because I do not agree with the definition of recursion" as a valid statement.

With that in mind, just about everything else you say is nonsense. The only other thing that you say that is not nonsense is the idea that you cannot imagine programming without a callstack. That is something that had been done for decades until using a callstack became popular. Old versions of FORTRAN lacked a callstack and they worked just fine.

By the way, there exist Turing-complete languages that only implement recursion (e.g. SML) as a means of looping. There also exist Turing-complete languages that only implement iteration as a means of looping (e.g. FORTRAN IV). The Church-Turing thesis proves that anything possible in a recursion-only languages can be done in a non-recursive language and vica-versa by the fact that they both have the property of turing-completeness.

Answer 3

A question: if as first thing the function makes a copy of itself in a random void memory space, and then instead of calling itself call the copy, is this still recursion?(1) I would say yes.

Is the explicit use of stack a real way to remove recursion? (2) I would say no. Basically, aren't we imitating what happens when we use explicitly recursion? I believe we can't define recursion simply as "a function that call itself", since I see recursion also in the "copy code" (1) and in the "explicit use of stack" (2).

Moreover, I don't see how the CT demonstrates that all recursive algorithms can become iterative. It only seems to say to me that "everything" having the "power" of the Turing machine can express all algorithms this can express. If Turing-machine can't recursion, we are sure every recursive algo has its interative translation... The Turing-machine can recursion? According to me, if it can be "implemented" (by any mean), then we can say it has it. Has it? I don't know.

All real CPUs I know can recursion. Honestly, I can't see how to program for real without having a call stack, and I think this is what makes recursion possible first.

Avoiding copying(1) and "imitated stack"(2), have we demonstrated that every recursive algo can be, on real machines, be expressed iteratively?! I can't see where we demonstrated it.

Answer 4

Recursion is implemented as stacks or similar constructs in the actual interpreters or compilers. So you certainly can convert a recursive function to an iterative counterpart because that's how it's always done (if automatically). You'll just be duplicating the compiler's work in an ad-hoc and probably in a very ugly and inefficient manner.

Answer 5

It is possible to convert any recursive algorithm to a non-recursive one, but often the logic is much more complex and doing so requires the use of a stack. In fact, recursion itself uses a stack: the function stack.

More Details: https://developer.mozilla.org/en-US/docs/Web/JavaScript/Guide/Functions

Answer 6

Is it always possible to write a non-recursive form for every recursive function?

Yes. A simple formal proof is to show that both µ recursion and a non-recursive calculus such as GOTO are both Turing complete. Since all Turing complete calculi are strictly equivalent in their expressive power, all recursive functions can be implemented by the non-recursive Turing-complete calculus.

Unfortunately, I’m unable to find a good, formal definition of GOTO online so here’s one:

A GOTO program is a sequence of commands P executed on a register machine such that P is one of the following:

• HALT, which halts execution
• r = r + 1 where r is any register
• r = r – 1 where r is any register
• GOTO x where x is a label
• IF r ≠ 0 GOTO x where r is any register and x is a label
• A label, followed by any of the above commands.

However, the conversions between recursive and non-recursive functions isn’t always trivial (except by mindless manual re-implementation of the call stack).