Understanding Recursion: Concepts, Complexity Analysis, and Practical Examples

Preface

Recursion is a crucial concept in algorithms, widely used from simple factorial calculations to large‑scale applications such as Google’s PageRank; it is also a favorite interview topic.

Many existing articles on recursion lack comprehensive coverage, especially regarding time and space complexity, which are essential for evaluating algorithms. This article aims to fill that gap by providing a systematic analysis of recursion complexity and a general solution framework.

The article will cover:

What recursion is

A universal approach to solving recursive problems

Hands‑on exercises ranging from beginner to advanced levels

The goal is to elevate readers’ understanding of recursion, with a detailed focus on time‑complexity analysis and a reusable method for deriving it.

What is Recursion

In simple terms, recursion occurs when a function calls itself.

For example, the factorial function calls factorial(n‑1) inside its definition:

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

The essence of recursion is to break a problem into smaller sub‑problems (the “divide” step) until reaching a base case that can be solved directly, then combine the results while unwinding the call stack (the “conquer” step).

General Recursive Problem‑Solving Process

Two key characteristics of recursive problems:

The problem can be decomposed into sub‑problems that share the same solution strategy and can invoke the same function.

There exists a terminating condition that stops further decomposition; without it, the recursion would be infinite.

Once a problem is confirmed to be suitable for recursion, the following four‑step framework can be applied:

Define a function and clearly state its purpose.

Derive the recurrence relation between the original problem and its sub‑problems.

Implement the recurrence relation in code, completing the function.

Analyze the time (and optionally space) complexity; if the complexity is unacceptable, transform the approach.

Hands‑On Exercises (From Beginner to Advanced)

Warm‑up: Factorial

Input a positive integer n and output n! (where n! = 1 × 2 × … × n ).

Applying the four‑step method:

Define the function factorial that computes n! .

/** * Compute n! */
public int factorial(int n) {
}

Recurrence: f(n) = n * f(n‑1) with base case f(1) = 1 .

Implement the recurrence:

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

Time complexity: O(n) because the function performs n multiplications.

Entry‑Level: Climbing Stairs

A frog can jump either 1 or 2 steps at a time. How many distinct ways are there to reach the n ‑th step?

Four‑step solution:

Define f(n) as the number of ways to reach step n .

/** * Number of ways to reach step n */
public int f(int n) {
}

Recurrence: f(n) = f(n‑1) + f(n‑2) with base cases f(1)=1 , f(2)=2 .

Implement:

/** * Number of ways to reach step n */
public int f(int n) {
    if (n == 1) return 1;
    if (n == 2) return 2;
    return f(n - 1) + f(n - 2);
}

Time complexity is exponential (≈O(2ⁿ)). To improve, memoize results:

public int f(int n) {
    if (n == 1) return 1;
    if (n == 2) return 2;
    if (map.get(n) != null) return map.get(n);
    return map.put(n, f(n - 1) + f(n - 2));
}

With memoization, time complexity becomes O(n) and space O(n). An iterative version reduces space to O(1):

public int f(int n) {
    if (n == 1) return 1;
    if (n == 2) return 2;
    int pre = 1, next = 2, result = 0;
    for (int i = 3; i <= n; i++) {
        result = pre + next;
        pre = next;
        next = result;
    }
    return result;
}

Intermediate: Invert Binary Tree

Given a binary tree, swap the left and right children of every node.

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

public TreeNode invertTree(TreeNode root) {
}

Recurrence: invert(root) = invert(root.left) + invert(root.right) with termination when root == null .

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

Time complexity O(n); space complexity equals the recursion depth, O(log n) for a balanced tree and O(n) in the worst case.

Advanced: Tower of Hanoi

Move n disks from peg A to peg C using peg B as auxiliary, obeying the rule that a larger disk cannot be placed on a smaller one.

// Move n disks from a to c via b
public void hanoid(int n, char a, char b, char c) {
    if (n <= 0) return;
    hanoid(n-1, a, c, b);
    move(a, c);
    hanoid(n-1, b, a, c);
}

public void move(char a, char b) {
    printf("%c->%c\n", a, b);
}

Recurrence: f(n) = 2·f(n‑1) + 1 , yielding time complexity O(2ⁿ).

Challenge: Cell Division Model

A cell divides once per hour, lives for three hours, then dies. The article derives a three‑state recurrence ( aCell , bCell , cCell ) and combines them to compute the total number of cells after n hours.

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

// a‑state
public int aCell(int n) {
    if (n == 1) return 1;
    else return aCell(n-1) + bCell(n-1) + cCell(n-1);
}

// b‑state
public int bCell(int n) {
    if (n == 1) return 0;
    else return aCell(n-1);
}

// c‑state
public int cCell(int n) {
    if (n == 1 || n == 2) return 0;
    else return bCell(n-1);
}

The resulting recurrence leads to exponential time complexity, similar to the Fibonacci‑type problems.

Conclusion

Most recursive problems follow a recognizable pattern; by applying the four‑step framework—understanding the problem, formulating a recurrence, implementing it, and analyzing complexity—one can solve a wide range of tasks. Visualizing the recursion tree, using memoization, or converting to an iterative solution are effective strategies for optimization.

If you found this article helpful, feel free to give it a “like”.