Introduction to the Art of Programming Using Scala

Chapter 15

Recursion

Back in chapter 6 we got our first introduction to recursion. At that point we used recursion to provide iteration. In chapter 8 we learned how to produce iteration using loops and have used that more than recursion since that point. If the only capability of recursion was to produce iteration it would not be of much interest in Computer Science because loops would be a complete substitute that would have simpler syntax for most uses. However, that is not the case. Recursion allows us to express a lot more than just simple iteration, and because of this, recursion is a critical tool in writing concise solutions to many different problems.

15.1 Power of Recursion

To understand the real power of recursion and where it comes ...