Recursion
Recursion is a programming and mathematical technique in which a function calls itself with a smaller or simpler version of the original problem, progressing toward one or more base cases that terminate the chain of calls. Every recursive solution requires a base case (stopping condition) and a recursive case (self-referential reduction). Recursion is fundamental to tree traversal, divide-and-conquer algorithms, backtracking, and functional programming.
Key Formula
F(n) = 1 if n <= 1, else F(n) = n * F(n-1) [factorial example]
LaTeX: F(n) = \begin{cases} 1 & \text{if } n \le 1 \\ n \cdot F(n-1) & \text{if } n > 1 \end{cases}
| Symbol | Meaning | Unit |
|---|---|---|
| F(n) | Factorial of n | dimensionless |
| n | Input integer | dimensionless |
| F(n-1) | Recursive call on n-1 | dimensionless |
Worked Example
Problem
Compute 4! (four factorial) using recursion.
Solution
F(4) calls F(3): 4 * F(3). F(3) calls F(2): 3 * F(2). F(2) calls F(1): 2 * F(1). F(1) hits base case: returns 1. Unwinding: F(2) = 2 * 1 = 2. F(3) = 3 * 2 = 6. F(4) = 4 * 6 = 24. Call stack depth: 4 frames.
Answer
4! = 24. The recursion used 4 call stack frames and returned through them in reverse order.
Recursion vs Iteration Comparison
| Aspect | Recursion | Iteration |
|---|---|---|
| Mechanism | Function calls itself | Loops (for/while) |
| Stack Usage | Call stack (O(n) space) | Constant stack space |
| Readability | Often cleaner for trees/graphs | Often cleaner for linear tasks |
| Risk | Stack overflow for deep recursion | Infinite loop if condition wrong |
| Performance | Overhead from function calls | Generally faster |
| Example | Tree traversal, quicksort | Array sum, linear search |
Interactive Tools
Python Tutor – Visualize Recursion
Visualize call stacks and recursive calls step-by-step in Python/JS/Java
Open Tool
Wikimedia Commons, CC BY-SA
Related Terms
Divide and Conquer
Divide and Conquer is an algorithmic paradigm that recursively breaks a problem into two or more smaller subproblems of the same type until they become simple enough to solve directly, then combines their solutions to solve the original problem. The three phases are: Divide (split the problem), Conquer (solve subproblems recursively), and Combine (merge results). Famous examples include Merge Sort, Quick Sort, Binary Search, and the Fast Fourier Transform.
Backtracking
Backtracking is an algorithmic technique for solving constraint satisfaction and combinatorial problems by incrementally building a solution and abandoning (backtracking from) a partial solution as soon as it is determined to violate the problem constraints, then trying the next possibility. It is essentially a depth-first search through the space of candidate solutions, pruning branches that cannot lead to a valid solution. Backtracking is used to solve N-Queens, Sudoku, crossword puzzles, subset-sum, and graph coloring problems.
Dynamic Programming
Dynamic Programming (DP) is an algorithmic paradigm that solves complex problems by breaking them into overlapping subproblems, solving each subproblem only once, and storing results to avoid redundant computation (memoization or tabulation). It applies when a problem exhibits two key properties: optimal substructure (optimal solution contains optimal solutions to subproblems) and overlapping subproblems. DP is used in sequence alignment, shortest-path problems, knapsack optimization, and compiler design.
From Latin recursio, meaning "a running back" (re- "back" + currere "to run"). In mathematics, recursive definitions appeared in the work of Giuseppe Peano (1889) for natural numbers. In computer science, recursion was formalized with the development of LISP by John McCarthy in 1958.