DSA sheet · Recursion · Pattern 2

Non-Linear Recursion

This video teaches the second recursion pattern: a function that calls itself more than once. In the previous pattern (linear recursion, e.g. factorial) each call made only one new call, so the calls formed a straight line. Here each call makes two calls, so the calls spread out like a tree. The teacher shows why that tree is slow (the same small problems get solved again and again), and how saving answers (memoisation / DP) and then two variables fix it. She solves two problems with it: Fibonacci Number (LeetCode 509) and Climbing Stairs (LeetCode 70). This idea is the doorway to dynamic programming, so it matters a lot.

This is a concept video, so the order is:
① what the pattern is → ② how to recognise it → ③ the intuition → ④ every example problem she solves, each with its own full mini-section (question, constraints, base case, recursive case, code, line by line, recursion tree + stack dry run, complexity) → ⑤ a pattern template in Python → ⑥ remember

• Part 0 · Recursion from scratch
• Part A · What non-linear recursion is (and why it repeats work)
• Part B · Fibonacci Number: plain recursion
• Part C · Fibonacci Number: saving answers (array / memo)
• Part D · Fibonacci Number: two variables, O(1) space
• Part E · Climbing Stairs: building the logic + recursion
• Part F · Climbing Stairs: array and two variables
• Part G · The pattern template
• Part H · Revision page

Part 0 · Recursion from scratch

1. A function that calls itself

Recursion means a function solves a problem by calling itself on a smaller version of the same problem. Example: to find 5! (5 factorial = 5×4×3×2×1) you can say "5! = 5 × 4!". Finding 4! is the same job, just smaller.

def fact(n):
    if n == 0:              # base case: smallest problem, answer known
        return 1
    return n * fact(n - 1)  # recursive case: use the answer of a smaller problem

2. The base case: why it must exist

The base case is the input so small that we know the answer without calling again. It is the "stop" sign.

• Without it, fact(0) would call fact(-1), which calls fact(-2)… forever.
• Python doesn't really run forever. It keeps every unfinished call in memory, and after about 1000 waiting calls it stops with RecursionError: maximum recursion depth exceeded.
• You can raise that limit with import sys; sys.setrecursionlimit(10**5), but that only helps when the recursion is correct but deep. It never fixes a missing base case.

3. The recursive case and the "leap of faith"

The recursive case is the line that calls the function on a smaller input and builds the answer from it. When you write it, trust that the smaller call already returns the right answer. Don't trace it in your head all the way down. This trust is called the leap of faith. Your only jobs are: (1) the base case is correct, (2) every call moves closer to the base case, (3) you combine the smaller answer correctly.

4. The call stack: push on call, pop on return

Python keeps a call stack: a pile of "frames". Each frame is one unfinished call with its own variables.

• When a function is called, its frame is pushed on top of the pile.
• When it returns, its frame is popped, and the answer goes to the frame just below, which was waiting.
• Only the top frame is running. All frames below it are paused.

Bottom of each picture = oldest call. Red = the frame running right now.

5. Work on the way down vs. work on the way back up

• On the way down = code that runs before the recursive call (e.g. printing n before calling).
• On the way back up = code that runs after the recursive call returns (e.g. n * fact(n-1): the multiply can only happen after the smaller answer comes back).

In this page, all the adding (f(n-1) + f(n-2)) happens on the way back up.

Part A · What non-linear recursion is

1The pattern

The teacher starts from the last video. In factorial, each call made one call: f(5) → f(4) → f(3) → f(2)… If you draw those calls, you get a straight line. That's why it was called linear recursion.

In non-linear recursion, one call makes two (or more) calls. For example f(n) calls f(n−1) and f(n−2). (It could also be f(n+1), or any other input. What matters is "more than one call".) Draw the calls now and each call splits into two branches, so the picture becomes a tree.

f(5)
 │
f(4)
 │
f(3)
 │
f(2)  ...a line

          f(4)
         /    \
      f(3)    f(2)
      /  \    /  \
   f(2) f(1) f(1) f(0)
   /  \
 f(1) f(0)     ...a tree

2How to recognise it

• Inside the function body, the function's own name appears two or more times in the recursive case.
• The answer for n "depends on several smaller answers" (e.g. "previous two numbers").
• The teacher's advice: looking at the code alone is not enough. To be sure, draw the calls (she calls it drawing the "stack calls"). If the drawing looks like a tree, it's non-linear.

3Intuition: the tree repeats itself

Look at the f(4) tree above. f(2) is solved twice, f(1) three times, f(0) twice. These are overlapping subproblems: the same small question shows up in different branches. The left branch already worked out f(2), so why does the right branch work it out again?

For f(4) the waste is small. For f(5), f(10), f(40) the tree explodes and the repeats multiply.

4Speed rule: when is 2ⁿ still OK?

Each call makes 2 calls, and the tree is about n levels deep, so the number of calls grows like 2ⁿ. A rough rule: a judge allows around 10⁸ simple operations per second.

So the teacher's rule of thumb: if n ≤ about 30, plain non-linear recursion can still be submitted; once n goes past 30, you must save answers.

5Space: recursion is not free

The teacher points out that recursion uses extra space even if you never create an array: every waiting call sits on the call stack. For the tree above, the stack is never taller than one root-to-leaf path, so the space is O(n) (the depth), not O(2ⁿ).

Part B · Fibonacci Number: plain recursion

LeetCode 509

1The question in simple words

The Fibonacci sequence starts with 0 and 1. Every later number is the sum of the two numbers before it.

Given n, return F(n), the n-th term (counting from term 0).

2What the constraints tell us

• 0 ≤ n ≤ 30 → n can be 0, so term 0 must be handled. n is never negative, so we don't need a negative check. (The teacher's note: she assumes non-negative input; if a question allowed negatives, you'd have to handle them.)
• n ≤ 30 → by the speed rule in Part A, the plain 2ⁿ recursion will pass (slowly). So here we don't strictly need DP, but we'll still learn it.
• Recursion depth is at most 30, far below Python's 1000 limit.

3Intuition: start from the simplest way you'd do it by hand

The teacher first forgets about recursion and asks: what's the most basic way? Make an array, put 0 and 1 in the first two slots (they can't be calculated, they're fixed), then fill each next slot as arr[i-1] + arr[i-2] (first previous + second previous). To get term 4, run the loop up to index 4 and return arr[4].

That loop shows the rule: term n needs the two previous terms. Recursion is just the same rule written as a function: "to get F(n), ask for F(n−1) and F(n−2) and add them".

4Building the base case and recursive case

Base cases: the terms that have no "two previous"

The formula needs two earlier terms, so it only works from term 2 onwards. Term 0 and term 1 have nothing (or only one thing) before them, so their answers must be fixed, exactly like the first two slots of the array:

• n = 0 → return 0
• n = 1 → return 1

Recursive case: everything from n = 2 up

return fib(n - 1) + fib(n - 2). Check n = 2: it calls fib(1) → 1 and fib(0) → 0, adds them → 1 ✓. This one line makes two calls, which is what makes it non-linear.

5Approach steps

1. If n ≤ 1, return n (fixed first two terms).
2. Otherwise, ask the same function for term n−1 and term n−2.
3. Return their sum.

6Code (Python)

class Solution:
    def fib(self, n: int) -> int:
        if n <= 1:                                  # base case: F(0)=0, F(1)=1
            return n
        return self.fib(n - 1) + self.fib(n - 2)    # two calls -> non-linear

7Code line by line

8Dry run: fib(4)

Each node shows call = what it returns. Red = a call that repeats work already done somewhere else in the tree.

                      fib(4)=3
                   /            \
            fib(3)=2             fib(2)=1   ← repeat
            /      \             /      \
      fib(2)=1    fib(1)=1   fib(1)=1  fib(0)=0
      /      \
 fib(1)=1  fib(0)=0

1. fib(4) starts. 4 > 1, so it calls fib(3) first. fib(4) waits.
2. fib(3) calls fib(2). fib(3) waits.
3. fib(2) calls fib(1).
4. fib(1) is a base case → returns 1. Its frame is popped.
5. Back in fib(2), now it calls fib(0) → returns 0.
6. fib(2) = 1 + 0 = 1, returned to fib(3).
7. fib(3) now calls its right side fib(1) → 1. fib(3) = 1 + 1 = 2, returned to fib(4).
8. fib(4) now calls its right side fib(2). We already found fib(2) = 1 in step 6, but plain recursion has no memory, so it does it all again: fib(1) → 1, fib(0) → 0, fib(2) = 1.
9. fib(4) = 2 + 1 = 3. The stack is empty. Answer 3 ✓

The stack is never taller than 4 frames (= n), even though 9 calls happen in total.

9Complexity & remember

Counting calls. Let calls(n) = how many calls fib(n) makes in total. calls(0) = calls(1) = 1, and calls(n) = calls(n−1) + calls(n−2) + 1.

• Time O(2ⁿ): two calls per level, about n levels. (The exact growth is about 1.6ⁿ, still exponential.)
• Space O(n): the call stack holds at most one path from the top to a leaf, n frames.
• With n ≤ 30 it passes on LeetCode, just slowly. The teacher submits it to show that.

Part C · Fibonacci Number: saving answers

1The idea

The plain recursion repeats work. The fix the teacher gives: save every answer once, then reuse it. She describes it with an array: slot 0 = 0, slot 1 = 1, and from slot 2 onward, each slot = sum of the two before it. The same "save it" idea can also be added inside the recursion (top-down memoisation). Both are shown below because both are DP.

2Constraints, once more

Nothing new: n from 0 to 30. Watch the n = 0 case in the array version: an array of size n+1 = 1 has only slot 0, so writing to slot 1 would crash. We return early for n ≤ 1.

3Approach steps (top-down)

1. Make memo of size n+1, filled with −1 ("not computed yet").
2. In the recursive function: base case n ≤ 1 → return n.
3. If memo[n] is not −1, the answer is already known → return it (no new calls).
4. Otherwise compute f(n-1) + f(n-2), store it in memo[n] first, then return it.

4Code (Python)

class Solution:
    def fib(self, n: int) -> int:
        memo = [-1] * (n + 1)              # -1 means "not computed yet"

        def f(k):
            if k <= 1:                     # base case
                return k
            if memo[k] != -1:              # already solved? reuse it
                return memo[k]
            memo[k] = f(k - 1) + f(k - 2)  # solve once, save
            return memo[k]

        return f(n)

class Solution:
    def fib(self, n: int) -> int:
        if n <= 1:                         # also protects dp[1] when n == 0
            return n
        dp = [0] * (n + 1)
        dp[0], dp[1] = 0, 1                # the two fixed terms
        for i in range(2, n + 1):
            dp[i] = dp[i - 1] + dp[i - 2]  # first previous + second previous
        return dp[n]

5Code line by line

6Dry run: fib(4) with memo

                 f(4)=3  saves memo[4]
                /        \
   saves memo[3] f(3)=2    f(2)=1  ← memo hit, no children
              /     \
 saves memo[2] f(2)=1  f(1)=1
           /    \
       f(1)=1  f(0)=0

1. f(4) → f(3) → f(2) → f(1) = 1, f(0) = 0 → memo[2] = 1.
2. Back in f(3): f(1) = 1 → memo[3] = 1 + 1 = 2.
3. Back in f(4): it asks for f(2). memo[2] is 1, already saved → return immediately. The red branch from Part B is gone.
4. memo[4] = 2 + 1 = 3. Answer 3 ✓. Total calls: 7 instead of 9 (for n = 30: 59 instead of 2.7 million).

Bottom-up table for n = 5:

7Complexity & remember

• Time O(n): each term 0..n is computed only once.
• Space O(n): the array. (Top-down also has the call stack, another O(n).) The teacher points out this is still extra space, which leads to Part D.

Part D · Fibonacci Number: two variables, O(1) space

1The question again, and what we want now

Same question. The teacher's next point: the array and the recursion both use extra space. Can we avoid it?

2Intuition: we only ever look two slots back

To fill dp[i] we only read dp[i−1] and dp[i−2]. Everything older is never read again. So instead of a whole array, keep just two variables:

• prev0 = the second previous term (starts at term 0 = 0)
• prev1 = the first previous term (starts at term 1 = 1)

She shows it with the terms 1, 2, 3, 4: to make 3 you need prev1 = 2 and prev0 = 1. For the next term (4), the pair slides one step right: the old prev1 (2) becomes the new prev0, and the term just made (3) becomes the new prev1.

3Building the update: why a temp variable?

Each loop step needs two updates: new prev0 = old prev1, and new prev1 = prev0 + prev1.

4Approach steps

1. If n ≤ 1, return n.
2. prev0 = 0, prev1 = 1.
3. For i from 2 to n: temp = prev0 + prev1; prev0 = prev1; prev1 = temp.
4. After the loop, prev1 holds term n → return it.

5Code (Python)

class Solution:
    def fib(self, n: int) -> int:
        if n <= 1:
            return n
        prev0, prev1 = 0, 1              # term 0 and term 1
        for i in range(2, n + 1):
            temp = prev0 + prev1         # the current term
            prev0 = prev1                # slide: first previous becomes second previous
            prev1 = temp                 # the current term becomes first previous
        return prev1

6Code line by line

7Dry run: n = 5 (hand table)

8Complexity

• Time O(n): one loop, constant work per step, no repeats.
• Space O(1): just two (three with temp) variables. The teacher calls this the fastest version.

9Remember

Part E · Climbing Stairs: building the logic + recursion

LeetCode 70

1The question in simple words

A staircase has n steps. From where you stand, each move is either 1 step or 2 steps. In how many different ways can you reach the top (step n)?

Careful: it doesn't ask for the number of jumps. It asks for the number of different sequences of jumps. "1 then 2" and "2 then 1" are two different ways.

The teacher says up front: this is Fibonacci in disguise, only the base cases change. Let's discover that the way she does.

2What the constraints tell us

• 1 ≤ n ≤ 45 → n is never 0, so the smallest case is 1 step.
• n can be 45 → plain recursion is about 2⁴⁵ ≈ 3.5×10¹³ (the teacher says roughly 10¹²–10¹³). That's way past 10⁸, so plain recursion will TLE. We still write it to learn, then optimise.
• The answer for 45 is 1,836,311,903, which fits in a 32-bit int (in Python ints never overflow anyway).

3Intuition: break it into small cases

We don't know the ways to reach step 10 directly. So the teacher starts from the tiniest staircases and counts by hand.

4Building the logic from examples

• n = 1: only one stair. You can't take a 2-jump (it would go past the top), so only one way.
• n = 2: jump 2 directly, or 1 then 1. Once you've done one 1-jump, only one stair is left, so you're forced to take another 1. → 2 ways.
• n = 3: at each stair you choose 1 or 2 (when 2 stairs remain), or only 1 (when 1 stair remains). Following every choice gives 3 ways.
• n = 4: the teacher asks you to pause and try it yourself. The answer is 5.

The base cases change

In Fibonacci we wrote n <= 1 because terms 0 and 1 were fixed. Here the problem starts at 1, and the fixed answers are ways(1) = 1 and ways(2) = 2. Both are "answer = n", so the base case becomes if n <= 2: return n. That's the only change from Fibonacci.

5Approach steps

1. If n ≤ 2, return n.
2. Otherwise return ways(n−1) + ways(n−2).

6Code (Python)

class Solution:
    def climbStairs(self, n: int) -> int:
        if n <= 2:                                          # ways(1)=1, ways(2)=2
            return n
        return self.climbStairs(n - 1) + self.climbStairs(n - 2)

7Code line by line

8Dry run: n = 5

                    cs(5)=8
                 /           \
           cs(4)=5           cs(3)=3   ← repeat
           /     \            /     \
      cs(3)=3   cs(2)=2  cs(2)=2  cs(1)=1
      /    \
 cs(2)=2  cs(1)=1

1. cs(5) → cs(4) → cs(3) → cs(2) = 2 (base), then cs(1) = 1 (base).
2. cs(3) = 2 + 1 = 3, returned to cs(4).
3. cs(4) calls cs(2) = 2 → cs(4) = 3 + 2 = 5, returned to cs(5).
4. cs(5) calls cs(3). cs(3) was already solved in step 2, but it's solved again: cs(2) = 2, cs(1) = 1 → 3.
5. cs(5) = 5 + 3 = 8 ✓

9Complexity & remember

• Calls: n = 5 → 9 calls; n = 45 → 2,269,806,339 calls. That's why the teacher's submission gets TLE.
• Time O(2ⁿ), Space O(n) for the call stack (depth at most n − 1).

Part F · Climbing Stairs: array and two variables

1What changes from Fibonacci

The teacher copies her Fibonacci solutions and changes only the starting values:

2Array version (bottom-up DP)

Make an array of size n+1, fix slots 1 and 2, then fill from slot 3 to slot n with the sum of the two slots before. Return slot n.

class Solution:
    def climbStairs(self, n: int) -> int:
        if n <= 2:                          # also stops dp[2] crashing when n == 1
            return n
        dp = [0] * (n + 1)
        dp[1], dp[2] = 1, 2
        for i in range(3, n + 1):
            dp[i] = dp[i - 1] + dp[i - 2]
        return dp[n]

3Memoised recursion (top-down), for completeness

class Solution:
    def climbStairs(self, n: int) -> int:
        memo = {}

        def ways(k):
            if k <= 2:
                return k
            if k in memo:                   # solved before -> reuse
                return memo[k]
            memo[k] = ways(k - 1) + ways(k - 2)
            return memo[k]

        return ways(n)

memo tree for n = 5:   ws(5)=8
                      /       \
                 ws(4)=5     ws(3) memo hit = 3
                 /     \
            ws(3)=3   ws(2)=2
            /    \
       ws(2)=2  ws(1)=1          7 calls instead of 9

4Two-variable version

class Solution:
    def climbStairs(self, n: int) -> int:
        if n <= 2:
            return n
        prev0, prev1 = 1, 2                 # ways(1), ways(2)
        for i in range(3, n + 1):
            temp = prev0 + prev1
            prev0 = prev1
            prev1 = temp
        return prev1

5Code line by line

6Dry run: n = 5

7Complexity

8Why the teacher calls the plain one "the worst"

It loses on both counts: exponential time, and it still uses O(n) space for its hidden call stack. The array fixes time but keeps O(n) space. Two variables fix both.

9Remember

Part G · The pattern template

Any "answer depends on the previous two answers" problem follows this ladder. Write the plain recursion first to get the logic right, then climb.

# 1) plain non-linear recursion: correct, but O(2^n)
def solve(n):
    if n is small:                         # fixed answers (base cases)
        return known_answer(n)
    return solve(n - 1) + solve(n - 2)     # two calls -> tree

# 2) memoised: O(n) time, O(n) space
def solve(n, memo):
    if n is small:
        return known_answer(n)
    if n in memo:                          # check the notebook first
        return memo[n]
    memo[n] = solve(n - 1, memo) + solve(n - 2, memo)
    return memo[n]                         # save before returning

# 3) two variables: O(n) time, O(1) space
def solve(n):
    if n is small:
        return known_answer(n)
    prev0, prev1 = known_answer(first), known_answer(second)
    for i in range(second + 1, n + 1):
        temp = prev0 + prev1
        prev0 = prev1
        prev1 = temp
    return prev1

This is a sketch (the "n is small" lines are placeholders), not runnable code.

Part H · Revision page

s = Solution()
# for a Fibonacci solution:
print([s.fib(n) for n in range(8)])          # [0, 1, 1, 2, 3, 5, 8, 13]
print(s.fib(30))                             # 832040
# for a Climbing Stairs solution:
print([s.climbStairs(n) for n in range(1, 6)])   # [1, 2, 3, 5, 8]
print(s.climbStairs(45))                     # 1836311903 (skip for the plain recursion!)

Based on this video: Non-Linear Recursion | Fibonacci Number & Climbing Stairs