Recursion

IB Syllabus: B2.4.4, B2.4.5 (HL) – Explain the fundamental concept of recursion. Construct and trace recursive algorithms.

This page is HL only.

Table of Contents

1. Key Concepts
   1. What is Recursion?
   2. How Recursion Works: The Call Stack
2. Worked Examples
   1. Example 1: Factorial
   2. Example 2: Fibonacci
   3. Example 3: Sum of Array
   4. Example 4: Power (Exponentiation)
3. Recursion vs Iteration
4. Common Mistakes
5. Quick Check
6. Trace Exercise
7. Code Completion
8. Spot the Error
9. Predict the Output
10. Practice Exercises
    1. Core
    2. Extension
    3. Challenge
11. Connections

---

Key Concepts

What is Recursion?

Recursion is when a method calls itself to solve a problem by breaking it into smaller, identical sub-problems. Each call works on a simpler version of the original problem until it reaches a case simple enough to solve directly.

Every recursive method has two essential parts:

1. Base case – the condition that stops the recursion. Without it, the method calls itself forever (infinite recursion).
2. Recursive case – the method calls itself with a simpler input, moving towards the base case.

public static int factorial(int n) {
    if (n == 0) {           // base case
        return 1;
    }
    return n * factorial(n - 1);  // recursive case
}

Every recursive method MUST have a base case. Without it, the method never stops and causes a StackOverflowError.

How Recursion Works: The Call Stack

When a method calls itself, Java pushes a new frame onto the call stack. Each frame has its own copy of local variables and parameters. When the base case is reached, frames are popped one by one, each returning its result to the caller.

Tracing factorial(4):

factorial(4) calls factorial(3)
  factorial(3) calls factorial(2)
    factorial(2) calls factorial(1)
      factorial(1) calls factorial(0)
        factorial(0) returns 1          ← base case
      factorial(1) returns 1 * 1 = 1
    factorial(2) returns 2 * 1 = 2
  factorial(3) returns 3 * 2 = 6
factorial(4) returns 4 * 6 = 24

The call stack grows as calls are made (going down) and shrinks as returns happen (going up).

---

Worked Examples

Example 1: Factorial

n! = n * (n-1) * (n-2) * ... * 1, with 0! = 1.

public static int factorial(int n) {
    if (n == 0) {
        return 1;
    }
    return n * factorial(n - 1);
}

Call	n	Returns	Calculation
factorial(0)	0	1	Base case
factorial(1)	1	1	1 * factorial(0) = 1 * 1
factorial(2)	2	2	2 * factorial(1) = 2 * 1
factorial(3)	3	6	3 * factorial(2) = 3 * 2
factorial(4)	4	24	4 * factorial(3) = 4 * 6

Example 2: Fibonacci

The Fibonacci sequence: 0, 1, 1, 2, 3, 5, 8, 13, … Each number is the sum of the two before it.

public static int fibonacci(int n) {
    if (n == 0) {
        return 0;
    }
    if (n == 1) {
        return 1;
    }
    return fibonacci(n - 1) + fibonacci(n - 2);
}

Two base cases: fibonacci(0) = 0 and fibonacci(1) = 1.

Tracing fibonacci(4):

fibonacci(4)
├── fibonacci(3)
│   ├── fibonacci(2)
│   │   ├── fibonacci(1) → 1
│   │   └── fibonacci(0) → 0
│   │   → 1 + 0 = 1
│   └── fibonacci(1) → 1
│   → 1 + 1 = 2
└── fibonacci(2)
    ├── fibonacci(1) → 1
    └── fibonacci(0) → 0
    → 1 + 0 = 1
→ 2 + 1 = 3

Fibonacci is inefficient recursively because it recalculates the same values many times (e.g., fibonacci(2) is calculated twice above). Its time complexity is O(2^n). An iterative solution with a loop is O(n).

Example 3: Sum of Array

Sum all elements in an array recursively by processing one element at a time.

public static int sum(int[] arr, int index) {
    if (index == arr.length) {  // base case: past the end
        return 0;
    }
    return arr[index] + sum(arr, index + 1);  // current + rest
}

Call: sum(new int[]{3, 7, 2}, 0) returns 12.

Example 4: Power (Exponentiation)

Calculate base^exponent recursively: x^n = x * x^(n-1), with x^0 = 1.

public static int power(int base, int exponent) {
    if (exponent == 0) {
        return 1;
    }
    return base * power(base, exponent - 1);
}

Call: power(2, 5) returns 32.

---

Recursion vs Iteration

Criterion	Recursion	Iteration (Loop)
Structure	Method calls itself	Loop repeats a block
Termination	Base case	Loop condition becomes false
Memory	Uses call stack (one frame per call)	Uses constant memory
Readability	Often cleaner for tree/divide-and-conquer problems	Often cleaner for simple counting/accumulation
Risk	StackOverflowError if base case is not reached	Infinite loop if condition never becomes false
Performance	Can be slower (function call overhead)	Generally faster (no call overhead)

When to use recursion:

• Problems that naturally decompose into smaller identical sub-problems
• Tree traversal (binary search trees)
• Divide-and-conquer algorithms (quicksort, merge sort)
• Problems with recursive mathematical definitions (factorial, Fibonacci)

When to use iteration:

• Simple counting, accumulation, or traversal
• Performance is critical and the problem has a straightforward loop solution
• Deep recursion would exhaust the call stack

IB exam tip: You can always rewrite a recursive solution as an iterative one (and vice versa). The exam may ask you to do either.

---

Common Mistakes

Missing base case:

public static int bad(int n) {
    return n * bad(n - 1);  // never stops -- StackOverflowError
}

Base case never reached:

public static int bad(int n) {
    if (n == 0) { return 1; }
    return n * bad(n + 1);  // n increases, never reaches 0
}

Off-by-one base case:

public static int bad(int n) {
    if (n == 1) { return 1; }  // what if n == 0? Misses it.
    return n * bad(n - 1);
}

---

Quick Check

Q1. What is the purpose of the base case in a recursive method?

Q2. What does factorial(3) return?

Q3. What happens if a recursive method has no base case?

Q4. Why does recursion use more memory than iteration?

Q5. What does fibonacci(5) return?

---

Trace Exercise

Trace the call stack for power(3, 4).

Trace: Fill in the return value for each call as the stack unwinds.

public static int power(int base, int exponent) {
    if (exponent == 0) { return 1; }
    return base * power(base, exponent - 1);
}

Call	base	exponent	Returns
power(3, 4)	3	4
power(3, 3)	3	3
power(3, 2)	3	2
power(3, 1)	3	1
power(3, 0)	3	0	1 (base case)

---

Code Completion

Complete the recursive method to count the digits in a positive integer.

Fill in the blanks: countDigits(4523) should return 4.

public static int countDigits(int n) {
    if (n < ) {
        return ;
    }
    return 1 + countDigits(n / );
}

---

Spot the Error

This recursive method should sum the numbers from 1 to n, but it crashes.

Bug Hunt: This method should return 1+2+...+n, but it causes a StackOverflowError.

1public static int sum(int n) { 2 if (n == 0) { 3 return 0; 4 return n + sum(n + 1); 5 } 6}

Pick the correct fix for line 4:

---

Predict the Output

Predict: What does this code print?

public static void mystery(int n) {
    if (n == 0) { return; }
    System.out.println(n);
    mystery(n - 1);
}
// Call: mystery(4)

Predict: What does this code print? (Note: the print is AFTER the recursive call.)

public static void mystery2(int n) {
    if (n == 0) { return; }
    mystery2(n - 1);
    System.out.println(n);
}
// Call: mystery2(4)

---

Practice Exercises

Core

1. Trace factorial(5) – Write out every call and return value, showing the call stack growing and shrinking. What is the final result?

2. Recursive countdown – Write a recursive method countdown(int n) that prints the numbers from n down to 1, then prints “Go!”. Do not use any loops.

3. Identify the base case – For each of the following recursive methods, state the base case and what would happen if it were removed:

   • (a) factorial(n) with base case n == 0
   • (b) fibonacci(n) with base cases n == 0 and n == 1
   • (c) sum(arr, index) with base case index == arr.length

Extension

1. Recursive string reversal – Write a recursive method reverse(String s) that returns the string in reverse. Base case: empty string or single character. Recursive case: last character + reverse of the rest.

2. Recursive binary search – Rewrite binary search as a recursive method: binarySearch(int[] arr, int target, int low, int high). Return the index of the target or -1 if not found.

Challenge

1. Towers of Hanoi – Implement the classic Towers of Hanoi problem for n disks. Print each move as “Move disk from [source] to [destination]”. The recursive insight: to move n disks from A to C, first move n-1 disks from A to B (using C as helper), then move disk n from A to C, then move n-1 disks from B to C (using A as helper).

---

Connections

• Prerequisites: Stacks – the call stack is a stack
• Prerequisites: Big-O Notation – analysing recursive complexity
• Related: Searching Algorithms – binary search can be written recursively
• Forward: Quicksort – a recursive sorting algorithm
• Forward: ADTs: Binary Search Trees – tree traversal uses recursion