Recursive call or loop

It should come as no surprise to you that you can write any recursive call with a " for " or a " while " loop. So why would you consider writing code that makes recursive calls?

Advertisement:

The first answer to this question usually comes in the form of a statement of surprise from many programmers I talk to. " I did not even know there was any other way to do this . . . "

The first rule to consider is that if a problem can be solved effectively and quickly using loop constructs then that should be your first choice. For most algorithms loops are easier and quicker to write and are a natural component of your programming arsenal. Before you start thinking about moving a loop to a recursive call rather explore tightening the loop, make it more efficient.

Recursive method calls or algorithms, however, often offer us a natural and elegant way of dealing with a complex problem, and this is the reason I brought the subject up over the past few weeks. We are going to look at some data structures that can be elegantly manipulated with recursive algorithms.

You will find that many algorithms are inherently recursive and those may be better coded with recursion than loops. Keeping the method and the size of the data structure that is being worked on small is very important. This is because recursive calls tend to impact the call stack, especially when the dataset explodes.

A good example (or a bad example depending on how you look at) of such a case is processing the Fibonacci series:

fibonacci(0) = 0

fibonacci(1) = 1

fibonacci(n) = fibonacci(n-1) + fibonacci(n - 2)

Processing Fibonacci 20 results in 21,891 calls, but processing Fibonacci 30 quickly racks up more than seven million recursive calls - clearly if you keep going you'll send the call stack into oblivion.

Next issue I'll provide a list of specific tips for using recursion as we prepare to get our hands a little green pruning trees and similar data structures.

 

Jeffrey Shapiro is a software development expert and well-known author. He has written several books, which include the widely acclaimed Computer Telephony Strategies, by Hungry Minds, and Visual Basic .NET Headstart by Osborne/McGraw-Hill. You can reach him by e-mail at java-pro@mcity.org.