The idea behind recursion

In computer science, a methods or function exhibits recursive behaviour when they can be defined by two properties: (1) a simple base case with a terminating scenario that does not use recursion to produce an answer. (2) A set of rules that reduce all other cases toward the base case (recursion).

For example, the following is a recursive definition of a person's ancestors: Base case: one's parents are one's ancestors. Recursion step: the ancestors of one's ancestors are also one's ancestors.

Another example is a recursive definition of natural numbers: Base case: 0 is a natural number. Recursion step: if n is a natural number, then n + 1 is a natural number.

Another example is visual recursion, also so-called the Droste-effect. Here an image contains a smaller version of itself.

The exercises on the following pages are examples of cases in which a recursive approach simplifies solving a computational task.