Compose & Trace Recursive Algorithms (HL)

How Recursive Algorithms Work

Each recursive function follows two parts:

• Base Case: The simplest instance that returns a direct result (e.g. n == 0).
• Recursive Case: The function calls itself with a smaller or simpler argument.

Example: Recursive Factorial Function

• Python
• Java

def factorial(n):
    if n == 0:
        return 1   # Base case
    return n * factorial(n - 1)   # Recursive case

print("Factorial:", factorial(5))

public class RecursionExample {
    public static int factorial(int n) {
        if (n == 0) return 1;   // Base case
        return n * factorial(n - 1);   // Recursive case
    }
    public static void main(String[] args) {
        System.out.println("Factorial: " + factorial(5));
    }
}

Tracing factorial(5)

How to Trace factorial(5)

1. Recall the rule: factorial(n) = n × factorial(n−1) with base case factorial(1) = 1 (or factorial(0) = 1).
2. Walk down the calls: record each call factorial(5) → factorial(4) → factorial(3) → factorial(2) → factorial(1).
3. At the base case, return 1.
4. Walk up the stack: for each waiting call, compute n × (return from below) and record that value.
5. Continue until the original call returns 120.

Example: Sum of N Natural Numbers

• Python
• Java

def sum_n(n):
    if n == 0:
        return 0   # Base case
    return n + sum_n(n - 1)   # Recursive case

print("Sum:", sum_n(5))

public class RecursiveSum {
    public static int sumN(int n) {
        if (n == 0) return 0;        // Base case
        return n + sumN(n - 1);      // Recursive case
    }

    public static void main(String[] args) {
        System.out.println("Sum: " + sumN(5));
    }
}

Tracing sum_n(5)

How to Trace sum_n(5)

1. Recall the rule: sum_n(n) = n + sum_n(n−1) with base case sum_n(0) = 0 (or sum_n(1) = 1).
2. Walk down the calls: sum_n(5) → sum_n(4) → sum_n(3) → sum_n(2) → sum_n(1) → base.
3. At the base, return 0.
4. Walk up the stack: at each level compute n + (return from below) and update “Accumulated Sum” (e.g. 0 → 1 → 3 → 6 → 10 → 15).
5. The original call returns 15.

Avoiding Common Errors

• Missing Base Case: Always define and test the simplest case (eg n == 0), or risk infinite recursion.
• Excessive Calls: Cache results when possible (memoisation) to avoid redundant work.
• Stack Overflow: Keep recursion depth reasonable or convert to iterative solutions when you hit limits.