# Recursion

This is the current revision of Recursion as edited by NKeaton (Talk | contribs) at 09:23, 26 February 2013. This URL is a permanent link to this version of this page.

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

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

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