DSA sheet · Recursion · Non-linear recursion

Unique Paths

This is the third problem in the non-linear recursion pattern, after Fibonacci and Climbing Stairs. It's really a DP (dynamic programming) problem, but the teacher uses it to practise the same journey once more: write the two-call recursion, see it repeat work, then save answers (memoisation) so it passes. It's a grid version of Climbing Stairs: instead of "how many ways to reach step n", it asks "how many ways to reach the last cell".

Every part below follows the same order:
① the question in simple words → ② what the constraints tell us → ③ intuition → ④ building the logic from examples → ⑤ approach steps → ⑥ code → ⑦ code line by line → ⑧ dry run → ⑨ complexity & remember

• Part 0 · Recursion from scratch
• Part A · Unique Paths with plain recursion
• Part B · Unique Paths with memoisation (DP)
• Part C · Revision page

Part 0 · Recursion from scratch

A function that calls itself

Recursion = a function solves a problem by calling itself on a smaller version of the same problem, and builds its answer from that smaller answer.

Base case: the stop sign

The base case is an input so small that the answer is known without any further call. Every chain of calls must eventually reach one. Without it, the calls go on forever. Python keeps every unfinished call in memory, and after about 1000 of them it stops with RecursionError. (sys.setrecursionlimit can raise the limit for correct-but-deep recursion. It can't fix a missing base case.) In this problem the depth is at most m + n ≈ 200, so the default limit is fine.

Recursive case and the leap of faith

The recursive case calls the function on smaller inputs and combines the results. While writing it, trust that the smaller calls return correct answers (the "leap of faith"). You only check three things: the base case is right, each call moves toward the base case, and you combine the answers correctly.

The call stack

Each call gets a frame (its own variables). A call pushes a frame on top of the call stack. A return pops it and hands the answer to the frame below, which was paused waiting. Only the top frame runs.

Way down vs. way back up

Code before the recursive call runs on the way down. Code after it runs on the way back up, once the smaller answers have returned. Here, adding the two path counts happens on the way back up. Saving into the memo table also happens on the way back up.

Linear vs. non-linear

If a function calls itself once, the calls form a line (linear recursion). If it calls itself twice, they form a tree (non-linear recursion), and the same smaller question often appears in several branches. That repeat is called an overlapping subproblem, and saving answers to skip the repeats is memoisation, the start of DP.

Part A · Unique Paths with plain recursion

LeetCode 62

1The question in simple words

A robot stands on the top-left cell (0, 0) of a grid with m rows and n columns. It wants to reach the bottom-right cell (m−1, n−1). At each move it can go only right or down. No left, no up, no diagonal. How many different paths are there?

Just like Climbing Stairs, we're not counting moves or turns. We're counting how many different routes exist.

  m = 3 rows, n = 7 columns
  S . . . . . .        S = start (0,0)
  . . . . . . .        E = end (2,6)
  . . . . . . E        answer: 28 paths

2What the constraints tell us

• 1 ≤ m, n ≤ 100 → m or n can be 1, so a grid can be a single row, a single column, or even a single cell.
• The grid can have 100 × 100 = 10⁴ cells. The teacher's estimate: the plain recursion is like 2 to the power of (number of cells), so 2^(10⁴). Way beyond 2³⁰ → TLE for sure. We must optimise with DP.
• LeetCode also promises the answer is at most 2×10⁹, so it fits in an int. (That means the real tests never use a grid that is huge in both directions: 100 × 100 would have about 2.3×10⁵⁸ paths. Python ints don't overflow, so our code would still give the exact number.)

3Intuition: where can you come from?

Stand on any cell. Since the robot only moves right or down, it can only have arrived from the cell above (moving down) or the cell to the left (moving right). So:

This is Climbing Stairs again: there, step n could be reached from n−1 or n−2. Here, cell (r, c) can be reached from (r−1, c) or (r, c−1). Two choices → two calls → non-linear recursion.

4Building the logic from small grids (the way the teacher does)

Forget the big grid. Start with the smallest ones the constraints allow.

1 × 1 grid

You're already standing on the target. The only "path" is don't move → 1 way.

1 × 2 grid, or 2 × 1 grid

One move (right, or down) → 1 way.

2 × 2 grid

  S → .        path 1: right, down
  ↓   ↓        path 2: down, right
  . → E        (diagonal is not allowed)  → 2 ways

A long single row (or single column)

Whether the row has 3, 4 or 5 cells, there's still only one path: keep going straight. So every cell in row 0 has 1 way, and every cell in column 0 has 1 way.

Filling a 2 × 4 grid by hand

Row 0 and column 0 are all 1. Now count the other cells:

  col:   0   1   2   3
  row 0: 1   1   1   1
  row 1: 1   2   3   4

• (1,1): from above (1) + from left (1) = 2. These are the 2×2 paths.
• (1,2): count by hand: right-right-down, down-right-right, right-down-right = 3. The formula gives 1 (above) + 2 (left) = 3 ✓.
• (1,3): by hand: R R R D · D R R R · R D R R · R R D R = 4. The formula gives 1 + 3 = 4 ✓.

So the pattern the teacher spots, "1 + 1 = 2, 2 + 1 = 3, 3 + 1 = 4", is exactly up + left.

Base case

If row == 0 or col == 0, the answer is 1 (straight line). This also covers the 1 × 1 grid (0, 0).

Where to start the call: (m−1, n−1)

The input gives the size m × n, but indexes start at 0, so the target cell is (m - 1, n - 1). Call the helper with those.

5Approach steps

1. Define count_paths(row, col) = the number of paths from (0,0) to (row, col).
2. If row == 0 or col == 0 → return 1.
3. Otherwise → return count_paths(row-1, col) + count_paths(row, col-1).
4. The answer is count_paths(m-1, n-1).

6Code (Python)

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        return self.count_paths(m - 1, n - 1)        # 0-based target cell

    def count_paths(self, row, col):
        if row == 0 or col == 0:                     # top row / left column
            return 1
        return self.count_paths(row - 1, col) + self.count_paths(row, col - 1)

7Code line by line

8Dry run: m = 3, n = 3 → count_paths(2, 2)

Each node shows (row,col) = paths. Red = a repeated subproblem.

                        (2,2)=6
                    /             \
             (1,2)=3                (2,1)=3
             /     \                /      \
       (0,2)=1    (1,1)=2      (1,1)=2     (2,0)=1
                  /     \       /     \
             (0,1)=1  (1,0)=1 (0,1)=1 (1,0)=1

1. (2,2): not on an edge → calls the cell above, (1,2), first. (2,2) waits.
2. (1,2) → calls (0,2): row 0 → returns 1.
3. (1,2) → calls (1,1) → calls (0,1) → 1, then (1,0) → 1. (1,1) returns 1 + 1 = 2.
4. (1,2) = 1 + 2 = 3, returned to (2,2).
5. (2,2) → calls the left cell (2,1) → calls (1,1). (1,1) was already solved in step 3, but nothing remembers it, so the whole subtree runs again → 2.
6. (2,1) → calls (2,0) → column 0 → 1. (2,1) = 2 + 1 = 3.
7. (2,2) = 3 + 3 = 6. Stack empty. Answer 6 ✓

The stack is at most (m−1)+(n−1)+1 = 5 frames tall here: each frame is one step closer to an edge.

9Complexity & remember

• Counting calls: 3 × 3 → 11 calls. 3 × 7 (answer 28) → 55 calls. In general the calls are 2 × answer − 1, because every leaf returns 1 (so there are "answer" leaves) and every inner call has exactly 2 children. Even a 17 × 17 grid (answer ≈ 6×10⁸, inside LeetCode's limit) needs over 10⁹ calls.
• Time: exponential. The teacher calls it O(2^N) with N = number of cells. A tighter bound is O(2^(m+n)). Both mean TLE, which is what happens when she submits it.
• Space O(m + n): the deepest chain of waiting calls.

Part B · Unique Paths with memoisation (DP)

1The question, and what changes

Same question, same rule, same base case. The only problem was the repeats. In the dry run, (2,1) asked (1,1) for its answer, even though (1,2) had already worked out (1,1) a moment earlier. If (1,1) had written its answer down, (2,1) could just read it.

2Constraints, again

m, n ≤ 100 → at most 10⁴ different cells. If each cell is solved only once, that's at most 10⁴ real computations: very fast. A 100 × 100 table is small in memory too.

3Intuition: a grid notebook

Make a 2D table dp the same size as the grid (m × n), filled with 0. When a call finishes computing a cell, it writes the answer into dp[row][col] before returning. When a call starts, after the base case, it first checks the table: if the cell isn't 0, it returns the saved value straight away.

4Building the code from Part A

The teacher changes only four things:

1. Create dp of size m × n, all 0.
2. Pass dp into the helper (and into every recursive call. On screen she first forgot one, got an error, and fixed it).
3. After the base case: if dp[row][col] != 0, return it.
4. Instead of returning the sum directly, store it in dp[row][col], then return it.

5Approach steps

1. dp = m × n table of zeros.
2. count_paths(row, col, dp): if row == 0 or col == 0 → return 1.
3. If dp[row][col] != 0 → return dp[row][col].
4. dp[row][col] = count_paths(row−1, col, dp) + count_paths(row, col−1, dp).
5. Return dp[row][col]. The answer is count_paths(m−1, n−1, dp).

6Code (Python)

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        dp = [[0] * n for _ in range(m)]             # m x n notebook, 0 = not solved
        return self.count_paths(m - 1, n - 1, dp)

    def count_paths(self, row, col, dp):
        if row == 0 or col == 0:                     # base case
            return 1
        if dp[row][col] != 0:                        # solved before? reuse it
            return dp[row][col]
        dp[row][col] = (self.count_paths(row - 1, col, dp)
                        + self.count_paths(row, col - 1, dp))   # solve once, save
        return dp[row][col]

7Code line by line

8Dry run: m = 3, n = 3 with the notebook

                      (2,2)=6  save
                   /             \
          save (1,2)=3          save (2,1)=3
             /     \               /        \
       (0,2)=1  save (1,1)=2   (1,1) memo hit 2  (2,0)=1
                  /     \
             (0,1)=1  (1,0)=1          9 calls instead of 11

1. (2,2): not an edge, dp[2][2] = 0 → go to (1,2).
2. (1,2) → (0,2) = 1 → (1,1) → (0,1) = 1, (1,0) = 1 → dp[1][1] = 2 saved.
3. (1,2) = 1 + 2 → dp[1][2] = 3 saved.
4. (2,2) → (2,1) → asks (1,1): dp[1][1] = 2 is not 0 → return 2 at once, no children.
5. (2,1) → (2,0) = 1 → dp[2][1] = 3 saved.
6. (2,2) = 3 + 3 → dp[2][2] = 6 → answer 6 ✓

The notebook at the end (cells the code never writes, the edges, stay 0 because the base case answers them directly):

  dp after the run      what each cell means
  0  0  0               1  1  1
  0  2  3               1  2  3
  0  3  6               1  3  6   ← answer

9Complexity & remember

• Time O(m · n): each cell is computed at most once, and each computation does O(1) work plus at most 2 calls (one of which may be a quick lookup). The teacher: previous cells have already saved their answers, so we don't go back down the recursion.
• Space O(m · n) for the table, plus O(m + n) for the call stack.
• 100 × 100 → about 10⁴ cells → passes easily.

Part C · Revision page

s = Solution()
print(s.uniquePaths(3, 7))     # 28
print(s.uniquePaths(3, 2))     # 3
print(s.uniquePaths(3, 3))     # 6
print(s.uniquePaths(1, 1))     # 1
print(s.uniquePaths(1, 5))     # 1
# memoised version only (plain recursion would never finish):
# print(s.uniquePaths(100, 100))

Based on this video: Unique Paths | Non-Linear Recursion & Memoisation