Recursion
A process defined by reference to a simpler version of itself.
Last updated
Recursion is a concept in which the definition of a process or object depends on a simpler or previous version of itself. It is used across disciplines including linguistics, logic, mathematics, and computer science, where a function being defined is applied within its own definition. While this can appear to define an infinite number of instances, it is often structured so that no infinite loop occurs.
Quick Facts
- Field
- Mathematics
- Computer Science
- Linguistics
- Logic
- Known for
- Recursive definitions
- base case and recursive step
- natural numbers
- Fibonacci sequence
- recursive humor
Facts from the source article.
Background
Recursion is formally defined by two properties: a base case that terminates the recursion, and a recursive step that reduces all cases toward the base case. For example, one's ancestor is defined as either one's parent (base case) or one's parent's ancestor (recursive step). The Fibonacci sequence is a classic example: Fib(0)=0, Fib(1)=1, and for n>1, Fib(n)=Fib(n-1)+Fib(n-2). The Peano axioms define natural numbers recursively: zero is a natural number, and each natural number has a successor that is also a natural number.
Did You Know?
- Recursive humor includes glossary entries like 'Recursion, see Recursion' and the joke 'To understand recursion, you must understand recursion.'
- Recursive acronyms include PHP (PHP Hypertext Preprocessor), WINE (WINE Is Not an Emulator), and GNU (GNU's not Unix).
Frequently Asked Questions
What is Recursion in Set Theory & Logic 1-19?
Recursion is a defining principle where a process or object is built by referencing a simpler or earlier version of itself. In the 1-19 entry, it serves as the structural backbone connecting logic, mathematics, and computer science.
Where does Recursion show up across disciplines?
The concept threads through linguistics, formal logic, mathematics, and computer science, wherever a function or structure is defined by applying itself to a simpler input. The Fibonacci sequence is the go-to example fans cite when discussing its mathematical flavor.
More in Set Theory & Logic
Sources
Compiled from Wikipedia and the sources listed below. Text from Wikipedia is available under CC BY-SA 4.0; this entry is adapted from it.
- Wikipedia: Recursion (CC BY-SA 4.0).
Spotted an error? Know more?
Reader corrections go straight into our review queue. Suggest an edit · How this site is sourced