Physics Library
 An open source physics library
Encyclopedia | Forums | Docs | Random | Template Test |  
Login
create new user
Username:
Password:
forget your password?
Main Menu
Sections

Talkback

Downloads

Information
Recursive Function (Definition)

Intuitively, a recursive function may be defined as an integer-valued function of one or more integer variables which may be computed by a definite algorithm. In order to produce a rigorous definition, one may proceed long at least two approaches; one may define the notion of algorithm rigorously in order to complete the intuitive definition given above or one may proceed inductively, first declaring certain functions to be recursive and then specifying definite procedures by which one may construct any other recursive function starting from the initial set. In this entry, we shall concentrate on the latter approach, only making a few brief remarks regarding the former approach towards the end.

  1. The constant function $c: \mathbb{Z}_+ \to \mathbb{Z}_+$ defined by $c(x) = 1$ for all $x \in \mathbb{Z}_+$ is a recursive function.
  2. The addition function $+: \mathbb{Z}_+^2 \to \mathbb{Z}_+$ and the multiplication function $\times: \mathbb{Z}_+^2 \to \mathbb{Z}_+$ are recursive function.
  3. The projection functions $I^n_m \colon \mathbb{Z}_+^n \to \mathbb{Z}_+$ with $1 \le m \le n$ defined as $I^n_m (x_1, \ldots, x_n) = x_m$ are recursive functions.
  4. (Closure under composition) If $f \colon \mathbb{Z}_+^n \to \mathbb{Z}_+$ is a recursive function and $g_i \colon \mathbb{Z}_+^m \to \mathbb{Z}_+$ with $i = 1, \ldots n$ are recursive functions, then $h \colon \mathbb{Z}_+^n \to \mathbb{Z}_+$, defined by $h(x_1, \ldots, x_n) = f(g_1(x_1, \ldots, x_m), \ldots, g_n(x_1, \ldots, x_m))$ is a recursive function.
  5. (Closure under primitive recursion)If $f \colon \mathbb{Z}_+^n \to \mathbb{Z}_+$ and $g \colon \mathbb{Z}_+^{n+2} \to \mathbb{Z}_+$ are recursive function, then $h \colon \mathbb{Z}_+^{n+1} \to \mathbb{Z}_+$, defined by the recursion

    $\displaystyle h(n+1,x_1,\ldots,x_{k}) = g(h(n,x_1,\ldots,x_k),n,x_1,\ldots, x_k)$
    with the initial condition

    $\displaystyle h(0,x_1,\ldots,x_k) = f(x_1,\ldots,x_k)$
    is a recursive function.
  6. (Closure under minimization) If $f \colon \mathbb{Z}_+^{n+1} \to \mathbb{Z}_+$ is a recursive function then $g \colon \mathbb{Z}_+^n \to \mathbb{Z}_+$ is a recursive function, where $g$ is defined to equal $y$ if there exists a $y \in \mathbb{Z}_+$ such that
    • $f(0, x_1, \ldots, x_n), f(1, x_1, \ldots, x_n), \ldots, f(y, x_1, \ldots, x_n)$ are all defined,
    • $f(z, x_1, \ldots, x_n) = 0$ when $1 \le z <y$, and
    • $f(y, x_1, \ldots, x_n) = 0$, otherwise $g(x_1, \ldots, x_n)$ is undefined.



"Recursive Function" is owned by rspuzio. [ full author list (2) ]

View style:


Cross-references: composition, algorithm, function

This is version 2 of Recursive Function, born on 2009-03-09, modified 2009-05-22.
Object id is 581, canonical name is RecursiveFunction2.
Accessed 397 times total.

Classification:
Physics Classification: 00. (GENERAL)
 02. (Mathematical methods in physics)
Pending Errata and Addenda
None.
Discussion
Style: Expand: Order:

No messages.

Testing some escape charachters for html category with a generator has an injective cogenerator" now escape ” with "