Recursive function be converted into a non-recursive function

Question

Possible Duplicate:
Can every recursion be converted into iteration?

Can always or which cases a recursive function be converted into a non-recursive function or set of non-recursive functions?

Can you point me to examples which work and do not work?

Thanks

Answer 1

This is always possible, because you can emulate the call stack yourself. However, it's not always easy to do.

The easy cases are tail recursion: these don't even require a stack. For example, this guy is trivially converted into a for loop:

def countdown(n):
    if n >= 0:
        print n
        countdown(n-1)

Even if the function is not strictly tail-recursive, you can sometimes still get away without a stack. For example, the classical factorial function:

def factorial(n):
    if n <= 1:
        return 1
    else:
        return n * factorial(n-1)

It gets harder when there are multiple recursive calls. Consider, for example, quicksort:

def quicksort(array):
    if len(array) <= 1:
        return array
    else:
        pivot = array[0]
        left = quicksort([x for x in array[1:] if x < pivot])
        right = quicksort([x for x in array[1:] if x >= pivot])
        return left + [pivot] + right

Although it's definitely possible to do this without recursion, you'll have to build a stack yourself, and construct a while loop that iterates until the stack is empty.

Answer 2

Yes, it's always possible to convert a recursive function into a non-recursive one.

You can prove this with a simple thought experiment: you can implement a simple non-recursive interpreter which emulates a Turing-complete register machine with a stack (basically the equivalent of a simple microprocessor). This is then a non-recursive piece of code that can run any recursive function.

Note that in all non-trivial cases of recursion (i.e. more complex than simple tail recursion which can just be converted into a loop), you will need to somehow capture the information contained in nested stack frames. In general, this can be done by emulating a variable-sized stack using heap memory, but it's also possible to use other techniques (e.g. continuations or queues).

Answer 3

It's always possible to turn recursion into iteration using a stack. Instead of making a recursive call with some parameters, you push the set of parameters on the stack. In each iteration, the top set of parameters is popped and handled.

Answer 4

All recursion functions can be converted to iteration functions, however it is not that simple.

It is only simple in the case of tail recursion. This is when only one recursion call happens and it happens at the end. This can be simply converted to a do-while statement.

For other cases it isn't that simple. While it is true that all recursion can be turned to iteration you will need to simulate your own stack in the more complex examples.

Answer 5

Yes every Recursive function can be converted to an iterative function.