再帰
集合論において、これは再帰的定義がなされた関数が存在することを保証する定理である。集合 Xと、Xの要素 aと、関数f: X → Xが与えられた場合に、任意の自然数nについて
F ( 0 ) = a {\displaystyle F(0)=a}
F ( n + 1 ) = f ( F ( n ) ) {\displaystyle F(n+1)=f(F(n))}
となるような一意な関数 F : N → X {\displaystyle F:\mathbb {N} \to X} (where N {\displaystyle \mathbb {N} } が存在する、と同定理は述べている(ここでの N {\displaystyle \mathbb {N} } は、ゼロを含む自然数の集合を示す)。
基底1として F i b ( 0 ) = 0 {\displaystyle Fib(0)=0} ,
基底2として F i b ( 1 ) = 1 {\displaystyle Fib(1)=1} ,
n > 1 {\displaystyle n>1} のあらゆる整数について F i b ( n ) = F i b ( n − 1 ) + F i b ( n − 2 ) {\displaystyle Fib(n)=Fib(n-1)+Fib(n-2)} .
多くの数学的公理は、再帰を用いた法則に基づいている。例えば、ペアノ公理による自然数の正式な定義は「ゼロは自然数であり、各自然数には後続数があり、これも自然数である」と記述されうる。この基底段階および再帰を用いた法則によって、全ての自然数の集合を生成できる。
他にも再帰を用いて定義されている数学的対象としては、関数の漸化式、集合のカントール集合、フラクタル分野、プログラミング言語における階乗、などがある。