This week's giveaway is in the Java/Jakarta EE forum. We're giving away four copies of Java EE 8 High Performance and have Romain Manni-Bucau on-line! See When you do a recursion, you repeatedly invoke a method (usually the same method), usually in very rapid succession at points. When ever you call a method, two things happen. First a next frame is added to the call stack, allocating appropriate memory. Second time it taken to set up the frame. If make 1000 calls and your recursion goes up to 10 levels, you've created 1000 frames and the size of the stack capped at C + 10F, where C was the size of the stack before the recursive call and F is the size of each frame. For very complex problems (or if you get the base case wrong), the size of the stack, C+NF, where N is the depth of the recrusion, may exceed the stack size, in which case you get a stack overflow error. In some cases you can do tail-recursion, in which you can, instead of recursion, use a loop. In this case its far more efficent, because you don't have the overhead of method calls. In general, don't fear recursion. --Mark
I agree with Mark. There is a slight performance penalty associated with recursion, but in most programs it will turn out to be insignificant compared to, say, time spent waiting for a response from a database, or doing I/O across a network, or, heck, even creating a String object or two on each iteration of a loop. Even if you're not doing any of these things (or other comparable tasks) the performance difference is generally pretty minor. Readability and maintainability are far more important concerns. Now having said that, it seems that there are people out there who find recursive solutions harder to understand, and therefore avoid them. And there are others (like me) who will almost always think of a recursive solution before an iterative one (for certain types of problems at least), and find it a bit difficult to understand the reasoning behind the iterative solution. So different people have different opinions about what's more "readable". I think if you fit in one of these groups, it's beneficial to you as a programmer to spend some time forcing yourself to convert a few solutions from recursion to iteration, or vice versa. That is, try out the one you don't like or understand as well, and see if you can't learn to appreciate it more. Both styles can be useful to you, and are important tools in a programmer's toolkit.
Let's look at what happens when we want to calculate the 5th fibonacci number. When we call fib(5), it in turn calls fib(4) and fib(3). The call to fib(4) calls fib(3) and fib(2). Notice that just at this level fib(3) has to be completely calculated twice. Each call to fib(3) then calls fib(2) and fib(1). That means fib(2) has been called a total of three times. Final fib(2) calls fib(1) and fib(0). This comes to a total of 5 calls to fib(1) and 4 calls to fib(0)! (You can see this more easily if you draw a tree with each function call as a branch. I didn't want to take the time to figure out how to do it with text art, so I'll leave it as the proverbial exercise for the reader.) Even fib(6) or fib(7) will increase the number of calls to fib(1) and fib(0) significantly. Calculating fib(10) will be even worse, and I doubt you would be willing to wait long enough to calculate anything larger than fib(15) using this recursive method. (Try it and see how long it takes!) The moral of the story here is that the benefits of a recursive solution can be easily undermined when the problem uses multiple recursive calls at each level. Recently I wrote a program to solve a puzzle where each calculation relied on 4 previous calculations! Can you imagine the amount of duplication there? Needless to say, it didn't take long for a pure recursive solution to fall to its knees. I hope you don't take this the wrong way. I am not saying recursion is bad. In fact, I am much like Jim in that I usually think of a recursive solution first. I find them much more readable. However, the Fibonacci sequence is just an example of when recurssion isn't the best idea. I think of recurssion as a tool. Just like any tool you need to know when to use it and when NOT to use it. you should understand its strengths and weaknesses. [ May 21, 2003: Message edited by: Layne Lund ]
Good point. I think it might be safe to say that alarm bells should go off in your brain the moment you see a method that invokes itself more than once from within its own body. Unless these invocations are on mutally exclusive sides of an if/else I suppose.
I usually prefer an iterative solution (I just usually can visualize it better) but as for performance, let's not foget that the fastest sorting algorithm is quicksort which is recursive. Some problems simply lend themselves well to recursion, like simple combination and permutaion calculations. Others are more difficult to see for programmers like myself.
Any intelligent fool can make things bigger, more complex, and more violent. It takes a touch of genius - and a lot of courage - to move in the opposite direction. - Ernst F. Schumacher