What is Recursion?
Definition
Recursion occurs when a method calls itself. It's a powerful programming technique where a problem is solved by breaking it down into smaller instances of the same problem.
Content of a Recursive Method
1. Base Case(s)
- Values of input variables for which we perform no recursive calls
- There should be at least one base case
- Every possible chain of recursive calls must eventually reach a base case
- When we stop the loop - the method must stop calling itself
2. Recursive Calls
- Calls to the current method
- Each recursive call should be defined so that it makes progress towards a base case
- The method must update parameters to eventually reach the base case
Critical Requirements
- Must have a base case (or the recursion never stops!)
- Must make progress toward the base case
- Must call itself (that's what makes it recursive)
The Recursion Pattern: Factorial
Classic Example: Factorial Function
Mathematical Definition: n! = 1 · 2 · 3 · ... · (n-1) · n
Recursive Definition:
f(n) = { 1 if n = 0
n · f(n-1) else
Java Implementation
Execution Trace: factorial(4)
factorial(4)
↓ call → return 4*6 = 24 (final answer)
factorial(3)
↓ call → return 3*2 = 6
factorial(2)
↓ call → return 2*1 = 2
factorial(1)
↓ call → return 1*1 = 1
factorial(0)
→ return 1 (base case)
How it Works:
- Forward calls: Methods keep calling themselves with decreasing n
- Base case reached: When n = 0, return 1
- Backward returns: Each call returns its result to the caller
- Final result: 4! = 24
Runtime: O(n) - Makes n+1 calls
Common Recursion Examples
1. Binary Search
Problem: Search for an integer in an ordered array
Strategy: Check middle element, then recur on appropriate half
Runtime: O(log n)
Each recursive call divides the search region in half, so there can be at most log n levels.
2. Linear Sum (Array Summation)
Problem: Add all numbers in an integer array
Strategy: Sum first n-1 elements, then add the nth element
Trace: linearSum(data, 5) for data = [4, 3, 6, 2, 8]
linearSum(data, 5) → return 15 + data[4] = 15 + 8 = 23
↓
linearSum(data, 4) → return 13 + data[3] = 13 + 2 = 15
↓
linearSum(data, 3) → return 7 + data[2] = 7 + 6 = 13
↓
linearSum(data, 2) → return 4 + data[1] = 4 + 3 = 7
↓
linearSum(data, 1) → return 0 + data[0] = 0 + 4 = 4
↓
linearSum(data, 0) → return 0 (base case)
3. Reversing an Array
Runtime: O(n)
Each recursive call swaps two elements and moves indices closer to the middle.
4. Computing Powers
✗ Slow Approach: O(n)
Makes n recursive calls
✓ Fast Approach: O(log n)
Uses repeated squaring!
How Recursive Squaring Works:
- 2⁴ = (2²)² = 4² = 16
- 2⁵ = 2 · (2²)² = 2 · 16 = 32
- 2⁸ = (2⁴)² = 16² = 256
Key Insight: Halve the exponent each time → logarithmic complexity!
5. Fibonacci Numbers
Definition:
- F₀ = 0
- F₁ = 1
- Fᵢ = Fᵢ₋₁ + Fᵢ₋₂ for i > 1
✗ Binary Recursion (SLOW)
Runtime: O(2ⁿ) - EXPONENTIAL!
Makes redundant calculations
✓ Linear Recursion (FAST)
Runtime: O(n) - LINEAR!
Returns pair (Fₖ, Fₖ₋₁)
6. English Ruler (Drawing Ticks)
Problem: Draw tick marks on a ruler with varying lengths
Pattern: For a tick of length L, draw smaller ticks (L-1) on both sides
Note: This is an example of binary recursion (two recursive calls per invocation)
Types of Recursion
1. Linear Recursion
Definition: Makes at most one recursive call per invocation
Characteristics:
- Test for base cases first
- Perform a single recursive call (may have conditionals to decide which call)
- Each recursive call makes progress toward base case
Examples:
- Factorial
- Linear sum
- Binary search
- Array reversal
2. Tail Recursion
Definition: A special case of linear recursion where the recursive call is the last step of the method
Special Property:
Tail recursive methods can be easily converted to iterative (loop-based) implementations, which are often more efficient.
Tail Recursive Version
Iterative Equivalent
3. Binary Recursion
Definition: Makes two recursive calls for each non-base case
Examples:
- Binary sum (divide array in half, sum each half)
- English ruler drawing
- Binary Fibonacci (inefficient)
4. Multiple Recursion
Definition: Makes potentially many recursive calls (more than two)
Example: Puzzle Solving
Generate all possible combinations/permutations
Recursion Tree for PuzzleSolve(3, [], {a,b,c})
[]
┌─────────┼─────────┐
[a] [b] [c]
┌──┴──┐ ┌──┴──┐ ┌──┴──┐
[ab][ac] [ba][bc] [ca][cb]
↓ ↓ ↓ ↓ ↓ ↓
abc acb bac bca cab cba
Complexity Analysis
Time Complexity Comparison
| Algorithm | Type | Time Complexity | Explanation |
|---|---|---|---|
| Factorial | Linear | O(n) | Makes n recursive calls |
| Binary Search | Linear | O(log n) | Halves search space each time |
| Linear Sum | Linear | O(n) | Processes each element once |
| Array Reversal | Tail | O(n) | Swaps n/2 pairs |
| Power (naive) | Linear | O(n) | Multiplies n times |
| Power (squaring) | Linear | O(log n) | Halves exponent each time |
| Binary Sum | Binary | O(n) | Processes each element in tree |
| Binary Fibonacci | Binary | O(2ⁿ) | Exponential - very inefficient! |
| Linear Fibonacci | Linear | O(n) | Makes n-1 calls |
Understanding Call Counts
Binary Fibonacci Analysis
Let nₖ = number of recursive calls for BinaryFib(k):
- n₀ = 1
- n₁ = 1
- n₂ = n₁ + n₀ + 1 = 3
- n₃ = n₂ + n₁ + 1 = 5
- n₄ = n₃ + n₂ + 1 = 9
- n₈ = 67
Notice: nₖ at least doubles every other time → nₖ > 2^(k/2)
This is exponential growth - very bad!
Key Insights for Efficiency
- Avoid redundant calculations: Binary Fibonacci recalculates same values multiple times
- Use clever math: Recursive squaring reduces O(n) to O(log n)
- Consider iterative alternatives: Tail recursive methods can often be converted to loops
- Store intermediate results: Dynamic programming (memoization) can help
Summary & Study Tips
Key Concepts to Remember
1. Three Requirements for Recursion:
- ✓ Must have a base case
- ✓ Must make progress toward base case
- ✓ Must call itself
2. Types of Recursion:
- Linear: One recursive call per invocation
- Tail: Recursive call is the last operation (easily converted to loops)
- Binary: Two recursive calls per invocation
- Multiple: Many recursive calls (used for enumeration/combinations)
3. When to Use Recursion:
- ✓ Problem can be broken into smaller subproblems of the same type
- ✓ Natural recursive structure (trees, divide-and-conquer)
- ✓ Code is clearer/simpler than iterative version
- ✗ Avoid when efficiency is critical and recursion adds overhead
- ✗ Avoid when iterative solution is equally clear
Common Pitfalls to Avoid
- Missing base case: Results in infinite recursion (stack overflow)
- Not making progress: Recursive call doesn't move toward base case
- Redundant calculations: Like binary Fibonacci - use dynamic programming instead
- Too many recursive calls: Can cause stack overflow for large inputs
- Modifying wrong parameters: Ensure you update parameters correctly
Study Strategies
To Master Recursion:
- Draw recursion trees: Visualize how calls are made and returned
- Trace execution: Follow the values step by step
- Count recursive calls: Understand time complexity
- Identify base cases: Always start here when analyzing recursive code
- Practice converting: Try converting recursive to iterative and vice versa
- Solve problems: Write your own recursive solutions from scratch
Practice Problems
Try implementing these recursively:
- Calculate the nth Fibonacci number (both ways)
- Find the maximum element in an array
- Check if a string is a palindrome
- Calculate the Greatest Common Divisor (GCD)
- Generate all permutations of a string
- Implement merge sort
- Traverse a binary tree
- Solve the Tower of Hanoi puzzle
Quick Reference Card
| Concept | Key Points |
|---|---|
| Base Case | Simplest case that can be solved directly without recursion |
| Recursive Case | Breaks problem into smaller subproblems and calls itself |
| Progress | Each recursive call must move closer to the base case |
| Stack Space | Each recursive call uses stack memory; deep recursion can overflow |
| Tail Recursion | Last operation is the recursive call; can be optimized to iteration |
| Time Complexity | Count how many times the function is called and work per call |
Final Tip
"To understand recursion, you must first understand recursion."
Practice is key! Start with simple examples and gradually work your way up to more complex problems. Draw diagrams, trace executions, and don't be afraid to experiment!
Practice Questions
Question 1: Three Requirements for Correct Recursion
Q: State the three necessary conditions for a correct recursive method and explain what goes wrong if each one is missing.
A:
1. Base case: Without it, the method calls itself forever → stack overflow (StackOverflowError in Java).
2. Progress toward base case: Without it, the recursion may never terminate even if a base case exists (e.g., factorial(n) that calls factorial(n) instead of factorial(n-1)).
3. Self-call (recursive case): Without it, the method is simply iterative/direct and does not use recursion. The combination of all three ensures the recursion terminates and produces a correct result.
Question 2: Trace factorial(4)
Q: Trace the execution of factorial(4) showing the call stack at maximum depth and the return values unwinding back.
A: Call stack builds up (forward phase): factorial(4) → factorial(3) → factorial(2) → factorial(1) → factorial(0). At maximum depth: 5 frames on the call stack. Return values unwind (backward phase): factorial(0) returns 1 → factorial(1) returns 1×1=1 → factorial(2) returns 2×1=2 → factorial(3) returns 3×2=6 → factorial(4) returns 4×6=24. Total: n+1 = 5 method calls, O(n) time, O(n) call stack space.
Question 3: Binary Fibonacci Is Exponential — Why?
Q: Explain why naive binary Fibonacci (two recursive calls per level) has O(2^n) complexity. Show the redundant computation for fib(5).
A: In naive binary recursion, binaryFib(5) calls binaryFib(4) and binaryFib(3). binaryFib(4) calls binaryFib(3) and binaryFib(2). Notice binaryFib(3) is computed twice. Similarly, binaryFib(2) is computed 3 times, binaryFib(1) is computed 5 times. In general, the number of calls for fib(k) grows faster than 2^(k/2), giving exponential complexity. The fix is linear recursion that returns a pair (Fₖ, Fₖ₋₁), computing each Fibonacci number exactly once — reducing time to O(n).
Question 4: Tail Recursion and Conversion to Iteration
Q: Define tail recursion. Show that the array reversal recursion is tail recursive and convert it to an iterative version.
A: A method is tail recursive if the recursive call is the very last operation before returning — no work is done with the return value. For array reversal: if (low < high) { swap(A[low], A[high]); reverseArray(A, low+1, high-1); } — the call is the last statement, so this is tail recursive.
Iterative equivalent: while (low < high) { swap(A[low], A[high]); low++; high--; }
The while loop replaces the recursive call, and the parameters become mutable loop variables. The iterative version uses O(1) stack space vs. O(n/2) for the recursive version.
Question 5: Recursive Squaring vs. Linear Power
Q: Compute 2^10 using the recursive squaring approach, showing each recursive call and demonstrating that only O(log n) multiplications are needed.
A: power(2, 10): n=10 (even) → y = power(2, 5), return y*y.
power(2, 5): n=5 (odd) → y = power(2, 2), return 2*y*y.
power(2, 2): n=2 (even) → y = power(2, 1), return y*y.
power(2, 1): n=1 (odd) → y = power(2, 0), return 2*y*y.
power(2, 0): base case → return 1.
Unwinding: power(2,1) = 2*1*1 = 2. power(2,2) = 2*2 = 4. power(2,5) = 2*4*4 = 32. power(2,10) = 32*32 = 1024. Only 4 recursive calls (log₂ 10 ≈ 3.3) vs. 10 for the naive approach.
Question 6: Types of Recursion Classification
Q: Classify each of the following as linear, tail, binary, or multiple recursion, and state the time complexity: (a) factorial, (b) binary search, (c) binary sum, (d) puzzle solver generating permutations.
A:
(a) Factorial: Linear recursion (one call per invocation, result used after return so NOT tail recursive). O(n).
(b) Binary search: Linear recursion (one call per invocation, last operation — actually tail recursive). O(log n).
(c) Binary sum: Binary recursion (two calls per invocation). O(n) — despite binary recursion, all n elements are processed once total.
(d) Puzzle solver: Multiple recursion (up to |U| calls per invocation, where U is the remaining unused set). O(n!) for generating all n! permutations.
Question 7: Call Stack and Stack Overflow
Q: What is the call stack, why does deep recursion risk a StackOverflowError, and which recursion type from this chapter is most dangerous for large inputs?
A: The call stack is a region of memory where each method invocation creates a stack frame storing local variables, parameters, and the return address. Frames are pushed on entry and popped on return. Java's call stack has a fixed maximum depth (typically ~5,000–10,000 frames, depending on frame size and JVM settings). If recursion goes deeper than this limit, a StackOverflowError is thrown.
The most dangerous type is linear/tail recursion with large n — e.g., factorial(100000) creates 100,001 frames. Binary recursion on large inputs also creates deep stacks (depth = log₂ N for balanced recursion). Tail recursion can be optimized by compilers to reuse the same frame (tail call optimization), but Java does NOT perform this optimization.
Question 8: Design a Recursive Solution
Q: Write a recursive method to check if a string is a palindrome (reads the same forwards and backwards). Identify the base case(s), recursive case, and its time complexity.
A:
Base cases: (1) Empty string → true (2) Single character → true.
Recursive case: Check if first and last characters match AND the substring between them is a palindrome.
boolean isPalindrome(String s, int lo, int hi) {
if (lo >= hi) return true; // base cases
if (s.charAt(lo) != s.charAt(hi)) return false;
return isPalindrome(s, lo+1, hi-1); // tail recursive
}
Time complexity: O(n/2) = O(n) — makes n/2 recursive calls. Space: O(n) call stack (or O(1) if compiler performs tail call optimization). This is a tail-recursive method and can be directly converted to a while loop.