**Recursion** is the repeated application of a procedure or definition through reference to itself.

## In Mathematics

There's a simple procedure for finding out whether a number is divisible by three.

- If the number is 3, 6, or 9 then it's divisible by three.
- Otherwise, add all the digits of the number; if the sum of the digits is divisible by three, then so is the original number.

Examples:

- 12 => 1 + 2 = 3 (yes)
- 14 => 1 + 4 = 5 (no)
- 96 => 9 + 6 = 15; 15 => 1 + 5 = 6

## In Computing

Recursion is a technique whereby a function, in order to accomplish a task, calls itself to accomplish part of the task.

Every recursive solution involves two major parts or cases, the second part having three components:

- base case(s), in which the problem is simple enough to be solved directly, and
- recursive case(s). A recursive case has three components:

- 1. divide the problem into one or more simpler or smaller parts of the problem,
- 2. call the function (recursively) on each part, and
- 3. combine the solutions of the parts into a solution for the problem.

These exercises are useful to see examples of recursion:

- 1. Write a function to compute the sum of all numbers from 1 to n.
- 2. Write a function to compute 2 to the power of a non-negative integer.
- 3. Write a function to compute any number to the power of a non-negative integer.