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.

Key Concepts
Worked Examples
Where Recursion Shines
1. Why BST insertion is recursive
Recursion vs Iteration
Common Mistakes
Quick Check
Trace Exercise
Code Completion
Spot the Error
Predict the Output
Practice Exercises
GitHub Classroom
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:

Base case – the condition that stops the recursion. Without it, the method calls itself forever (infinite recursion).
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) = 4 * factorial(3)
             = 4 * 3 * factorial(2)
             = 4 * 3 * 2 * factorial(1)
             = 4 * 3 * 2 * 1 * factorial(0)
             = 4 * 3 * 2 * 1 * 1
             = 24

Each call adds a frame on top of the stack; each return pops the top frame and hands its value down to the caller. Too many frames before a return and the stack runs out of memory – StackOverflowError. This is the failure mode to keep in mind whenever a recursive method is called with a very large input: even a correct algorithm can blow the stack if the chain of calls is long enough.

Linear vs Branching Recursion

The shape of a recursive method’s call chain is the key classification:

Linear recursion – at most one recursive call runs per invocation. The call chain is a straight line. Examples: factorial, sumUpTo, array sum, binary search, string reversal, countDigits.
Branching recursion – two or more recursive calls run per invocation. The call chain grows into a tree. Examples: Fibonacci, BST traversals, quicksort, Towers of Hanoi, fractals.

A method with two recursive-call sites inside an if / else if / else is still linear if only one branch fires per call – what counts is how many calls run per invocation, not how many appear in the code.

Linear recursion is generally cheaper (memory proportional to the depth of the chain) and easier to write correctly; branching recursion is more expressive for self-similar data but can be catastrophically slow if the same sub-problem is recomputed many times (see Fibonacci below).

Note for IB CS learners (B2.4 syllabus): The current IB CS syllabus (B2.4) splits recursion into two skills: B2.4.4 Explain and identify (describe recursion, identify base and recursive cases, recognise applications, trace any recursive method given to you – linear or branching) and B2.4.5 Construct and trace (write simple non-branching, i.e. linear, recursive methods). Branching applications – Fibonacci, quicksort, tree traversals, Towers of Hanoi – are recognise-and-trace only; you do not author them on the exam. Every construct task in the practice exercises below is linear to match this scope.

You Already Know This

Recursion is built on ideas you have already used:

Methods with parameters and return types – recursion is a static method that calls itself
Iteration (while / do-while / for loops) – recursion is the alternative to iteration; many loops can be rewritten as recursive calls
Binary search – you wrote it with a while loop; this page shows the same algorithm as recursion with a shrinking (low, high) window
Binary search tree traversals – when you walked pre-order / in-order / post-order on paper, you were following a recursive pattern without a name for it

Worked Examples

Each example is labelled LINEAR or BRANCHING so you can see the shape of the call chain at a glance. Construct tasks on the exam come from the LINEAR examples only.

Example 1: Countdown (LINEAR)

The simplest useful recursion – print numbers from n down to 1, then “Go”.

public static void countDown(int n) {
    if (n == 0) {
        System.out.println("Go");
        return;
    }
    System.out.println(n);
    countDown(n - 1);
}

Call: countDown(3) prints:

3
2
1
Go

One recursive call per invocation. Base case: n == 0.

Example 2: Factorial (LINEAR)

Mathematical definition: 5! = 5 * 4 * 3 * 2 * 1 = 120, and also 5! = 5 * 4!.

Recursive definition: n! = n * (n-1)! where 0! = 1.

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

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

The recursive definition mirrors the mathematical definition exactly. This pattern – “f(n) in terms of f(n-1)” – is why factorial is the classic recursion example.

Example 3: Array Sum – Iterative vs Recursive (LINEAR)

You already know the iterative version:

public static int sumIterative(int[] arr) {
    int total = 0;
    for (int i = 0; i < arr.length; i++) {
        total += arr[i];
    }
    return total;
}

The recursive version needs an index parameter because there is no loop variable:

public static int sumRecursive(int[] arr, int index) {
    if (index == arr.length) {                       // base case
        return 0;
    }
    return arr[index] + sumRecursive(arr, index + 1); // recursive case
}

Call with sumRecursive(arr, 0). Base case: the index has passed the end of the array. Recursive case: add the current element to the sum of everything after it.

For linear sequential work like this, the iterative version is often clearer. Recursion earns its keep when the problem has a self-similar structure (trees, divide-and-conquer), not when you are just walking a flat array.

Example 4: Binary Search, Recursively (LINEAR)

In W26 you wrote binary search with a while loop. Here it is as recursion – same algorithm, no mid-updating loop variables:

public static int binarySearch(int[] arr, int target, int low, int high) {
    if (low > high) {                   // base case: not found
        return -1;
    }
    int mid = (low + high) / 2;
    if (arr[mid] == target) {           // base case: found
        return mid;
    }
    if (target < arr[mid]) {
        return binarySearch(arr, target, low, mid - 1);   // recurse left
    }
    return binarySearch(arr, target, mid + 1, high);      // recurse right
}

Call with the full window: binarySearch(arr, target, 0, arr.length - 1).

Trace binarySearch([2, 5, 8, 13, 21, 34, 55], 21, 0, 6):

binarySearch(arr, 21, 0, 6): mid=3, arr[3]=13, 21 > 13, recurse right
binarySearch(arr, 21, 4, 6): mid=5, arr[5]=34, 21 < 34, recurse left
binarySearch(arr, 21, 4, 4): mid=4, arr[4]=21, return 4

There are two recursive call sites in the code (left half or right half), but only one runs per invocation – the if selects exactly one branch. So the call chain is still a straight line: this is linear recursion, same shape as factorial.

Example 5: Power (LINEAR)

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. Another “f(n) in terms of f(n-1)” pattern.

Example 6: Fibonacci – a Branching Example (BRANCHING, trace / explain only)

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;                              // base case 1
    if (n == 1) return 1;                              // base case 2
    return fibonacci(n - 1) + fibonacci(n - 2);        // TWO recursive calls
}

Two base cases and two recursive calls per invocation – this is branching recursion.

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 pathologically slow recursively. Each call spawns two more, so the call tree roughly doubles at every level: fibonacci(n) is O(2^n). An iterative version with a loop is O(n). The recursive version recomputes fibonacci(2) twice just for fibonacci(4); for fibonacci(30) it recomputes the same small values millions of times.

Note for IB CS learners: Fibonacci is a recognise-and-describe example in B2.4.4 – you trace it, you explain why it is slow, and you compare it to the iterative version, but it is not a construct task. The “write a recursive method” exercises on this page are linear recursion only.

Example 7: String Reversal (LINEAR, optional)

Recursion on a String, using W28 String methods:

public static String reverse(String s) {
    if (s.length() <= 1) {
        return s;
    }
    return reverse(s.substring(1)) + s.charAt(0);
}

Trace reverse("JAVA"):

reverse("JAVA") = reverse("AVA") + 'J'
                = (reverse("VA") + 'A') + 'J'
                = ((reverse("A") + 'V') + 'A') + 'J'
                = (("A" + 'V') + 'A') + 'J'
                = "AV" + 'A' + 'J'
                = "AVA" + 'J'
                = "AVAJ"

Base case: a string of length 0 or 1 is already its own reverse. Each call strips one character from the front, so substring(1) shortens the string until the base case.

Where Recursion Shines

The syllabus names these applications. Recognise and describe them – on the exam you will trace or explain the branching ones, not construct them from scratch.

Application	Shape	Why recursion fits
Factorial, GCD, sum-to-n	Linear	The mathematical definition is self-referential: `f(n)` in terms of `f(n-1)`.
Binary search	Linear	Halve the search range, recurse on the half containing the target.
String reversal, countDigits	Linear	Strip one character / one digit per call.
Fractal image creation (Koch, Sierpinski)	Branching	Each fragment is a scaled-down copy of the whole.
Tree traversals (BST in-order / pre-order / post-order)	Branching	A node’s subtree is itself a tree, so the same operation applies at every level.
Sorting algorithms (quicksort, merge sort)	Branching	Partition the array, sort each half, combine.
Towers of Hanoi	Branching	Move `n-1` disks aside, move the bottom disk, move `n-1` disks back on top.
Nested data (folders, DOM tree, JSON tree)	Branching	Each container holds items, some of which are containers.

The common thread: a problem is naturally recursive when its data or its definition is self-similar – that is, any part of it has the same structure as the whole. A folder contains folders. A BST’s subtree is itself a BST. A fractal fragment is a scaled-down copy of the fractal. When you see self-similar structure, recursion usually gives the cleanest solution.

Why BST insertion is recursive

When you insert a name into a binary search tree, you compare it to the current node and then either insert into the left subtree or the right subtree. But a subtree is itself a BST, so inserting into it is the same problem on smaller data – just call the same insert routine on that subtree. The base case is reaching an empty subtree: the name becomes a new leaf there.

This is the self-similar-structure argument written out for one specific application. Being able to articulate it – “the same operation applies at every level because the data structure repeats” – is a useful skill for answering “explain why X is recursive” questions on any assessment.

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?

Q6. Which of these is an example of linear (non-branching) recursion?

Q7. A recursive method contains two return statements that call itself, inside an if and an else branch. Which classification applies?

Trace Exercise

Trace 1: `power(3, 4)` (LINEAR)

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)

Trace 2: `f(7)` – odd-number sum (LINEAR)

Trace: State the return value of each call in the chain.

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

Call	Returns
f(-1)	0 (base case)
f(1) = 1 + f(-1)
f(3) = 3 + f(1)
f(5) = 5 + f(3)
f(7) = 7 + f(5)

Trace 3: `step(9, 3)` – two call sites, one fires (LINEAR)

Trace: This method has two recursive call sites but only one runs per invocation -- still linear. Fill in the return values.

public static int step(int a, int b) {
    if (a > b) {
        return step(a - 2, b + 1);
    } else if (a == b) {
        return 2 * step(a - 1, b + 2) + 3;
    } else {
        return a + b;
    }
}

Call	Branch taken	Returns
step(4, 7)	else (a < b)
step(5, 5) = 2 * step(4, 7) + 3	else-if (a == b)
step(7, 4) = step(5, 5)	if (a > b)
step(9, 3) = step(7, 4)	if (a > b)

Trace 4: `mystery(5)` – a branching example (BRANCHING)

Trace: Two recursive calls per invocation -- the call chain is a tree, not a line. Fill in the return values.

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

Call	Returns
mystery(0)	0 (base case)
mystery(1)	1 (base case)
mystery(2) = mystery(1) + mystery(0)
mystery(3) = mystery(2) + mystery(1)
mystery(4) = mystery(3) + mystery(2)
mystery(5) = mystery(4) + mystery(3)

This is Fibonacci. Notice how mystery(3) gets computed twice and mystery(2) gets computed three times on the way to mystery(5) – the branching shape makes the machine redo work. That is why recursive Fibonacci is O(2^n).

Code Completion

Fill in the base case: `sumUpTo`

Fill in the blanks: sumUpTo(4) should return 1 + 2 + 3 + 4 = 10.

public static int sumUpTo(int n) {
    if (n == ) {
        return ;
    }
    return n + sumUpTo(n - );
}

Fill in the recursive case: `factorial`

Fill in the blanks: the recursive case for factorial is n * factorial(n - 1).

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

Fill in both cases: `countDigits`

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

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

Advance toward the base case: `countMatches`

Fill in the blanks: the recursive call must advance index by 1 each time, so the base case index == arr.length is eventually reached.

public static int countMatches(int[] arr, int target, int index) {
    if (index == arr.length) {
        return ;
    }
    if (arr[index] == target) {
        return  + countMatches(arr, target, index + );
    }
    return countMatches(arr, target, index + );
}

Spot the Error

Bug 1: Recursive call goes the wrong direction

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:

Bug 2: Missing base case

Bug Hunt: This method is meant to compute n! but throws a StackOverflowError for any input.

1public static int product(int n) { 2 return n * product(n - 1); 3}

Pick the correct fix:

Bug 3: Off-by-one base case

Bug Hunt: sumUpTo(3) returns 7 instead of 6. The method does not crash, but the answer is wrong.

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

Pick the correct fix for line 3:

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)

Predict: What does compute(5, 3) return?

public static int compute(int a, int b) {
    if (b == 0) return 0;
    if (b == 1) return a;
    return a + compute(a, b - 1);
}

Practice Exercises

Every construct exercise on this page is linear recursion – a single recursive call advancing toward the base case. Branching examples (Fibonacci, BST traversals, Towers of Hanoi, quicksort) are trace / explain material only; they appear above in the worked examples and the “Where recursion shines” table.

Mark allocations in brackets follow IB CS Paper 2 conventions so students currently following the IB syllabus can calibrate. Readers outside that context can treat them as a guide to the relative weight of each concept.

Core

1. Define the term “recursion” in the context of programming. [2 marks]

2. State the two components that every recursive method must have. [2 marks]

3. Trace the following method call and state the return value: [3 marks]

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

f(7);

4. Write a recursive method public static int sumUpTo(int n) that returns 1 + 2 + ... + n for n >= 1, and 0 when n == 0. [3 marks]

Extension

5. Write a recursive method public static int countMatches(int[] arr, int target, int index) that returns the number of times target appears in arr, starting from position index. The method should be called with index = 0. [4 marks]

6. Write a recursive method public static boolean isPalindrome(String word) that returns true if the word reads the same forwards and backwards. Use charAt() and substring(). [4 marks]

7. Consider the following recursive method:

public static int step(int a, int b) {
    if (a > b) {
        return step(a - 2, b + 1);
    } else if (a == b) {
        return 2 * step(a - 1, b + 2) + 3;
    } else {
        return a + b;
    }
}

(a) Trace the method call step(9, 3). Show each recursive call and the return value at each step. [4 marks]

(b) The method body contains two recursive calls. Explain why this method is classified as linear recursion and not branching recursion. [2 marks]

8. Compare recursion and iteration as approaches to solving repetitive problems. [4 marks]

Exam-Style (14 marks)

9. A recursive method is defined as follows:

public static int compute(int a, int b) {
    if (b == 0) return 0;
    if (b == 1) return a;
    return a + compute(a, b - 1);
}

(a) Trace the method call compute(5, 3). Show each recursive call and the return value at each step. [4 marks]

(b) Describe what the compute method calculates in general terms. [2 marks]

(d) Write an iterative method that produces the same result as compute(a, b). [3 marks]

(e) State one advantage and one disadvantage of the recursive version compared to the iterative version. [2 marks]

(f) Explain what would happen if compute(5, -1) were called. [1 mark]

Homework / Bonus

10. Write a recursive method public static int countDigits(int n) that returns the number of digits in a positive integer (for example, countDigits(4523) returns 4). Hint: the base case is n < 10 (a single digit); the recursive case divides by 10. [3 marks]

Answer sketches

Worked solutions and concept-based mark schemes for every question are in the teacher guide. A few quick pointers for self-checkers:

Q3: f(7) = 7 + 5 + 3 + 1 + 0 = 16. The function sums odd numbers from n down to 1 (for odd n).
Q4: base case n == 0 returns 0, recursive case n + sumUpTo(n - 1). Accept n <= 0 as an equivalent base.
Q7a: step(9, 3) = step(7, 4) = step(5, 5) = 2 * step(4, 7) + 3 = 2 * 11 + 3 = 25. Q7b: two call sites but the if / else-if / else selects exactly one per invocation, so only one recursive call fires per call – linear.
Q9a: compute(5, 3) = 15. Q9f: neither base case is reached (b goes -1, -2, -3, ...); infinite recursion until StackOverflowError.

GitHub Classroom

Practice writing and tracing recursive methods. Every task is linear (single recursive call per invocation) -- branching examples like Fibonacci are on this page for tracing only, not for you to write. Each method must have a clearly identifiable base case and a recursive case that moves toward it.

Codespace Setup Instructions (click to expand)

First Time Setup

Click “Open in GitHub” above, then click the green “Accept this assignment” button
Check the email registered with your GitHub account – click the link there to open your repository. This avoids access issues and means your teacher does not need to share links manually
Wait for your repository to be created, then click “Open in Codespace”
Wait for the Codespace to finish loading (you’ll see VS Code in your browser)

Important: Switch to Standard Mode

Look at the bottom status bar. If it says Java: Lightweight Mode, click on it and select Standard
Wait for Java to finish loading (status bar will say Java: Ready)
Without Standard Mode, the Run button won’t work and you’ll get “Main method not found” errors

Dismiss Popups

You’ll see two notification popups. Dismiss them both:

“Would you like VS Code to periodically run git fetch?” → Click No
“There’s a pull request associated with main” → Click Don’t Show Again

These are housekeeping popups, not part of the assignment.

How to Code

Open src/Factorial.java. This is the only file you need to edit
Complete each // TODO section with a single recursive call (n * factorial(n - 1)) guarded by the base case
Click the Run button (▶ above main) to test your output
Compare your output with the expected output written in the comments above each task

Work through the Core exercises first (factorial, power, countDigits, sumArray, sumUpTo) before moving on to Extension (countMatches, isPalindrome, stringReverse, compute).

How to Check Your Code

You can check your work in two ways:

Option A: Run your code directly

Click the Run button (▶) above main in Factorial.java
Compare your printed output with the expected output shown in the comments above each task

Option B: Run the autograder tests

Open the Terminal (Menu → Terminal → New Terminal)
Type bash run-tests.sh and press Enter
Green ✓ = test passed, Red ✗ = test failed
Each test tells you what it expected. Read the error message to fix your code

How to Submit

Click the Source Control icon (branch icon) in the left sidebar
Type a message like completed tasks in the message box
Click the green Commit button
If asked “stage all changes?” → click Always
Click Sync Changes → if asked about push/pull → click OK, Don’t Show Again
Done! Autograding runs automatically. Your teacher can see your results in the GitHub Classroom dashboard

How to Review Feedback

Go to your repository on GitHub
Click the “Pull requests” tab at the top
Open the pull request called “Feedback”
Click the “Files changed” tab. You’ll see your teacher’s comments on specific lines of your code
Read through each comment carefully, then fix your code in Codespaces
Run bash run-tests.sh in your Codespaces Terminal to check your fixes
Commit and push again (repeat steps 12-17). The autograder will re-run automatically

Connections

Prerequisites: Methods – recursion is a static method that calls itself
Prerequisites: Iteration – recursion is the alternative to loops for repeated work
Prerequisites: 1D Arrays – many recursive examples traverse arrays with an index parameter
Prerequisites: Strings – charAt and substring power the isPalindrome and reverse exercises
Prerequisites: Stacks – the call stack is literally a stack, and StackOverflowError is what happens when it fills
Prerequisites: Big-O Notation – the reason branching recursion (Fibonacci O(2^n)) is so much slower than iteration (O(n))
Related: Searching Algorithms – binary search rewritten recursively with a shrinking (low, high) window
Forward: Quicksort – the canonical divide-and-conquer application; you will trace and describe it, not author it
Forward: Binary Search Trees – insertion, search, and traversal all follow the recursive pattern