Recursion in C++

The principles of recursion are the same, regardless of the language used for implementation. This chapter views the topic through the lens of C++. There are a fair number of examples and visualizations. Read through these at a minimum. You might find the exercises useful since the application of a principle is an aid to your understanding. Read Chapter 5 in this book on C++.

13. Summary

In this chapter we have looked at examples of several recursive algorithms. These algorithms were chosen to expose you to several different problems where recursion is an effective problem-solving technique. The key points to remember from this chapter are as follows:

  • All recursive algorithms must have a base case.

  • A recursive algorithm must change its state and make progress toward the base case.

  • A recursive algorithm must call itself (recursively).

  • Recursion can take the place of iteration in some cases.

  • Recursive algorithms often map very naturally to a formal expression of the problem you are trying to solve.

  • Recursion is not always the answer. Sometimes a recursive solution may be more computationally expensive than an alternative algorithm.