TOPICS
Search

Recursion


A recursive process is one in which objects are defined in terms of other objects of the same type. Using some sort of recurrence relation, the entire class of objects can then be built up from a few initial values and a small number of rules. The Fibonacci numbers are most commonly defined recursively. Care, however, must be taken to avoid self-recursion, in which an object is defined in terms of itself, leading to an infinite nesting.


See also

Ackermann Function, Kleene's Recursion Theorem, McCarthy 91-Function, Primitive Recursive Function, Recurrence Relation, Recursive Function, Recursively Undecidable, Regression, Richardson's Theorem, Self-Recursion, Self-Similarity, TAK Function

Explore with Wolfram|Alpha

References

Buck, R. C. "Mathematical Induction and Recursive Definitions." Amer. Math. Monthly 70, 128-135, 1963.Gardner, M. "Infinite Regress." Ch. 22 in The Sixth Book of Mathematical Games from Scientific American. Chicago, IL: University of Chicago Press, pp. 220-229, 1984.Hofstadter, D. R. "Lisp: Lists and Recursion" and "Lisp: Recursion and Generality." Chs. 18-19 in Metamagical Themas: Questing of Mind and Pattern. New York: BasicBooks, pp. 410-454, 1985.Knuth, D. E. "Textbook Examples of Recursion." In Artificial Intelligence and Mathematical Theory of Computation, Papers in Honor of John McCarthy (Ed. V. Lifschitz). Boston, MA: Academic Press, pp. 207-229, 1991.Péter, R. Rekursive Funktionen in der Komputer-Theorie. Budapest: Akad. Kiado, 1951.Thompson, W. "Recursive Algorithms: A Mixed Blessing." Computers in Physics 10, 25-29, 1996.

Referenced on Wolfram|Alpha

Recursion

Cite this as:

Weisstein, Eric W. "Recursion." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/Recursion.html

Subject classifications