Master Recursion: From Basics to Advanced Techniques with Time‑Complexity Insights

Introduction

Recursion is a fundamental algorithmic technique used in problems ranging from simple factorial calculations to complex graph algorithms such as PageRank, and it is a favorite topic in technical interviews.

Many existing tutorials omit rigorous analysis of time and space complexity, which are essential for evaluating algorithmic efficiency.

What Is Recursion?

Recursion occurs when a function calls itself. For example, the classic factorial function calls factorial(n‑1) inside its own definition.

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

The process can be visualized as repeatedly breaking a problem into smaller sub‑problems until reaching a base case that can be solved directly.

General Recursive Solution Approach

The four‑step method for solving recursive problems is:

Define a function and clearly state its purpose.

Derive the recurrence relation that links the problem to its sub‑problems.

Implement the recurrence in code, adding the base case.

Analyze the time and space complexity; if the complexity is unacceptable, consider alternative approaches.

Practical Exercises

Warm‑up: Factorial

Input a positive integer n and output n! .

Define the function factorial that computes n!.

/**
 * Compute n!
 */
public int factorial(int n) {
    if (n <= 1) return 1;
    return n * factorial(n - 1);
}

Time complexity: O(n) multiplications.

Introductory Problem: Frog Jump

A frog can jump either 1 or 2 steps. How many distinct ways are there to reach step n ?

Define int f(int n) representing the number of ways.

public int f(int n) {
    if (n == 1) return 1;
    if (n == 2) return 2;
    return f(n - 1) + f(n - 2);
}

Time complexity of the naive recursion is exponential; using memoization (store intermediate results) reduces it to O(n) time and O(n) space, or O(1) space with an iterative bottom‑up version.

public int f(int n) {
    if (n == 1) return 1;
    if (n == 2) return 2;
    int a = 1, b = 2, c = 0;
    for (int i = 3; i <= n; i++) {
        c = a + b;
        a = b;
        b = c;
    }
    return c;
}

Intermediate Problem: Invert Binary Tree

Given a binary tree, invert it so that left and right children are swapped at every node.

public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

public TreeNode invertTree(TreeNode root) {
    if (root == null) return null;
    TreeNode left = invertTree(root.left);
    TreeNode right = invertTree(root.right);
    root.left = right;
    root.right = left;
    return root;
}

Time complexity: O(n) where n is the number of nodes. Space complexity equals the recursion depth, i.e., O(h) where h is the tree height (O(log n) for balanced trees, O(n) for degenerate trees).

Advanced Problem: Tower of Hanoi

Move n disks from peg A to peg C using peg B as auxiliary, moving one disk at a time and never placing a larger disk on a smaller one.

public void hanoi(int n, char from, char aux, char to) {
    if (n <= 0) return;
    hanoi(n - 1, from, to, aux);
    move(from, to);
    hanoi(n - 1, aux, from, to);
}

private void move(char a, char b) {
    System.out.printf("%c->%c
", a, b);
}

The recurrence is T(n) = 2·T(n‑1) + 1, yielding a time complexity of O(2^n) and a recursion depth of n.

Challenge: Cellular Division Model

A cell divides once per hour, producing one new cell; after three hours it dies. How many cells exist after n hours?

The model uses three states (A: newborn, B: one‑hour old, C: two‑hour old) with the following recurrences: aCell(n) = aCell(n‑1) + bCell(n‑1) + cCell(n‑1) (base case aCell(1)=1) bCell(n) = aCell(n‑1) (base case bCell(1)=0) cCell(n) = bCell(n‑1) (base case cCell(1)=cCell(2)=0)

public int allCells(int n) {
    return aCell(n) + bCell(n) + cCell(n);
}

public int aCell(int n) {
    if (n == 1) return 1;
    return aCell(n-1) + bCell(n-1) + cCell(n-1);
}

public int bCell(int n) {
    if (n == 1) return 0;
    return aCell(n-1);
}

public int cCell(int n) {
    if (n == 1 || n == 2) return 0;
    return bCell(n-1);
}

The overall recurrence leads to exponential growth, so the time complexity is also exponential.

Conclusion

Most recursive problems follow a recognizable pattern. By applying the four‑step method—defining the function, deriving the recurrence, coding it, and analyzing complexity—one can systematically solve a wide range of tasks. For harder problems, drawing diagrams and experimenting with small cases often reveal the underlying recurrence, enabling efficient implementations.