Recursion is a word from mathematics. In mathematics and in computer science, it is used to define a thing, usually a function. Unlike with normal definitions, the function to be defined can be used to define itself.
Recursion consists of two steps:
- Are we done yet? If so, return the results. Without this step, a recursion would go on forever.
- If not, recurse: simplify the problem, solve the simpler problem(s), and assemble the results into a solution for the original problem. Then return that solution.
An example might be how to define ancestor, using recursion:
- A person's parents are his or her ancestors (base hypothesis).
- The ancestors of a person's ancestors are also ancestors of the person being considered (recursion step).