Recursion (HL)

How Recursion Works

1. Define a Base Case: The simplest instance (e.g. factorial(0) = 1) where no further recursion is needed.
2. Define the Recursive Case: Express the problem in terms of a smaller instance (e.g. factorial(n) = n × factorial(n–1)).
3. Break Down: Each call reduces the problem size until the base case is reached.
4. Unwind: Once the base case is reached, return values propagate back up the call chain to build the final result.

Analogies:

• Russian nesting dolls: To open the largest doll, you open each one inside it until you reach the smallest, then reverse the process.
• (Fractal) tree drawing: Draw a branch, then recursively draw smaller branches at its end, and so on.

Advantages and Limitations of Recursion

Example: Recursive Quicksort

Algorithm Steps (Quicksort)

1. Choose a pivot element.
2. Partition remaining elements into left (≤ pivot) and right (> pivot) lists.
3. Recursively sort left and right sublists.
4. Concatenate sorted left, pivot(s), and sorted right.

• Python
• Java

def quicksort(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[len(arr)//2]
    left   = [x for x in arr if x < pivot]
    middle = [x for x in arr if x == pivot]
    right  = [x for x in arr if x > pivot]
    return quicksort(left) + middle + quicksort(right)

numbers = [10, 3, 8, 6, 7, 5]
print("Sorted Array:", quicksort(numbers))

import java.util.Arrays;

public class QuickSort {
    public static void quickSort(int[] arr, int low, int high) {
        if (low < high) {
            int pi = partition(arr, low, high);
            quickSort(arr, low, pi - 1);
            quickSort(arr, pi + 1, high);
        }
    }

    private static int partition(int[] arr, int low, int high) {
        int pivot = arr[high];
        int i = low - 1;
        for (int j = low; j < high; j++) {
            if (arr[j] < pivot) {
                i++;
                int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp;
            }
        }
        int temp = arr[i + 1]; arr[i + 1] = arr[high]; arr[high] = temp;
        return i + 1;
    }

    public static void main(String[] args) {
        int[] numbers = {10, 3, 8, 6, 7, 5};
        quickSort(numbers, 0, numbers.length - 1);
        System.out.println("Sorted Array: " + Arrays.toString(numbers));
    }
}

Example: Recursive and Iterative Factorial

Algorithm Steps (Factorial)

1. Recursive:
   • If n == 0 → return 1 (base case).
   • Else → return n × factorial(n–1).
2. Iterative:
   • Initialise result = 1.
   • Loop i from 1 to n, multiply result by i each time.
   • Return result.

Visualisation

• Factorial, Recursive

• Python
• Java

def factorial(n):
    if n == 0:
        return 1
    return n * factorial(n - 1)

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

def factorial_iterative(n):
    result = 1
    for i in range(1, n + 1):
        result *= i
    return result

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

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

public class IterativeFactorial {
    public static int factorial(int n) {
        int result = 1;
        for (int i = 1; i <= n; i++) {
            result *= i;
        }
        return result;
    }
    public static void main(String[] args) {
        System.out.println("Factorial: " + factorial(5));
    }
}

EXTENSION: Memoised vs Iterative DP (Fibonacci)

The naive recursive Fibonacci (calling fib(n-1) and fib(n-2) each time) repeats work, so time grows exponentially (about O(2^n)) and the call stack can get deep (O(n)). Memoised recursion keeps the same top-down shape but caches results so each n is solved once - time O(n), still uses recursion so stack O(n). Iterative DP (Dynamic Programming) builds values in a simple loop from F(0) and F(1) - also O(n) time, but with only constant extra space (O(1)) and no recursion overhead.

• Memoised (top-down): recursion + cache → time O(n), stack O(n).
• Iterative DP (bottom-up): loop only → time O(n), stack O(1).

• Python
• Java

# Python - Memoised recursion (top-down DP)
from functools import lru_cache

@lru_cache(maxsize=None)
def fib(n: int) -> int:
    if n < 2:
        return n
    return fib(n-1) + fib(n-2)

# Python - Iterative DP (bottom-up)
def fib_it(n: int) -> int:
    a, b = 0, 1
    for _ in range(n):
        a, b = b, a + b
    return a

// Java - Memoised recursion (top-down DP)
static int fibMemo(int n, int[] memo) {
    if (n < 2) return n;
    if (memo[n] != -1) return memo[n];
    return memo[n] = fibMemo(n - 1, memo) + fibMemo(n - 2, memo);
}

// Java - Iterative DP (bottom-up)
static int fibIt(int n) {
    int a = 0, b = 1;
    for (int i = 0; i < n; i++) {
        int next = a + b;
        a = b;
        b = next;
    }
    return a;
}

Applications of Recursion

• Sorting: Quicksort, mergesort.
• Tree Traversal: In-order, pre-order, post-order of binary trees.
• Graph Traversal: Depth-first search (DFS).
• Fractal Generation: Drawing self-similar patterns.
• Mathematical: Fibonacci, factorials, exponentiation.