Recursion - Formal Definitions of Recursion

Formal Definitions of Recursion

In mathematics and computer science, a class of objects or methods exhibit recursive behavior when they can be defined by two properties:

1. A simple base case (or cases), and
2. A set of rules which reduce all other cases toward the base case.

For example, the following is a recursive definition of a person's ancestors:

• One's parents are one's ancestors (base case).
• The parents of one's ancestors are also one's ancestors (recursion step).

The Fibonacci sequence is a classic example of recursion:

• Fib(0) is 0
• Fib(1) is 1
• For all integers n > 1: Fib(n) is (Fib(n-1) + Fib(n-2))

Many mathematical axioms are based upon recursive rules. For example, the formal definition of the natural numbers in set theory follows: 1 is a natural number, and each natural number has a successor, which is also a natural number. By this base case and recursive rule, one can generate the set of all natural numbers

A more humorous illustration goes: "To understand recursion, you must first understand recursion." Or perhaps more accurate is the following, from Andrew Plotkin: "If you already know what recursion is, just remember the answer. Otherwise, find someone who is standing closer to Douglas Hofstadter than you are; then ask him or her what recursion is."

Recursively defined mathematical objects include functions, sets, and especially fractals.