---
tag: 0DSHAVH45F
kind: concept
name: Definition by recursion
aliases: [recursive-definition, inductive-definition]
msc: ["03E20"]
sources:
  - url: https://en.wikipedia.org/wiki/Recursive_definition
    locator: lead section
  - url: https://en.wikipedia.org/wiki/Recursive_definition
    locator: Principle of recursive definition
same_as:
  wikidata: Q2466486
  wikipedia: Recursive definition
---

## Summary

A definition by recursion defines a function on the [[natural numbers|0MWKJ44V5A]] in two parts.
It gives the value at $0$, and a rule that gives the value at $n + 1$ from the value at $n$.
The recursion theorem says that such a definition always gives exactly one function.
Precisely, let $X$ be a set, let $a$ be an element of $X$ and let $g \colon \mathbb{N} \times X \to X$ be a function.
Then there is exactly one function $f \colon \mathbb{N} \to X$ with $f(0) = a$ and $f(n + 1) = g(n, f(n))$ for each $n$ in $\mathbb{N}$.

## Remarks

The factorial is an example: $0! = 1$ and $(n + 1)! = (n + 1) \cdot n!$.
The [[addition|0W5DSDFQ4G]] and the [[multiplication|0JRC32D6K2]] of natural numbers have definitions by recursion.
The proof of the recursion theorem uses the [[principle of mathematical induction|0ASJVEFA9J]].

## Explanations

### L1 human

A recursive definition tells you where to start and how to take one step.
For the factorial, you start with $0! = 1$, and each step multiplies by the next number.
Step by step, this gives $1! = 1$, $2! = 2$, $3! = 6$ and $4! = 24$.