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++.

16. Glossary

base case

A branch of the conditional statement in a recursive function that does not give rise to further recursive calls.

data structure

An organization of data for the purpose of making it easier to use.

dynamic programming

a way to solve complex problems by breaking it up, solving the smaller portions, and storing the results to avoid re-calculating them.

exception

An error that occurs at runtime.

handle an exception

To prevent an exception from terminating a program by wrapping the block of code in a try / except construct.

immutable data type

A data type which cannot be modified. Assignments to elements or slices of immutable types cause a runtime error.

infinite recursion

A function that calls itself recursively without ever reaching the base case. Eventually, an infinite recursion causes a runtime error.

mutable data type

A data type which can be modified. All mutable types are compound types. Lists and dictionaries (see next chapter) are mutable data types; strings and tuples are not.

raise

To cause an exception by using the raise statement.

recursion

The process of calling the function that is already executing.

recursive call

The statement that calls an already executing function. Recursion can even be indirect ­– function f can call g which calls h, and h could make a call back to f.

recursive definition

A definition which defines something in terms of itself. To be useful it must include base cases which are not recursive. In this way it differs from a circular definition. Recursive definitions often provide an elegant way to express complex data structures.

stack frame

a stack that contains a "frame" or group of data. For a call stack, this would be a function and its arguments.

tuple

A data type that contains a sequence of elements of any type, like a list, but is immutable. Tuples can be used wherever an immutable type is required, such as a key in a dictionary (see next chapter).

tuple assignment

An assignment to all of the elements in a tuple using a single assignment statement. Tuple assignment occurs in parallel rather than in sequence, making it useful for swapping values.