Can every recursive function be rewritten as an iterative function?

Question

I've had this question on my mind for a really long time but I can't figure out the answer. The question is, if does every recursive function have an iterative function that does the same?

For example,

factorial(n) {
    if (n==1) { return 1 }
    else      { return factorial(n-1) }
}

This can be easily rewritten iteratively:

factorial(n) {
    result = 1;
    for (i=1; i<=n; i++) {
        result *= i
    }
    return result
}

But there are many other, more complicated recursive functions, so I don't know the answer in general. This might also be a theoretical computer science question.

possible duplicate of [Can every recursion be converted into iteration?](http://stackoverflow.com/questions/931762/can-every-recursion-be-converted-into-iteration) — Sylwester, Sep 06 '13 at 16:59

score 2 · Answer 1 · edited May 23 '17 at 11:43

Yes, a recursive function can always be written as an iteration, from a theoretical point of view - this has been discussed before. Quoting from the linked post:

Because you can build a Turing complete language using strictly iterative structures and a Turning complete language using only recursive structures, then the two are therefore equivalent.

Explaining a bit: we know that any computable problem can be solved by a Turing machine. And it's possible to construct a programming language A without recursion, that is equivalent to a Turing machine. Similarly, it's possible to build a programming language B without iteration, equal in computational power to a Turing machine.

Therefore, if both A and B are Turing-complete we can conclude that for any iterative program there must exist an equivalent recursive program, and vice versa. This is a theoretical result, in the sense that it doesn't give you any hints on how to derive one recursive program from an arbitrary iterative program, or vice versa.

score 0 · Answer 2 · answered Sep 10 '13 at 18:18

0

Without going to theory, it is easy to convince oneself that any recursive function can have an iterative equivalent by observing that processors (such as Pentium) just run iteratively.

answered Sep 10 '13 at 18:18

anumi

3,869
2
22
22

Can every recursive function be rewritten as an iterative function?

2 Answers2