Recursion is the repeated application of a procedure or definition.
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.
Recursion in language enables phrases to be embedded within one another, usually through conjunctions, such that it should be possible to make an infinitely long sentence. For one such example we could take the sentence Many atheists are overweight and precede it with <person> said that indefinitely, as follows: Blaine said that Barbie said that Ken said that many atheists are overweight.