Recursion is a way of solving a problem by having a procedure call itself on a smaller version of the same problem, with a base case that stops the calls once the problem is simple enough to answer directly. It is one of computing's central organizing ideas, letting problems that are naturally self similar, walking a tree shaped data structure or defining a mathematical sequence, be expressed compactly, and it was given a rigorous mathematical footing well before general purpose computers existed, in Alonzo Church's 1930s lambda calculus and Kurt Godel's earlier work on recursive functions.
Facts
Disputed
Origin YearThe mathematical theory of recursive functions was formalized in the 1930s by Church, Godel and Kleene; John McCarthy brought recursion into practical programming with Lisp around 1958 to 1960, so the concept's origin year depends on whether the mathematics or the programming language is being dated. Core PrincipleA procedure that solves a problem by calling itself on a smaller instance of the same problem, until a base case is reached. 1 Connections
Associated With
Source Wikipedia: Recursion (Computer Science)
In Field
Source Encyclopedia Britannica: Computer ScienceEncyclopedia Britannica Editors
Sources
1. Encyclopedia Britannica: Computer Science
Encyclopedia Britannica Editors, Encyclopaedia Britannica Inc, 2024View the Source 2. Wikipedia: Recursion (Computer Science)
Wikimedia FoundationHistoryQuote, History
The early work done by Church, Godel, Kleene, and Turing on recursive function and computability laid the groundwork that made recursion possible in programming languages.
Reader Challenges (0)
No disputes yet. Spotted an error or a better source? Open the first one.
Sign in to dispute this or suggest a correction.