Siguiente: Esquema de recursión acotada Un nivel arriba: Propiedades de cerradura de Anterior: Esquema de minimización acotada

Esquema de recursión

Una típica aplicación de este esquema define a una función f haciendo

La función g está definiendo el caso ``base'' de la recurrencia, en tanto que la función h define precisamente el recurrente. En h, puede también ocurrir y como un argumento. Así pues, este esquema se aplica sobre dos funciones, la primera correspondiente al caso ``base'' con n-1 argumentos y la segunda correspondiente al caso recurrente con n+1 argumentos, y produce una función con n argumentos,

Más precisamente: Si $g:I\!\!N^{n-1}\rightarrow N$ y $h:I\!\!N^{n+1}\rightarrow N$ son dos funciones definimos

$$\begin{eqnarray*}f:I\!\!N^n &\rightarrow& I\!\!N\\ (\mbox{\bf x},y) &\mapsto& f(\mbox{\bf x},y) \end{eqnarray*}$$

donde

$$\begin{array}{lrcl} \mbox{\it Caso base}:& f(\mbox{\bf x},0)... ...f x},y+1) &=& h(\mbox{\bf x},y,f(\mbox{\bf x},y)) \end{array}$$

Así pues, $\mbox{\it Recu}(g;h)=f.$