CODEWITHSUNDEEP
recursioniterationcomputer-science
bodacydo
bodacydo

Reputation: 79319

Can every recursive function be rewritten as an iterative function?

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.

Upvotes: 3

Views: 1302

Answers (2)

anumi
anumi

Reputation: 3947

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.

Upvotes: 0

&#211;scar L&#243;pez
&#211;scar L&#243;pez

Reputation: 236004

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.

Upvotes: 2

Related Questions