# Can all the recursive functions be coded with iterations? [closed]

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?

## closed as too broad by gnat, user40980, jwenting, GlenH7♦, DynamicMay 7 '14 at 23:38

Please edit the question to limit it to a specific problem with enough detail to identify an adequate answer. Avoid asking multiple distinct questions at once. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

## 5 Answers

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.

• I get it. So, what advantage would recursion have? Simplicity? – OscarRyz Dec 9 '10 at 19:05
• @OscarRyz: Yes, and it's more elegant. – Michael K Dec 9 '10 at 19:12
• @OscarRyz, the way I've described is recursion. It is just not done with native CPU-instructions. Doing it manually allows you to do things - like parallelization - which maps badly to native instructions. – user1249 Dec 9 '10 at 20:35

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.

• I'd say that right is always better than fast. Code that does the wrong thing very quickly isn't much good to anyone. – Mason Wheeler Dec 9 '10 at 19:30
• But what if you can do that wrong thing really quick?! – RationalGeek Dec 9 '10 at 19:39
• @jkohlhepp - I can solve any problem instantly. The answer is 0. – Note to self - think of a name Dec 9 '10 at 20:16
• Using recursion rather than an explicit stack can be more efficient - avoiding the need for heap allocations, possible memory fragmentation, and possible locality issues. However, on "right is normally better than fast", stack overflow in cases your software needs to handle means your code is broken. Usually, problem cases are fairly easy to spot - recursion on a (reasonably) balanced tree is fine, but recursion on a tree that may be very unbalanced, or on a linked list, can be a serious bug in a language like C. Worse, it may survive simple testing, and only crash when deployed for real. – Steve314 Dec 9 '10 at 23:59
• I think you all understand what Mason meant and are just making jokes for the fun of it. Of course a slow correct program is more useful than a fast incorrect program. – Giorgio Jun 17 '13 at 17:32

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.

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();
}
``````
• With a stack, as mentioned by other answers. – Nicole Dec 9 '10 at 19:12
• Yes, but how simple is that?-) – Joonas Pulakka Dec 9 '10 at 19:18
• Oh, recursion is definitely better. I thought you were saying it was not possible. – Nicole Dec 9 '10 at 20:33

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!