Recursion

Recursion is a method of defining objects or processes in terms of themselves, typically by specifying a base case and a rule for building new instances from existing ones.

Recursive Definitions

A recursive definition consists of:

1. Base case(s): Explicitly defined initial value(s)
2. Recursive step: A rule defining new values in terms of previously defined values

Examples

Factorial

$$ n! = \begin{cases} 1 & \text{if } n = 0 \\ n \cdot (n-1)! & \text{if } n > 0 \end{cases} $$

Fibonacci Sequence

$$ F_n = \begin{cases} 0 & \text{if } n = 0 \\ 1 & \text{if } n = 1 \\ F_{n-1} + F_{n-2} & \text{if } n > 1 \end{cases} $$

Recursive Set Construction

The Cantor_set is defined recursively:

• $C_0 = [0, 1]$
• $C_{n+1}$ is obtained by removing the open middle third of each interval in $C_n$
• $C = \bigcap_{n=0}^{\infty} C_n$

Principle of Recursion

The validity of recursive definitions on $\mathbb{N}$ is guaranteed by the Recursion Theorem, which follows from the Peano axioms and the well-ordering of the natural numbers.

Related

• Cantor_set
• sequence