Recursion
Recursion is a technique where a function calls itself to solve smaller instances of the same problem. Every recursive function needs a base case to stop the recursion and a recursive case that breaks the problem down. Recursion is the foundation for divide-and-conquer algorithms, tree traversals, backtracking, and dynamic programming.
How Recursion Works
A recursive function solves a problem by reducing it to one or more smaller sub-problems of the same type. Every correct recursive function has two essential parts:
- Base case: The simplest instance of the problem that can be answered directly without further recursion. Without a base case, recursion would continue indefinitely.
- Recursive case: The function calls itself with a smaller or simpler input, making progress toward the base case with each call.
When a function calls itself, the current execution context is pushed onto the call stack. Each frame on the stack holds the function's local variables and the point to resume execution after the recursive call returns. Once the base case is reached, frames begin to unwind (pop off the stack) and return their results back up the chain.
Classic examples of recursion:
- Factorial:
n! = n * (n-1)!with base case0! = 1. - Fibonacci:
fib(n) = fib(n-1) + fib(n-2)with base casesfib(0) = 0andfib(1) = 1. - Tree traversal: Visit the current node, then recursively traverse left and right subtrees.
Stack overflow: If the recursion depth becomes too large (e.g., computing fib(100000) without optimization), the call stack exceeds its memory limit and the program crashes with a stack overflow error. Python's default recursion limit is 1000 frames; C++ and Java limits depend on the thread stack size.
Tail recursion: A special form where the recursive call is the last operation in the function. Some compilers and interpreters can optimize tail-recursive functions into iterative loops, eliminating the extra stack frames entirely. This is called tail-call optimization (TCO). Languages like Scheme guarantee TCO, while Python does not support it natively.
Interactive Visualization
Watch the recursive call tree for fib(n) being built step by step. Each node represents a function call. Yellow nodes are currently being computed, and green nodes have returned their value. Observe how the naive approach recomputes the same sub-problems many times.
Code Implementation
Below are implementations of three classic recursive functions: naive Fibonacci, factorial, and memoized Fibonacci. The memoized version eliminates redundant computations by caching previously computed results.
def fibonacci(n):
"""Naive recursive Fibonacci - O(2^n) time."""
if n <= 0:
return 0
if n == 1:
return 1
return fibonacci(n - 1) + fibonacci(n - 2)
def factorial(n):
"""Recursive factorial - O(n) time."""
if n <= 1:
return 1
return n * factorial(n - 1)
def fibonacci_memo(n, memo=None):
"""Memoized Fibonacci - O(n) time, O(n) space."""
if memo is None:
memo = {}
if n <= 0:
return 0
if n == 1:
return 1
if n in memo:
return memo[n]
memo[n] = fibonacci_memo(n - 1, memo) + fibonacci_memo(n - 2, memo)
return memo[n]
# Example usage
print(fibonacci(10)) # Output: 55
print(factorial(5)) # Output: 120
print(fibonacci_memo(50)) # Output: 12586269025 (instant with memoization)
import java.util.HashMap;
import java.util.Map;
public class Recursion {
/** Naive recursive Fibonacci - O(2^n) time */
public static int fibonacci(int n) {
if (n <= 0) return 0;
if (n == 1) return 1;
return fibonacci(n - 1) + fibonacci(n - 2);
}
/** Recursive factorial - O(n) time */
public static long factorial(int n) {
if (n <= 1) return 1;
return n * factorial(n - 1);
}
/** Memoized Fibonacci - O(n) time, O(n) space */
private static Map<Integer, Long> memo = new HashMap<>();
public static long fibonacciMemo(int n) {
if (n <= 0) return 0;
if (n == 1) return 1;
if (memo.containsKey(n)) return memo.get(n);
long result = fibonacciMemo(n - 1) + fibonacciMemo(n - 2);
memo.put(n, result);
return result;
}
public static void main(String[] args) {
System.out.println(fibonacci(10)); // Output: 55
System.out.println(factorial(5)); // Output: 120
System.out.println(fibonacciMemo(50)); // Output: 12586269025
}
}
#include <iostream>
#include <unordered_map>
using namespace std;
/** Naive recursive Fibonacci - O(2^n) time */
int fibonacci(int n) {
if (n <= 0) return 0;
if (n == 1) return 1;
return fibonacci(n - 1) + fibonacci(n - 2);
}
/** Recursive factorial - O(n) time */
long long factorial(int n) {
if (n <= 1) return 1;
return n * factorial(n - 1);
}
/** Memoized Fibonacci - O(n) time, O(n) space */
unordered_map<int, long long> memo;
long long fibonacciMemo(int n) {
if (n <= 0) return 0;
if (n == 1) return 1;
if (memo.count(n)) return memo[n];
memo[n] = fibonacciMemo(n - 1) + fibonacciMemo(n - 2);
return memo[n];
}
int main() {
cout << fibonacci(10) << endl; // Output: 55
cout << factorial(5) << endl; // Output: 120
cout << fibonacciMemo(50) << endl; // Output: 12586269025
return 0;
}
Complexity Analysis
The complexity of recursive algorithms depends heavily on the number of recursive calls and whether sub-problems overlap. Naive Fibonacci is a classic example of exponential blowup due to redundant computation, while memoization reduces it to linear time.
| Algorithm | Time Complexity | Space Complexity | Description |
|---|---|---|---|
| Naive Fibonacci | O(2n) | O(n) | Each call branches into two; call stack depth is n |
| Memoized Fibonacci | O(n) | O(n) | Each sub-problem computed once; memo table and call stack each use O(n) |
| Factorial | O(n) | O(n) | Single recursive call per step; call stack depth is n |
Why naive Fibonacci is O(2n): Each call to fib(n) makes two recursive calls, forming a binary tree of calls. The number of nodes in this tree grows exponentially. For example, fib(5) produces 15 function calls, while fib(30) produces over 2.6 million calls.
Space complexity insight: Even though the call tree is exponential, the call stack at any point only holds the frames along the current path from root to leaf, which is at most O(n) deep. Memoization adds an O(n) hash table but eliminates the exponential time by ensuring each unique sub-problem is solved only once.
Quiz
Test your understanding of recursion with these questions.
Q1. What are the two essential components of every recursive function?
Q2. What is the time complexity of the naive recursive Fibonacci algorithm?
Q3. What happens when a recursive function has no base case?
Q4. What is tail recursion?
Q5. How does memoization improve recursive Fibonacci from O(2n) to O(n)?