(201) 767-8450 

 The point of this book is to provide a leisurely and perhaps even entertaining journey through recursion. It begins with the most basic of recursive algorithms and slowly guides the reader to more and more advanced applications. Most importantly, however, it is a unified treatment so that by the end of the book the reader will have learned that a sophisticated recursive algorithm to find the median in linear time has a great deal in common with a simple recursive algorithm to output an array. Once one learns to use the recursive paradigm it is easy to use and is often the correct way to go.

 Many people scoff at recursive algorithms claiming that they are too inefficient. Certainly many recursive algorithms can be retooled to an iterative form and be made to run faster by some factor that is typically small. But this is usually irrelevant. Who cares if the iterative implementation of an algorithm sorts an array with 1000 elements 10 milliseconds faster than the recursive one? For example, I wrote iterative and recursive functions to find factorials. Since very little is done inside the recursive function, the price we pay for using recursion will stand out. It turned out (at least on my computer and using my compiler) that the iterative version ran only 25% faster. I was able to calculate 15! 300 times in 100 seconds using the recursive function while it only took 75 seconds in the iterative case. Not much of a penalty in my mind. And this example was designed to make recursion look bad. In most cases the difference would be much less.

 This book takes great care to analyze the complexity of all of its algorithms and emphasizes the importance of this. After all, there is a big difference between a linear algorithm and an exponential one and, unfortunately, exponential behavior can creep into recursive algorithms quite unexpectedly. Inefficiency of this kind cannot be ignored. So, not only do we spend a lot of time discussing how to design recursive algorithms we learn how to analyze them as well.

 Owners of this book are likely to carry it around with them to many different classes. It will help them through their first exposure to recursion in CS 1. It will be a big help when the recursive crunch comes in CS 2. But most important, by reading this book they will become comfortable and proficient at recursive programming and this will prove helpful throughout a computer scientist's career, through school and beyond.