DSA sheet · Recursion · Linear recursion pattern

Linear Recursion

The sheet has finished arrays, strings, binary search and stack, and this video opens recursion. Before solving questions, the teacher sorts recursion into types. By the number of calls, it's linear (one call) or non-linear / binary (two or more calls). By how the answer is built, it's functional (the answer is built while returning) or parameterised (the answer travels inside the parameters). Then she solves 3 sheet questions in the linear pattern: Factorial of n, Print 1 to n / n to 1 (left for practice) and Palindrome Number.

The big message: recursion does not automatically mean 2ⁿ time. Linear recursion is just as fast as a loop: O(n). Only when a function makes 2 or more calls does the time explode.

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

• Part 0 · Recursion from scratch
• Part A · Factorial: from a loop to recursion (functional)
• Part B · Types by number of calls: linear vs non-linear (Fibonacci)
• Part C · Functional vs parameterised recursion
• Part D · Problem 1: Factorial of n
• Part E · Problem 2: Print 1 to n and n to 1
• Part F · Problem 3: Palindrome Number
• Part G · Revision page

Part 0 · Recursion from scratch

A function calling itself

Recursion is when a function calls itself to solve a smaller version of the same problem. Anything you can do with a linear recursion, you can also do with a for or while loop. Recursion is just another way of writing the repeated step.

The 2 parts of every recursive function

• Base case: the condition where the function stops and returns a known answer without calling itself. It plays the same role as the stopping condition of a loop.
• Recursive case: the function calls itself on a smaller input and uses that answer.

What happens without a base case?

The calls never stop: f(5) → f(4) → … → f(0) → f(−1) → … The teacher calls this getting stuck in an infinite loop. In Python, every unfinished call takes a slot on the call stack, and after about 1000 nested calls Python raises RecursionError.

The leap of faith

The teacher keeps saying each call is dependent on another call to hand it an answer. 5! says: "I don't know 4!, but if someone gives it to me, I multiply by 5 and I'm done." You don't trace all the calls when you write the code. You trust that the smaller call returns the right answer, and you only write your own small step.

The call stack: push on call, pop on return

Every call is stored in an internal stack in memory (the call stack). A new call is pushed on top and the caller pauses. When a call returns, it is popped, and its value goes to the call underneath, which continues from where it paused.

Work on the way down vs on the way up

Code written before the recursive call runs while the calls go down (n shrinking). Code written after it runs while the calls come back up. This one fact explains both functional vs parameterised recursion (Part C) and "print 1 to n" vs "print n to 1" (Part E).

Part A · Factorial: from a loop to recursion

1What the idea is

Factorial of n (n!) = n × (n−1) × … × 2 × 1. For example, 5! = 5 × 4 × 3 × 2 × 1 = 120, and 0! is defined as 1. The teacher starts with the loop everyone knows, then turns it into recursion.

def fact_loop(n):
    prod = 1
    for i in range(1, n + 1):     # 1, 2, ..., n  (start at 1, not 0)
        prod *= i
    return prod

She points out that the loop must start at 1, not 0. Multiplying by 0 would make everything 0.

2How to recognise the recursion inside

Look at what repeats: 5! = 5 × (4 × 3 × 2 × 1), and the bracket is 4!. Likewise 4! = 4 × 3!, 3! = 3 × 2!. The same work is repeated on a smaller number. Whenever you see that, the work can be handed to a function call instead of a loop: f(n) = n × f(n − 1).

3Intuition

f(5) says: "give me 4! and I'll multiply by 5." f(4) says: "give me 3! and I'll multiply by 4." … Each call waits for the smaller one. Nobody multiplies anything until the smallest call answers. Then the answers flow back and each call does its one multiplication.

4Building the base case, the way the teacher derives it

A loop knows where to stop. A recursion needs the same thing, and that stopping condition is the base case. How do we choose it?

• We start from a large number (n) and go down. So the base case must be the small end.
• Which small value? The loop started at i = 1. That same value becomes the base case: if n == 1: return 1.

def fact_up(i, n):
    if i > n:                     # passed n: nothing left to multiply
        return 1
    return i * fact_up(i + 1, n)  # i times the product of (i+1 .. n)

# call it as fact_up(1, n)

5Approach steps

1. If n ≤ 1 → return 1 (base case).
2. Otherwise call f(n − 1). Don't compute anything yet. Just wait.
3. When it returns, multiply by n and return that.

6Code (Python)

def fact(n):
    if n <= 1:                  # base case: 0! = 1! = 1
        return 1
    return n * fact(n - 1)      # wait for (n-1)!, then multiply by n

7Code line by line

8Dry run: fact(5)

fact(5) = 5 × fact(4)                 → 120
  └─ fact(4) = 4 × fact(3)            → 24
       └─ fact(3) = 3 × fact(2)       → 6
            └─ fact(2) = 2 × fact(1)  → 2
                 └─ fact(1)  base case → 1

1. fact(5) is pushed. It needs fact(4), so it pauses.
2. fact(4), fact(3), fact(2) are pushed the same way. Each one pauses.
3. fact(1) hits the base case → returns 1 and is popped.
4. fact(2): 2 × 1 = 2 → returned to fact(3).
5. fact(3): 3 × 2 = 6 → returned to fact(4), which was waiting for 3!.
6. fact(4): 4 × 6 = 24 → returned to fact(5).
7. fact(5): 5 × 24 = 120. The final answer is produced by the very first call, where we started ✓

Because the answer is built from the returned values on the way back up, this style is called functional recursion (more in Part C).

9Complexity & remember

• Calls: fact(5), 4, 3, 2, 1 = 5 calls, one chain. For n it's about n calls → Time O(n), the same as the loop.
• Space O(n): n calls wait on the stack at the deepest point (the loop needs only O(1)).

Part B · Types by number of calls: linear vs non-linear

1What the idea is

2How to recognise it

Count the recursive calls in the return line (or the body). One call → linear. f(n-1) + f(n-2) → two calls → binary / non-linear.

3Intuition: why linear is NOT 2ⁿ

The teacher clears up a common myth. In factorial, the loop ran 5 times for 5!, and the recursion made 5 calls for 5!: 5 → 4 → 3 → 2 → 1, then 5 returns. Same work, so it's O(n). Time only blows up when one call creates two new calls, and each of those creates two more.

4Example: Fibonacci (non-linear / binary recursion)

Question

The Fibonacci sequence starts 0, 1, and every next number is the sum of the previous two: 0, 1, 1, 2, 3, 5, 8, 13, … Return the n-th term, with f(0) = 0 and f(1) = 1.

Base case

Two base cases: n == 0 → 0 and n == 1 → 1. Both are needed, because f(n-2) can jump straight from 2 to 0.

Recursive case

f(n) = f(n − 1) + f(n − 2). For example, to get the 100th term, she needs the 99th and the 98th, then adds them. The function depends on two different calls.

def fib(n):
    if n == 0:                       # base case 1
        return 0
    if n == 1:                       # base case 2
        return 1
    return fib(n - 1) + fib(n - 2)   # TWO calls: the tree branches

Recursion tree: fib(5)

The teacher drew f(7) and filled in the values from the bottom up: f(2) = 1, f(3) = 2, f(4) = 3, f(5) = 5, f(6) = 8, f(7) = 8 + 5 = 13. Here is the smaller f(5) tree in full (value after →):

                         f(5) → 5
                 /                       \
           f(4) → 3                     f(3) → 2
          /         \                  /        \
     f(3) → 2     f(2) → 1        f(2) → 1    f(1) → 1
     /      \      /     \         /     \
 f(2)→1  f(1)→1 f(1)→1 f(0)→0  f(1)→1 f(0)→0
  /   \
f(1)→1 f(0)→0

1. f(5) calls f(4) first. f(4) calls f(3), f(3) calls f(2), f(2) calls f(1) → 1, then f(0) → 0. f(2) returns 1 + 0 = 1.
2. f(3) now calls f(1) → 1. f(3) returns 1 + 1 = 2.
3. f(4) calls its second child f(2) → computed all over again → 1. f(4) returns 2 + 1 = 3.
4. f(5) calls its second child f(3) → the whole f(3) subtree is rebuilt → 2.
5. f(5) returns 3 + 2 = 5 ✓

The stack is never taller than about n (one branch at a time), even though the tree is huge.

Why it grows "insanely": overlapping sub-problems

Look at the tree: f(3) is computed twice, f(2) three times. The teacher's question: if we have already calculated this part, why make the same calls again? These repeated pieces are called overlapping sub-problems. Fixing them is what dynamic programming does later.

Complexity: count the calls

• Every call makes 2 calls, so each level of the tree can double: 1, 2, 4, 8 … and there are n levels → at most about 2ⁿ calls → Time O(2ⁿ). With 3 calls per node it would be O(3ⁿ). That's why non-linear recursion almost always has just 2 calls.
• Space O(n): only one root-to-leaf path is on the stack at a time.

def fib_memo(n, memo=None):
    if memo is None:
        memo = {}
    if n <= 1:                       # same base cases: f(0)=0, f(1)=1
        return n
    if n not in memo:                # compute each f(n) only once
        memo[n] = fib_memo(n - 1, memo) + fib_memo(n - 2, memo)
    return memo[n]

Not covered in this video. It's here to show where the "why recalculate?" question leads: each f(k) is computed once, so the time drops to O(n).

5Pattern template (non-linear)

def solve(n):
    if n <= SMALL:                         # base case(s)
        return KNOWN
    return combine(solve(n - 1), solve(n - 2))   # two calls → a tree of calls

6Remember

Part C · Functional vs parameterised recursion

1What the idea is

This is a second way to classify recursion: by where the answer is calculated. The teacher says to remember both, because any problem can be solved either way.

2How to recognise it

• Functional: the recursive call is inside an expression (n * f(...), f(...) + f(...)).
• Parameterised: there's an extra parameter like ans / total / path, and the call is returned as it is.
• The teacher notes that you'll mostly meet the parameterised style in tree questions.

3Intuition

Functional: each person in the line waits for the person behind them, then adds their piece. Parameterised: each person writes their piece on a running slip and hands the slip on. The last person reads the finished total. It still has to be passed back to the front, because that's who asked.

4Example: factorial in both styles

Functional (from Part A)

Already traced: nothing is computed going down. 1 → 2 → 6 → 24 → 120 is built coming up, and the first call produces 120.

Parameterised: carry the answer

Instead of waiting to multiply, put the number to multiply into the next call. Start with ans = 1. Each call passes n - 1 and n * ans.

Base case

When n reaches 1 (or 0), the slip already holds the full product → return ans.

def fact_param(n, ans=1):
    if n <= 1:                          # base case: the slip is complete
        return ans
    return fact_param(n - 1, n * ans)   # multiply now, pass it down

Dry run: fact_param(5)

fp(5, 1)    5×1   = 5   → call fp(4, 5)    → returns 120
  └─ fp(4, 5)    4×5   = 20  → call fp(3, 20)   → returns 120
       └─ fp(3, 20)   3×20  = 60  → call fp(2, 60)  → returns 120
            └─ fp(2, 60)   2×60 = 120 → call fp(1, 120) → returns 120
                 └─ fp(1, 120)  base case             → returns 120

1. fp(5, 1): "I want 4!, and so far I have 5." → fp(4, 5).
2. fp(4, 5): "so far 20, I want 3!." → fp(3, 20).
3. fp(3, 20) → fp(2, 60) → fp(1, 120).
4. fp(1, 120): base case → returns 120. The answer is already complete at the last call.
5. fp(2, 60) was called by fp(3, 20), and so on, so 120 is handed back through every waiting call without any more work, until it reaches the main function → 120 ✓

5Is one of them faster?

No. Both go all the way down and all the way back up. Every call is stored on the stack and popped for sure. The functional one does its work coming up. The parameterised one does it going down, but it still has to come back to the start to return. So the time complexity is the same, for linear and for non-linear recursion. Only how the answer is calculated differs.

6Pattern templates & remember

def functional(n):
    if n <= 1:
        return BASE
    return step(n, functional(n - 1))        # work AFTER the call (coming up)

def parameterised(n, acc=START):
    if n <= 1:
        return acc                           # answer is already complete
    return parameterised(n - 1, step(n, acc))  # work BEFORE the call (going down)

Part D · Problem 1: Factorial of n

Sheet question 1 (GFG-style "Factorial")

1The question in simple words

Given a non-negative integer n, return n!.

2What the constraints tell us

• n can be 0 → the base case must cover 0, so use n == 0 or n == 1 (written as n <= 1). n == 1 alone would run 0 → −1 → … and crash.
• Factorials grow very fast, so judges keep n small. Python integers never overflow, so big values are not a problem here. In Java/C++ you'd need long.
• For a large n (say 5000) the plain recursion needs sys.setrecursionlimit, or a loop.

3Intuition

Exactly Part A: n! = n × (n − 1)!, and stop at 0 or 1.

4Conditions

• Why a base case at all? Otherwise the calls never stop.
• Why n ≤ 1? Both 0! and 1! are 1, and n shrinks by 1 each time, so it's guaranteed to land on 1 (or start at 0).

5Approach steps

1. If n is 0 or 1 → return 1.
2. Else return n × factorial(n − 1).

6Code (Python)

class Solution:
    def factorial(self, n):
        if n == 0 or n == 1:                 # base case covers n = 0 too
            return 1
        return n * self.factorial(n - 1)     # linear: one call

7Code line by line

8Dry run: factorial(3) and factorial(0)

factorial(3) = 3 × factorial(2)        → 6
  └─ factorial(2) = 2 × factorial(1)   → 2
       └─ factorial(1)  base            → 1

factorial(0)  base                      → 1   (no other calls)

1. factorial(3) → waits for factorial(2) → waits for factorial(1).
2. factorial(1) returns 1. Then 2 × 1 = 2, then 3 × 2 = 6.
3. factorial(0) returns 1 straight away. This is the edge case the constraint warned about.

9Complexity & remember

• Time O(n): n calls in one chain.
• Space O(n): the stack.

Part E · Problem 2: Print 1 to n and n to 1

Sheet question 2, left by the teacher for practice. Worked out here so you can check yourself.

1The question in simple words

Print the numbers 1, 2, …, n without a loop. Then print n, n−1, …, 1. The teacher includes it because it's linear recursion, and anything done with linear recursion can also be done with a for/while loop.

2What the constraints tell us

n is a positive count (n = 0 just prints nothing). Depth is n, so a very large n needs a raised recursion limit in Python.

3Intuition: the same call, two different moments to print

Both functions shrink n → n − 1. The only difference is where the print sits:

• Print before the call → it runs on the way down → n, n−1, …, 1.
• Print after the call → it runs on the way back up, smallest first → 1, 2, …, n.

4Conditions

Base case: n == 0 → nothing to print, just return. The function returns nothing (it only prints), so a plain return is enough.

5Approach steps

1. n to 1: if n is 0, stop. Print n, then call with n − 1.
2. 1 to n: if n is 0, stop. Call with n − 1 first, then print n.

6Code (Python)

def print_n_to_1(n):
    if n == 0:                    # base case: nothing left
        return
    print(n, end=" ")             # work on the way DOWN
    print_n_to_1(n - 1)

def print_1_to_n(n):
    if n == 0:
        return
    print_1_to_n(n - 1)           # go all the way down first
    print(n, end=" ")             # work on the way UP

7Code line by line

8Dry run: print_1_to_n(3)

p(3)  waits, then prints 3
  └─ p(2)  waits, then prints 2
       └─ p(1)  waits, then prints 1
            └─ p(0)  base → return

1. Going down: p(3) → p(2) → p(1) → p(0). Nothing is printed yet.
2. p(0) returns. p(1) continues after its call → prints 1.
3. p(2) prints 2, p(3) prints 3 → output "1 2 3" ✓
4. For print_n_to_1(3), each call prints before calling → "3 2 1".

9Complexity & remember

• Time O(n), Space O(n) for the stack (a loop would be O(1) space).

Part F · Problem 3: Palindrome Number

Sheet question 3 (the judge's version treats a negative number by its digits, so −6 counts as a palindrome)

1The question in simple words

A number is a palindrome if it reads the same from left to right and from right to left. The teacher's examples:

2What the constraints tell us

• The number can be negative, and the expected answer for −6 is True. So the sign must be ignored: check abs(n). This is the bug the teacher hit on screen, covered in step 4.
• |n| goes up to about 10⁹.

3Intuition: brute force → two pointers

Brute force: reverse and compare

Reverse the digits (131 → 131) and compare with the original. Equal → palindrome. It's linear, but it makes a full reversed copy and then a full comparison, so it does about 2n work. The teacher calls this the brute force.

def is_palindrome_brute(n):
    s = str(abs(n))
    return s == s[::-1]          # build the reversed copy, then compare

Better: two pointers

Put one pointer on the first digit and one on the last. Compare. If they match, move left one step forward and right one step back, and compare again. That's only about n/2 comparisons and no reversed copy.

4Building the conditions from examples

The base case: odd length vs even length

The teacher's habit: when writing recursion, first ask where the code should stop.

index:  0  1  2
digit:  1  3  1
step 1: L        R   1 = 1 ✓
step 2:    LR        same digit → stop

index:  0  1  2  3
digit:  1  2  2  1
step 1: L           R   1 = 1 ✓
step 2:    L  R         2 = 2 ✓
step 3:    R  L         crossed → stop

• Odd length: the pointers end up on the same digit (l == r). A digit always equals itself, so there's nothing to check → stop with True.
• Even length: the pointers never become equal. They jump past each other (l > r). Every pair was already checked → stop with True.

So one condition like l == r is not enough. It would miss the even case and keep going. The base case must cover both: if l >= r: return True. Reaching it means no pair ever failed, because a failing pair would have stopped us earlier.

The False condition

If the pointers haven't crossed and s[l] != s[r] → not a palindrome → return False straight away.

The recursive call replaces l++ and r--

The teacher converts the loop version line by line:

def is_pal_loop(s):
    l, r = 0, len(s) - 1
    while l < r:                 # loop condition → becomes the base case
        if s[l] != s[r]:
            return False
        l += 1                   # these two lines → become the call's arguments
        r -= 1
    return True

5Approach steps

1. Convert abs(n) to a string s.
2. Call check(s, 0, len(s) - 1).
3. In check: if l ≥ r → True.
4. If s[l] ≠ s[r] → False.
5. Else return check(s, l + 1, r - 1).

6Code (Python)

class Solution:
    def isPalindrome(self, n):
        s = str(abs(n))                      # ignore the sign: -6 → "6"
        return self.check(s, 0, len(s) - 1)

    def check(self, s, l, r):
        if l >= r:                           # met (odd) or crossed (even)
            return True
        if s[l] != s[r]:                     # a pair doesn't match
            return False
        return self.check(s, l + 1, r - 1)   # don't forget the return!

7Code line by line

8Dry run

The teacher counts the calls on a 4-digit number (pointers start at 0 and 3). Take 1221:

check(0,3)  '1'=='1' ✓                 → True
  └─ check(1,2)  '2'=='2' ✓             → True
       └─ check(2,1)  l > r, base case  → True

1. check(0, 3): not crossed. '1' = '1' → call check(1, 2).
2. check(1, 2): not crossed. '2' = '2' → call check(2, 1).
3. check(2, 1): l > r → crossed → return True.
4. True is passed back through check(1, 2) and check(0, 3) → True ✓ That's 3 calls = n/2 + 1 for n = 4 digits.

And 124: check(0, 2): '1' vs '4' → False at the very first call.

9Complexity & remember

• Calls: about n/2 + 1, where n is the number of digits. One call per step → linear recursion → Time O(n) (exactly about n/2).
• Space O(n): the string and the stack (only about 10 digits here, so it's tiny in practice).
• It passes comfortably because it's linear, not binary, recursion. "2ⁿ" only shows up when a call makes two calls.

Part G · Revision page

print(fact(5), fact_param(5), fact_up(1, 5), fact_loop(5))   # 120 120 120 120
print([fib(i) for i in range(8)])                           # [0, 1, 1, 2, 3, 5, 8, 13]
s = Solution()
print(s.isPalindrome(131), s.isPalindrome(124), s.isPalindrome(-6), s.isPalindrome(1221))
# True False True True
print_1_to_n(5); print()                                    # 1 2 3 4 5
print_n_to_1(5); print()                                    # 5 4 3 2 1

Based on this video: Linear Recursion · types of recursion, Factorial, Print 1 to N, Palindrome Number