Recursion (computer science)
Recursion (computer science)
Recursion is a technique in computer science where a function calls itself, either directly or indirectly, in order to solve a problem by breaking it into smaller, similar subproblems. A recursive function typically consists of a base case (a condition that stops the recursion) and a recursive case (the part where the function calls itself with modified arguments). Recursion is widely used in algorithm design, data structures, and functional programming.
Common examples
A classic example is the computation of the factorial of a number: the factorial of n (written n!) is defined as n × (n-1)!, with the base case 0! = 1. Another common example is the Fibonacci sequence, where each term is the sum of the two preceding terms, with base cases F(0)=0 and F(1)=1.
Recursion also naturally appears in operations on recursive data structures such as trees and linked lists, for tasks like tree traversal (e.g., depth-first search) and list processing.
Features
- Elegance and simplicity: Recursive solutions can express the problem's structure more directly than iterative approaches, making them easier to understand.
- Stack usage: Each recursive call adds a new frame to the call stack, which may lead to stack overflow if the recursion depth is too large.
- Tail recursion: A special form where the recursive call is the last operation performed; some compilers and interpreters can optimize tail-recursive functions to avoid growing the stack (tail-call optimization).
History
The concept of recursion in computing traces back to early work in computability theory and lambda calculus (developed by Alonzo Church in the 1930s), where recursive definitions were formalized. The first programming language to support recursion was Lisp, introduced in the late 1950s. Recursion later became a cornerstone of functional programming languages and is supported in nearly all modern programming languages.