Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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?

share|improve this question

closed as too broad by gnat, MichaelT, jwenting, GlenH7, Dynamic May 7 at 23:38

There are either too many possible answers, or good answers would be too long for this format. Please add details to narrow the answer set or to isolate an issue that can be answered in a few paragraphs.If this question can be reworded to fit the rules in the help center, please edit the question.

1  
stackoverflow.com/questions/531668 –  BlackICE Dec 9 '10 at 19:04
add comment

5 Answers

up vote 6 down vote accepted

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.

share|improve this answer
    
I get it. So, what advantage would recursion have? Simplicity? –  OscarRyz Dec 9 '10 at 19:05
2  
@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
add comment

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.

share|improve this answer
7  
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
1  
But what if you can do that wrong thing really quick?! –  RationalGeek Dec 9 '10 at 19:39
    
@Mason: I think this (near-)quote is from Programming Pearls: "You know our text formatting software. It's got ten known bugs, and next week it will have ten different known bugs. It also runs really slowly. Would you prefer to have all the bugs fixed or it to run ten times faster?" –  David Thornley Dec 9 '10 at 20:14
1  
@jkohlhepp - I can solve any problem instantly. The answer is 0. –  Note to self - think of a name Dec 9 '10 at 20:16
2  
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
show 5 more comments

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();
}
share|improve this answer
1  
With a stack, as mentioned by other answers. –  NickC 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. –  NickC Dec 9 '10 at 20:33
add comment

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.

share|improve this answer
add comment

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!

share|improve this answer
add comment

Not the answer you're looking for? Browse other questions tagged or ask your own question.