Recursion
Recursion is a programming technique in which a function solves a problem by calling itself on smaller subproblems, combined with a base case that stops the recursive calls and prevents infinite repetition.
Definition
Recursion is a programming technique in which a function solves a problem by calling itself on smaller subproblems, combined with a base case that stops the recursive calls and prevents infinite repetition.
Overview
A recursive function typically has two parts: one or more base cases that return a result directly without further recursion, and a recursive case that breaks the problem into a smaller version of itself and calls the function again, trusting that the smaller call will eventually reach a base case. Classic examples include computing a factorial, traversing a linked list or tree structure, and algorithms like quicksort and mergesort, where the natural structure of the problem — a smaller version of the same problem nested inside the larger one — maps directly onto a recursive solution. Recursion is especially natural for problems with inherently recursive structure, like tree and graph traversal, parsing nested expressions, and divide-and-conquer algorithms, often producing more concise and readable code than an equivalent iterative loop. However, each recursive call typically consumes stack space, so deep recursion can cause stack overflow errors, and in languages without guaranteed tail-call optimization, very deep or performance-critical recursive code is sometimes rewritten as an explicit loop. Some languages, notably those in the functional programming tradition like Scheme and Haskell, guarantee proper tail-call optimization, allowing certain recursive functions to run in constant stack space, effectively as efficient as loops. Understanding recursion — including how to identify base cases and how call stacks grow and unwind — is considered a foundational skill in computer science, closely tied to concepts like Big O notation for reasoning about the time and space complexity of recursive algorithms.
Key Concepts
- Function calls itself on a smaller version of the problem
- Requires one or more base cases to terminate the recursion
- Well suited to inherently recursive structures like trees and graphs
- Consumes stack space per call, risking stack overflow if too deep
- Some languages optimize tail-recursive calls to run in constant space
- Common in divide-and-conquer algorithms like quicksort and mergesort