Introduction to Recursion
Recursion is a powerful tool for solving certain kinds of problems. Recursion breaks a problem into smaller problems that are identical to the original, in such a way that solving the smaller problems provides a solution to the larger one. Recursion can be used to solve a wide range of problems, and hence it is a fundamental concept in computer science. This book will introduce you to recursion with several examples written in Java/C++ styled languages.
The power of recursion evidently lies in the possibility of defining an infinite set of objects by a finite statement. In the same manner, an infinite number of computations can be described by a finite recursive program, even if this program contains no explicit repetitions. — Niklaus Wirth, Algorithms + Data Structures = Programs, 1976
It can be used to define mathematical functions, languages and sets, and algorithms or programming language functions. It has been established that these are essentially equivalent in the following sense: the set of all functions that can be computed by algorithms, given some reasonable notion of what an algorithm is, is the same as the set of all functions that can be defined recursively, and each set (or language) for which membership can be determined by an algorithm corresponds to a function that can be defined recursively.
Recursion Explained - Simplify and Delegate
Recursion can be described loosely as follows:
- If the given instance of the problem can be solved directly, solve it directly.
- Otherwise, reduce it to one or more simpler instances of the same problem.
If the self-reference is confusing, it may be helpful to imagine that someone else is going to solve the simpler problem, magically. Your only task is to simplify the original problem, or to solve it directly when simplification is either unnecessary or impossible; the recursion magic will solve all the simpler subproblems for you.
There is one mild technical condition that must be satisfied in order for any recursive method to work correctly: There must be no infinite sequence of reductions to simpler and simpler instances. Eventually, the recursive reductions must lead to an elementary base case that can be solved by some other method; otherwise, the recursive algorithm will loop forever. The most common way to satisfy this condition is to reduce to one or more smaller instances of the same problem. We’ll see how this is used in several examples in the later chapters of this book.