Skip to main content

🔴 Unique Paths - Unoptimized Recursive Solution

Understanding the naive approach and why it fails

SERIES NAVIGATION

📘 Unique Paths Series:

  1. 📘 The Discovery Journey - How humans naturally discover the solution
  2. 🔴 Unoptimized Recursive (You are here) - Pure recursion and its exponential complexity
  3. Plain English Proof - Accessible logical reasoning
  4. Formal Proof - Mathematical rigor and certainty
THE PROBLEM (LC 62)

A robot is located at the top-left corner of an m × n grid. The robot can only move either down or right at any point in time.

Goal: How many possible unique paths are there to reach the bottom-right corner?

Example: 3×3 grid → 6 unique paths

Constraints: All cells are reachable (no obstacles)

1. Understanding the Recursive Approach​

The First Instinct​

When you first encounter this problem, the most intuitive approach is often recursive:

"To find the number of paths to reach (i, j), I can sum up:

  • The number of paths to reach the cell above (i-1, j)
  • The number of paths to reach the cell to the left (i, j-1)"

This is a beautiful insight and forms the foundation of the dynamic programming solution. But implementing it naively leads to severe performance issues.

Pure Recursive Implementation​

public class UnoptimizedUniquePaths {
    public int uniquePaths(int m, int n) {
        return countPaths(m - 1, n - 1);
    }

    private int countPaths(int i, int j) {
        // Base case 1: Reached the top row
        if (i == 0) return 1;

        // Base case 2: Reached the leftmost column
        if (j == 0) return 1;

        // Recursive case: sum paths from above and from left
        int pathsFromAbove = countPaths(i - 1, j);  // Count paths from cell above
        int pathsFromLeft = countPaths(i, j - 1);   // Count paths from cell to left

        return pathsFromAbove + pathsFromLeft;
    }
}

Understanding the Recursive Logic​

RECURSIVE BREAKDOWN

Base Cases:

  • If we're in the first row (i == 0): Can only go right → 1 way
  • If we're in the first column (j == 0): Can only go down → 1 way

Recursive Case (with explicit variables for clarity):

// Step 1: Calculate paths from cell above
int pathsFromAbove = countPaths(i - 1, j);

// Step 2: Calculate paths from cell to left
int pathsFromLeft = countPaths(i, j - 1);

// Step 3: Total paths = sum of both
return pathsFromAbove + pathsFromLeft;

Why use explicit variables?

  • Makes the two recursive calls visible and separate
  • Easy to see we're calling the same function twice with different arguments
  • Shows the addition happens AFTER both recursive calls complete
  • Better for debugging - you can inspect each value
  • Clearer mental model of what's happening

Why Addition?

  • Paths from above and paths from left are mutually exclusive
  • They don't overlap (can't come from both simultaneously)
  • Together they cover all possibilities

2. Why It Fails: Visualizing Exponential Complexity​

Small Example: 3×3 Grid​

Let's trace what happens when we call countPaths(2, 2) with explicit variables:

countPaths(2, 2):
    // Not a base case, so continue...
    int pathsFromAbove = countPaths(1, 2);  // First recursive call
    int pathsFromLeft = countPaths(2, 1);   // Second recursive call
    return pathsFromAbove + pathsFromLeft;

Full Execution Tree:

countPaths(2,2)
├─ Step 1: Calculate pathsFromAbove = countPaths(1,2)
│  ├─ Step 1a: pathsFromAbove = countPaths(0,2) → returns 1 ✓
│  ├─ Step 1b: pathsFromLeft = countPaths(1,1)
│  │  ├─ pathsFromAbove = countPaths(0,1) → returns 1 ✓
│  │  └─ pathsFromLeft = countPaths(1,0) → returns 1 ✓
│  │  └─ returns 1 + 1 = 2
│  └─ returns 1 + 2 = 3
│
└─ Step 2: Calculate pathsFromLeft = countPaths(2,1)
   ├─ Step 2a: pathsFromAbove = countPaths(1,1) ← COMPUTED AGAIN!
   │  ├─ pathsFromAbove = countPaths(0,1) → returns 1 ✓
   │  └─ pathsFromLeft = countPaths(1,0) → returns 1 ✓
   │  └─ returns 1 + 1 = 2
   └─ Step 2b: pathsFromLeft = countPaths(2,0) → returns 1 ✓
   └─ returns 2 + 1 = 3

Final: returns 3 + 3 = 6 ✓
THE PROBLEM

Notice that countPaths(1,1) is computed twice!

  • Once when calculating pathsFromAbove for countPaths(1,2)
  • Once when calculating pathsFromAbove for countPaths(2,1)

The explicit variables make it clear:

// Inside countPaths(1,2):
int pathsFromLeft = countPaths(1,1);  // Computes (1,1) → result: 2

// Inside countPaths(2,1):
int pathsFromAbove = countPaths(1,1); // Computes (1,1) AGAIN → result: 2

This is just a 3×3 grid. Imagine a 10×10 or 20×20 grid! 😱

Step-by-Step Execution (Understanding Variables)​

Let's see exactly how the explicit variables help us understand the flow:

// Call: countPaths(2, 2)
countPaths(2, 2) {
    // Check base cases: i=2, j=2 → not a base case

    // Create variable for paths from above
    int pathsFromAbove = countPaths(1, 2);  // ← PAUSE HERE: Must compute this first!

        // Call: countPaths(1, 2)
        countPaths(1, 2) {
            // Check base cases: i=1, j=2 → not a base case

            int pathsFromAbove = countPaths(0, 2);  // ← Base case! Returns 1
            int pathsFromLeft = countPaths(1, 1);   // ← Must compute this

                // Call: countPaths(1, 1)
                countPaths(1, 1) {
                    int pathsFromAbove = countPaths(0, 1);  // Returns 1
                    int pathsFromLeft = countPaths(1, 0);   // Returns 1
                    return 1 + 1 = 2;  // ← RESULT STORED
                }

            return 1 + 2 = 3;  // ← RESULT STORED
        }

    // pathsFromAbove now contains 3

    // Create variable for paths from left
    int pathsFromLeft = countPaths(2, 1);  // ← Now compute this!

        // Call: countPaths(2, 1)
        countPaths(2, 1) {
            int pathsFromAbove = countPaths(1, 1);  // ← RECOMPUTING (1,1)!

                // countPaths(1, 1) executes AGAIN!
                // Returns 2 (same calculation as before)

            int pathsFromLeft = countPaths(2, 0);   // Returns 1
            return 2 + 1 = 3;
        }

    // pathsFromLeft now contains 3

    return pathsFromAbove + pathsFromLeft;  // Returns 3 + 3 = 6
}
KEY INSIGHT

The explicit variables pathsFromAbove and pathsFromLeft show you:

  1. When each recursive call happens (sequentially, not simultaneously)
  2. What value each recursive call returns
  3. Where the repeated calculations occur
  4. How the final result is computed from the two values

Without explicit variables, all of this is hidden in a single line:

return countPaths(i - 1, j) + countPaths(i, j - 1);  // What's happening? 🤔

Complete Recursion Tree​

Here's the full recursion tree for a 3×3 grid (showing all repeated computations):

                    countPaths(2,2)
                    /              \
        countPaths(1,2)          countPaths(2,1)
           /        \                /         \
    countPaths(0,2) countPaths(1,1) countPaths(1,1) countPaths(2,0)
         |           /      \          /      \          |
         1    countPaths(0,1) countPaths(1,0) ...      1
                   |              |
                   1              1

Repeated Subproblems:

  • countPaths(1,1) is computed 2 times
  • countPaths(0,1) is computed 2 times
  • countPaths(1,0) is computed 2 times

For larger grids, some cells are recomputed hundreds or thousands of times!

The Exponential Time Complexity​

TIME COMPLEXITY: O(2^(m+n))

Why exponential?

Each recursive call makes two more calls:

countPaths(i,j) → countPaths(i-1,j) + countPaths(i,j-1)

The recursion tree has approximately:

  • Height: m + n - 2 (number of moves needed)
  • Branches: 2 at each level
  • Total nodes: Approximately 2^(m+n)

In practice:

  • 3×3 grid: ~20 calls
  • 5×5 grid: ~512 calls
  • 10×10 grid: ~524,288 calls
  • 20×20 grid: ~1,099,511,627,776 calls (1 trillion!) 💥
SPACE COMPLEXITY: O(m + n)

The call stack depth is at most m + n - 2:

  • From (m-1, n-1) to (0, 0)
  • Each recursive call reduces either i or j by 1
  • Maximum depth: (m-1) + (n-1) = m + n - 2

This is actually reasonable - the problem is the time complexity!

Empirical Performance Testing​

Let's see how long this takes in practice:

public class PerformanceTest {
    public static void main(String[] args) {
        UnoptimizedUniquePaths solver = new UnoptimizedUniquePaths();

        // Test different grid sizes
        System.out.println("3x3: " + solver.uniquePaths(3, 3));   // Fast
        System.out.println("5x5: " + solver.uniquePaths(5, 5));   // Still fast
        System.out.println("10x10: " + solver.uniquePaths(10, 10)); // Slow
        System.out.println("15x15: " + solver.uniquePaths(15, 15)); // Very slow
        System.out.println("20x20: " + solver.uniquePaths(20, 20)); // ☠️ Don't try this
    }
}

Approximate Running Times:

Grid Size | Approximate Time
----------|------------------
3×3       | < 1 ms
5×5       | < 1 ms
10×10     | ~100 ms
15×15     | ~30 seconds
20×20     | ~2 hours
25×25     | ~several days

The Core Problem: Overlapping Subproblems​

REPEATED WORK

The recursive solution recalculates the same subproblem multiple times.

Example: For countPaths(4,4), the cell (2,2) might be computed in dozens of different ways:

countPaths(4,4) → ... → countPaths(2,2)
countPaths(4,4) → ... → countPaths(2,2) ← REPEATED!
countPaths(4,4) → ... → countPaths(2,2) ← REPEATED!
...

Each path to (2,2) in the recursion tree recomputes the entire subtree below it!

Visual Comparison​

┌──────────────────────────────────────────────────────┐
│  UNOPTIMIZED RECURSION                               │
│                                                       │
│  ✗ Recomputes same cells many times                 │
│  ✗ Exponential time: O(2^(m+n))                     │
│  ✓ Simple to understand                              │
│  ✓ Directly mirrors the problem logic               │
│                                                       │
│  Example: 10×10 grid                                 │
│    Calls: ~524,288                                   │
│    Time: ~100 ms                                     │
│    Space: O(m+n) - call stack                        │
└──────────────────────────────────────────────────────┘

vs.

┌──────────────────────────────────────────────────────┐
│  DYNAMIC PROGRAMMING (Coming Next)                   │
│                                                       │
│  ✓ Each cell computed exactly once                   │
│  ✓ Linear time: O(m×n)                              │
│  ✓ Can optimize space to O(n)                        │
│  ✗ Requires understanding DP                         │
│                                                       │
│  Example: 10×10 grid                                 │
│    Cells: 100                                        │
│    Time: < 1 ms                                      │
│    Space: O(m×n) or O(n)                             │
└──────────────────────────────────────────────────────┘

3. Practical Application & Key Takeaways​

When Pure Recursion Makes Sense​

Despite its inefficiency, pure recursion is valuable for:

  1. Understanding the Problem

    • It directly mirrors the problem's recursive structure
    • Easiest to understand and explain

  2. Small Inputs

    • For tiny grids (3×3, 4×4), the performance difference is negligible
    • Good for testing and validation

  3. Interview Communication

    • Starting with recursion shows you understand the problem
    • Natural stepping stone to the DP solution

  4. Educational Purposes

    • Demonstrates why we need dynamic programming
    • Shows the importance of recognizing overlapping subproblems

The Learning Path​

THE NATURAL PROGRESSION
1. Pure Recursion (This Document)
   ↓
   [Recognize repeated subproblems]
   ↓
2. Recursion with Memoization
   ↓
   [Convert to iterative]
   ↓
3. Bottom-Up DP (2D Array)
   ↓
   [Optimize space]
   ↓
4. Space-Optimized DP (1D Array)

Each step builds on the previous one!

Complete Working Code​

Full Implementation with Comments​

/**
 * Unoptimized Recursive Solution for Unique Paths
 *
 * Time Complexity: O(2^(m+n)) - EXPONENTIAL!
 * Space Complexity: O(m+n) - Call stack depth
 *
 * WARNING: Do not use for grids larger than 10×10!
 */
public class UnoptimizedUniquePaths {

    /**
     * Main entry point
     * @param m number of rows
     * @param n number of columns
     * @return number of unique paths from (0,0) to (m-1,n-1)
     */
    public int uniquePaths(int m, int n) {
        // Convert to 0-indexed
        return countPaths(m - 1, n - 1);
    }

    /**
     * Recursive helper function
     * @param i current row (0-indexed)
     * @param j current column (0-indexed)
     * @return number of ways to reach (i,j) from (0,0)
     */
    private int countPaths(int i, int j) {
        // Base case 1: First row - can only go right
        if (i == 0) {
            return 1;
        }

        // Base case 2: First column - can only go down
        if (j == 0) {
            return 1;
        }

        // Recursive case: sum paths from above and from left
        // EXPLICIT VARIABLES make it easier to understand!
        int pathsFromAbove = countPaths(i - 1, j);  // How many ways to reach cell above?
        int pathsFromLeft = countPaths(i, j - 1);   // How many ways to reach cell to left?

        // Total paths = paths from above + paths from left
        return pathsFromAbove + pathsFromLeft;
    }

    /**
     * Test the implementation
     */
    public static void main(String[] args) {
        UnoptimizedUniquePaths solver = new UnoptimizedUniquePaths();

        // Small test cases (safe to run)
        System.out.println("3×3 grid: " + solver.uniquePaths(3, 3));  // Expected: 6
        System.out.println("3×7 grid: " + solver.uniquePaths(3, 7));  // Expected: 28
        System.out.println("5×5 grid: " + solver.uniquePaths(5, 5));  // Expected: 70

        // Larger cases (use with caution!)
        // System.out.println("10×10 grid: " + solver.uniquePaths(10, 10));
        // System.out.println("15×15 grid: " + solver.uniquePaths(15, 15));
    }
}

Adding Debug Output​

To see the repeated calculations in action:

public class DebugUniquePaths {
    private int callCount = 0;

    public int uniquePaths(int m, int n) {
        callCount = 0;
        int result = countPaths(m - 1, n - 1);
        System.out.println("Total function calls: " + callCount);
        return result;
    }

    private int countPaths(int i, int j) {
        callCount++;
        System.out.println("Computing countPaths(" + i + ", " + j + ")");

        if (i == 0 || j == 0) {
            return 1;
        }

        int pathsFromAbove = countPaths(i - 1, j);
        int pathsFromLeft = countPaths(i, j - 1);
        return pathsFromAbove + pathsFromLeft;
    }

    public static void main(String[] args) {
        DebugUniquePaths solver = new DebugUniquePaths();

        System.out.println("\n=== 3×3 Grid ===");
        System.out.println("Result: " + solver.uniquePaths(3, 3));
    }
}

Output for 3×3:

=== 3×3 Grid ===
Computing countPaths(2, 2)
Computing countPaths(1, 2)
Computing countPaths(0, 2)
Computing countPaths(1, 1)
Computing countPaths(0, 1)
Computing countPaths(1, 0)
Computing countPaths(2, 1)
Computing countPaths(1, 1)  ← REPEATED!
Computing countPaths(0, 1)  ← REPEATED!
Computing countPaths(1, 0)  ← REPEATED!
Computing countPaths(2, 0)
Total function calls: 11
Result: 6

Key Takeaways​

CORE INSIGHTS

  1. The Recursive Formula is Beautiful:

    paths(i,j) = paths(i-1,j) + paths(i,j-1)

    This insight is the foundation of the solution.

  2. But Naive Implementation is Exponential:

    • O(2^(m+n)) time complexity
    • Repeated subproblems kill performance
    • Unusable for grids larger than ~15×15

  3. This is Why We Need Dynamic Programming:

    • DP solves each subproblem exactly once
    • Stores results to avoid recomputation
    • Reduces time from exponential to polynomial

  4. The Pattern Recognition:

    • When you see overlapping subproblems
    • And optimal substructure (optimal solution uses optimal subsolutions)
    • Think: Dynamic Programming!

  5. Explicit Variables Aid Understanding:

    • Makes recursive calls visible and trackable
    • Shows when and how values are computed
    • Essential for debugging and learning
    • Transforms complex one-liners into clear steps

Next Steps​

Now that you understand why the naive recursion fails, you're ready to learn how to fix it:

  1. Add Memoization - Cache results to avoid recomputation
  2. Convert to Bottom-Up DP - Build solutions iteratively
  3. Optimize Space - Use only O(n) space instead of O(m×n)

Each optimization builds on your understanding of this recursive foundation!

THE FOUNDATION

Understanding this unoptimized solution is essential for truly grasping dynamic programming.

The best engineers don't just memorize DP patterns - they understand why recursion fails and how DP fixes it! 🚀

Practice Problems​

Understanding Questions​

  1. Why does the recursion tree have exponential nodes?

    Click for answer

    Each call branches into two more calls, creating a binary tree structure. With depth approximately m+n, we get roughly 2^(m+n) nodes.

  2. What's the maximum depth of the recursion?

    Click for answer

    Maximum depth is m + n - 2 because we need to reduce i from m-1 to 0 and j from n-1 to 0.

  3. How many times is countPaths(5, 5) computed in countPaths(7, 7)?

    Click for answer

    It's computed C(4, 2) = 6 times - once for each unique path from (7,7) to (5,5) in the recursion tree.

Modification Challenges​

  1. Add a counter to track how many times each cell is computed
  2. Modify to return the actual paths, not just the count
  3. Add memoization to avoid repeated calculations

Remember: This solution is "bad" in terms of performance, but essential for understanding. Master this, and the DP optimization will make perfect sense! 💡