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
Use Cases
Frequently Asked Questions
From the Blog
Recursion Explained With Simple Examples
Recursion is when a function solves a problem by calling itself on smaller pieces. Learn how it works, why it needs a base case, and when to use it.
Read More ProgrammingRecursion vs Iteration: When to Use Each
Recursion solves a problem by calling itself on smaller inputs; iteration loops until done. Learn the trade-offs and when each approach is the right choice.
Read More Learn Through HobbiesLearn Algorithms Through Chess Puzzles
Chess is a perfect algorithmic playground: the knight's tour teaches BFS, the N- Queens problem teaches backtracking, move generation teaches recursion, and game AI teaches minimax search. This guide covers four classic computer science algorithms using chess problems that make the concepts tangible.
Read More