TOPICS
Search

Recursive Function


The term "recursive function" is often used informally to describe any function that is defined with recursion. There are several formal counterparts to this informal definition, many of which only differ in trivial respects.

Kleene (1952) defines a "partial recursive function" of nonnegative integers to be any function f that is defined by a noncontradictory system of equations whose left and right sides are composed from (1) function symbols (for example, f, g, h, etc.), (2) variables for nonnegative integers (for example, x, y, z, etc.), (3) the constant 0, and (4) the successor function S(x)=x+1.

For example,

f(x,0)=0
(1)
f(x,S(y))=g(f(x,y),x)
(2)
g(x,0)=x
(3)
g(x,S(y))=S(g(x,y))
(4)

defines f(x,y) to be the function xy that computes the product of x and y.

Note that the equations might not uniquely determine the value of f for every possible input, and in that sense the definition is "partial." If the system of equations determines the value of f for every input, then the definition is said to be "total." When the term "recursive function" is used alone, it is usually implicit that "total recursive function" is intended. Note that some authors use the term "general recursive function to mean partial recursive function, although others use it to mean "total recursive function."

The set of functions that can be defined recursively in this manner is known to be equivalent to the set of functions computed by Turing machines and by the lambda calculus.

RecursiveFunctionCausalGraph

Wolfram (2023) discusses the multicomputation of nestedly recursive functions via their causal graphs. For example, the illustration above shows the causal graph of the nested recursive function

 f(n)={f(n-f(n-3))+f(n-2)   for n>3; 1   otherwise.
(5)

This graph has both spacelike and timelike structure (Wolfram 2023).


See also

Church-Turing Thesis, General Recursive Function, Primitive Recursive Function, Recursively Undecidable, Turing Machine

This entry contributed by Matthew Szudzik

Explore with Wolfram|Alpha

References

Kleene, S. C. Introduction to Metamathematics. Princeton, NJ: Van Nostrand, 1952.Odifreddi, P. In Combinatorics, Computability and Logic (Ed. C. S. Calude, M. J. Dinneen, and S. Sburlan). London: Springer-Verlag, 2001.Péter, R. Rekursive Funktionen in der Komputer-Theorie. Budapest: Akad. Kiado, 1951.Rogers, H. Theory of Recursive Functions and Effective Computability. Cambridge, MA: MIT Press, 1987.Schnorr, C. P. Rekursive Funktionen und ihre Komplexität. Stuttgart, Germany: Teubner, 1974.Wolfram, S. A New Kind of Science. Champaign, IL: Wolfram Media, p. 907, 2002.Wolfram, S. "Expression Evaluation and Fundamental Physics." Sep. 29, 2023. https://writings.stephenwolfram.com/2023/09/expression-evaluation-and-fundamental-physics/.

Referenced on Wolfram|Alpha

Recursive Function

Cite this as:

Szudzik, Matthew. "Recursive Function." From MathWorld--A Wolfram Web Resource, created by Eric W. Weisstein. https://mathworld.wolfram.com/RecursiveFunction.html

Subject classifications