Recursion

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.