Recursion
/rɪˈkɜːr.ʒən/ · Noun · Development
Definitions
Recursion is a programming technique in which a function calls itself to solve smaller instances of the same problem. Every recursive function needs a base case that stops the recursion and a recursive case that breaks the problem into a simpler subproblem. Classic examples include computing factorials, traversing tree structures, and generating Fibonacci numbers. Recursion maps naturally to problems that have a self-similar or divide-and-conquer structure, such as merge sort, directory tree traversal, and parsing nested data formats like JSON or XML. While elegant, recursion carries the risk of stack overflow if the recursion depth grows too large, because each call adds a frame to the call stack. Tail-call optimization, available in some languages, can mitigate this by reusing the current stack frame. Many recursive solutions can also be rewritten iteratively using an explicit stack, which may be more efficient in practice.
In plain English: When a function solves a problem by breaking it into smaller copies of the same problem and calling itself on each one — like Russian nesting dolls of code.
Etymology
- 1930s
- Godel, Church, and Turing formalize recursive functions as a foundation of computability theory.
- 1958
- John McCarthy's Lisp makes recursion a practical programming tool, replacing iterative loops in many cases.
- 1960s
- Algol 60 supports recursive procedures, establishing recursion as a standard language feature.
- 2020s
- Recursion remains a core computer science concept. 'To understand recursion, you must first understand recursion' is the field's most enduring joke.
Origin Story
See: recursion (the joke that explains itself)
**Recursion** — a function calling itself — has roots in mathematics long before computers existed. The concept appears in the work of **Kurt Godel** (1931), who used recursive functions in his incompleteness theorems, and **Alonzo Church** and **Alan Turing** (1936), whose models of computation were inherently recursive.
In programming, recursion became practical with the development of stack-based memory allocation in the late 1950s. Languages like LISP (1958) made recursion a first-class programming technique. The classic teaching examples — factorial, Fibonacci, Tower of Hanoi — have been traumatizing computer science students ever since.
The self-referential nature of recursion has made it a rich source of humor. Google's "Did you mean: *recursion*" Easter egg (which links back to the same search) is the most famous example. The GNU project's name is a recursive acronym: **GNU's Not Unix**. And every CS textbook seems obligated to define recursion as: "See: recursion."
Coined by: Mathematical foundations by Godel, Church, Turing
Context: Mathematics, 1930s; programming adoption, late 1950s
Fun fact: The first rule of recursion is to have a base case. The second rule of recursion is to see the first rule. Google's 'recursion' Easter egg has been active since at least 2010 and remains one of their longest-running search jokes.