bounded recursion
In this entry, the following notations are used:
$\mathcal{F}=\bigcup \{{F}_{k}\mid k\in \mathbb{N}\}$, where for each $k\in \mathbb{N}$, and ${F}_{k}=\{f\mid f:{\mathbb{N}}^{k}\to \mathbb{N}\}$.
Definition. A function^{} $f\in {F}_{m+1}$ is said to be defined by bounded recursion via functions $g\in {F}_{m}$, $h\in {F}_{m+2}$, and $k\in {F}_{m+1}$ if, for any $\bm{x}\in {\mathbb{N}}^{m}$ and $y\in \mathbb{N}$,

1.
$f$ is defined by primitive recursion via $g$ and $h$:

–
$f(\bm{x},0)=g(\bm{x})$,

–
$f(\bm{x},y+1)=h(\bm{x},y,f(\bm{x},y))$;

–

2.
$f$ is bounded from above by $k$:

–
$f(\bm{x},y)\le k(\bm{x},y)$.

–
Clearly, a function that is defined by bounded recursion is defined by primitive recursion. Conversely, a function is defined by primitive recursion, it is also defined by bounded recursion, since it is bounded by itself. However, the two concepts are not exactly the same. To make this precise, we first define what it means for a set of numbertheoretic functions be closed under bounded recursion:
Definition. A set $\mathcal{B}\subseteq \mathcal{F}$ is said to be closed under bounded recursion if, for any $f$ defined by bounded recursion via $g,h,k\in \mathcal{B}$, then $f\in \mathcal{B}$.
It is clear that $\mathcal{F}$ is closed under both primitive recursion and bounded recursion, and so are $\mathcal{P}\mathcal{R}$, the set of all primitive recursive functions^{}, as well as $\mathcal{R}\cap \mathcal{F}$, the set of all total recursive functions. However,
Proposition 1.
The set $\mathrm{E}\mathit{}\mathrm{R}$ of all elementary recursive functions is closed under bounded recursion, but not primitive recursion.
Since the exponential function^{}, the $i$th prime function, and the function ${(x)}_{y}$ (the exponent^{} of $y$ in $x$) are elementary recursive, we have the following corollary:
Corollary 1.
If $f$ is defined by courseofvalues recursion via an elementary recursive function $h$, and $f$ is bounded from above by an elementary recursive function $k$, then $f$ is elementary recursive.
Title  bounded recursion 

Canonical name  BoundedRecursion 
Date of creation  20130322 19:07:01 
Last modified on  20130322 19:07:01 
Owner  CWoo (3771) 
Last modified by  CWoo (3771) 
Numerical id  5 
Author  CWoo (3771) 
Entry type  Definition 
Classification  msc 03D20 
Synonym  bounded primitive recursion 
Related topic  ElementaryRecursiveFunction 