Recursion

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.

1. If the number is 3, 6, or 9 then it's divisible by three.
2. 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.

External links

• Unit on recursion in free online computer science course from MIT.