Can all the recursive functions be coded with iterations?

Question

What are the advantages of recursion?

Some programming languages can optimize tail recursion, but, still in general terms, recursion consume more resources than regular loops.

Is it possible to have an iterative version of some recursive function?

Answer 1

Recursion is often a more natural way of looking at things than iteration. For example, consider inorder traversal of a binary tree: inorder(left); process(); inorder(right); is a lot simpler than explicitly maintaining a stack.

As long as you don't go too deep (blowing the stack), the difference in resource use is usually trivial. Don't worry about it in general. Simple code is normally better than hand-optimized code, although there are exceptions. Right is normally better than fast.

Any recursive algorithm can be expressed as an iterative algorithm, but you may need to keep an explicit stack (corresponding to the call stack that's handled implicitly). After all, if you compile a recursive function, you get something that relies on manipulating a stack and looping through the function, and that's iterative.

Tail-recursive functions can be easily translated into loops, and don't need a stack, but that's a special case.

Answer 2

Yes, you can code recursive functions as iterations. It basically requires you to maintain the information manually that otherwise would have been taken care of by the method calling code generated by the compiler.

In other words, you need a stack where each entry is a structure containing the passed parameters and all the local variables. You always work on the top-most entry on the stack. If you need to call yourself, create a new entry and put on top of the stack. When done take the topmost entry of the stack exposing the one below, and use the previously topmost entry to extract the return values and update the new topmost entry accordingly.

I suggest you study a compiler book to see how this is usually implemented in machine code.

Answer 3

What are the advantages of recursion?

Simplicity. Without tail-call optimization it of course takes more resources (stack), but how would you implement, say, deltree in Java without recursion? The twist is that delete() can delete directories only if they're empty; here's it with recursion:

deltree(File fileOrDirectory) {
    if (fileOrDirectory.isDirectory()) {
        for (File subFileOrDirectory : fileOrDirectory.listFiles()) {
            deltree(subFileOrDirectory);
        }
    }
    fileOrDirectory.delete();
}

Answer 4

What are the advantages of recursion?

Try solving the Towers of Hanoi problem iteratively. Once you give up, take a look at the iterative solution and compare it to the recursive one. Which one is simpler?

Is it possible to have an iterative version of some recursive function?

Yes, in principle. However for many problems, including very common tasks, such as tree traversals, the recursive solutions are much simpler and more elegant than the iterative ones.

Answer 5

I believe that recursion is one of those tools that a programmer must have to live. With recursion you can "think" your algorithms and solve them just the way you thought about it. But, I must warn you, everybody is talking about how pretty recursion is and how much simplicity brings to the code, regarding that I have a few things to say:

1. First of all, thinking the "recursive way" of an algorithm is not easy. Building a function like a factorial(n!) or something like Hanoi Towers is just the tip of the iceberg, and reaching the bottom requires a looong time.
2. Don't think that recursion brings simplicity only into your code, sometimes, the iterative way is ugly and messy, but is cost effective (look into the recursive solution of the Fibonacci problem)

Having those things in mind, learn recursion! it's funny, complex and it will smash your brain!, but you'll find yourself loving it.

Best of luck!