In mathematics, recursion describes a situation where a function's output is plugged back into it. If we have a function \(f(x)\), we can recurse it to form functions \(f(f(x))\), \(f(f(f(x)))\), etc. \(f(f(\ldots f(f(x))\ldots ))\) with \(t\) copies of \(f\) is often abbreviated \(f^t(x)\). Recursion is very important to googology since it easily produces quickly-growing functions. If \(f(x)\) displays rapid growth, \(f^t(x)\) will grow much faster for large \(t\).
Every primitive recursive function breaks into two types of rules: base case, where for some argument value is given immediately, and recursive rule, where function applies for itself.
A recursive hierarchy of functions must have three rules: "brake" rule (starting function), "plugging" rule (it tells how many times the previous function must be plugged) and "decomposing" rule (for diagonalizing purposes, it finds the fundamental sequences of so-called limit ordinals).
Examples of recursive hierarchies are FGH, HAN, Hyper-E Notation and Bird's array notation.
See also[]
Bignum Bakeoff contestants: pete-3.c · pete-9.c · pete-8.c · harper.c · ioannis.c · chan-2.c · chan-3.c · pete-4.c · chan.c · pete-5.c · pete-6.c · pete-7.c · marxen.c · loader.c
Channel systems: lossy channel system · priority channel system
Concepts: Recursion