DSA sheet · Recursion · concept video

Recursion Patterns Overview

This is the map for the whole recursion topic. Most of us start recursion by memorising code and drawing call stacks without really knowing why they work. The teacher wants to fix that first. She says recursion is not just "a function that calls itself". It's about trusting the same function to solve a smaller copy of the problem. Then she sorts recursion problems into 4 patterns: linear recursion, divide & conquer, recursion on strings, and recursion on stacks / linked lists. If you can tell which pattern a question belongs to, you already know the shape of the code.

Recursion matters because trees, graphs, backtracking and dynamic programming are all built on it. Recursion is not a data structure. It's a way of writing an algorithm.

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

• Part 0 · Recursion from scratch (factorial)
• Part A · Pattern 1: Linear recursion
• Part B · Pattern 2: Divide & conquer
• Part C · Pattern 3: Recursion on strings
• Part D · Pattern 4: Recursion on stacks & linked lists
• Part E · Revision page

Part 0 · Recursion from scratch

What is recursion?

Recursion means a function solves a problem by calling itself on a smaller version of the same problem. The teacher puts the weight on the second half of that sentence. The important part isn't the self-call. It's the trust: you hand a smaller input to the same function and believe it will bring back the right answer for that smaller input. Then you only do one small step of work yourself.

Every recursive function has exactly 2 parts

Why the base case must exist

Without a base case, fact(5) calls fact(4), which calls fact(3) … fact(0), fact(-1), fact(-2) … forever. The teacher calls this "saving the function from an infinite loop". Each unfinished call takes memory. In Python the program crashes after about 1000 nested calls with RecursionError: maximum recursion depth exceeded.

The "leap of faith" (trusting the smaller call)

When you write return n * fact(n - 1), don't try to trace all the calls in your head. Assume fact(n - 1) already works, the same way you trust Python's built-in max(). Ask only: "if I had the answer for n − 1, how would I build the answer for n?" For factorial: multiply by n. That's the whole recursive case.

The call stack: push on call, pop on return

Python keeps a pile of unfinished calls called the call stack. When a function calls itself, the new call is pushed on top and the caller waits, paused in the middle of its line. When the top call returns, it is popped, and its answer goes to the call just below it, which then continues.

Work on the way down vs on the way back up

• Going down = the calls being made, n getting smaller. Anything written before the recursive call happens in this phase.
• Coming back up = the calls returning one by one. Anything written after the recursive call (like "multiply by n") happens in this phase.

In factorial, nothing is multiplied on the way down. Every multiplication happens on the way back up.

The teacher's first example: 5!

Factorial of n (written n!) is the product of all whole numbers from 1 to n. 5! = 5 × 4 × 3 × 2 × 1 = 120. She points out that the tail 4 × 3 × 2 × 1 is itself 4!. So 5! = 5 × 4!, 4! = 4 × 3!, and so on, down to 0! = 1. This is the smaller copy of the same problem. We trace it fully in Part A.

Part A · Pattern 1: Linear recursion

1What the pattern is

Each call makes exactly one recursive call, usually with the input reduced by one step (n → n − 1, or the string one character shorter). The calls form a single straight chain.

2How to recognise it

• Inside the function there is only one recursive call.
• If you draw the stack diagram, it looks like a straight line: f(5) → f(4) → f(3) → f(2) → … That straight look is where the name "linear" comes from.
• Typical questions: factorial of n, sum of the first n natural numbers, reverse a string, print 1 to n.

3Intuition

Think of a queue of people passing a question backwards. Person 5 asks person 4, who asks person 3 … until the last person knows the answer without asking (the base case). The answer then travels forwards again, and each person adds their small piece before passing it on.

4aExample: Factorial of n

Question

Given n ≥ 0, return n! (with 0! = 1).

Base case

n == 0 → return 1. The teacher keeps breaking the problem down until she reaches f(0), and we know 0! is 1. So that's where the chain stops.

Recursive case

n! = n × (n − 1)!, so return n * fact(n - 1).

Code

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

Line by line

Dry run for fact(5)

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

1. fact(5) needs fact(4), so it pauses. Stack: fact(5)
2. fact(4) needs fact(3), fact(3) needs fact(2), fact(2) needs fact(1), fact(1) needs fact(0). Each one pauses. Nothing has been multiplied yet.
3. fact(0) hits the base case and returns 1. It is popped off the stack.
4. fact(1) gets 1 → 1 × 1 = 1 → returns.
5. fact(2) gets 1 → 2 × 1 = 2 → returns.
6. fact(3) gets 2 → 3 × 2 = 6 → returns.
7. fact(4) gets 6 → 4 × 6 = 24 → returns.
8. fact(5) gets 24 → 5 × 24 = 120. The stack is empty. Final answer 120 ✓

Newest call on top (red). Each call leaves the stack the moment it returns.

Complexity

• Calls: fact(5) … fact(0) = 6 calls. For n it's n + 1 calls in one straight chain → Time O(n).
• Space O(n): at the deepest moment, n + 1 calls wait on the stack.

4bExample: Sum of the first n natural numbers

Question

Return 1 + 2 + … + n for n ≥ 0 (the sum is 0 when n = 0). The teacher lists it as a typical linear question.

Base case & recursive case

Base: n == 0 → 0 (adding nothing gives 0). Recursive: the sum up to n is n + the sum up to n − 1. It has the same shape as factorial, with + instead of × and 0 instead of 1.

def sum_n(n):
    if n == 0:                  # base case: empty sum
        return 0
    return n + sum_n(n - 1)     # my number + the sum of everything below me

Dry run for sum_n(3)

sum_n(3) = 3 + sum_n(2)          → 6
   └─ sum_n(2) = 2 + sum_n(1)    → 3
        └─ sum_n(1) = 1 + sum_n(0) → 1
             └─ sum_n(0) base      → 0

1. Going down: sum_n(3) → sum_n(2) → sum_n(1) → sum_n(0).
2. sum_n(0) returns 0.
3. Coming back up: 1 + 0 = 1, then 2 + 1 = 3, then 3 + 3 = 6 ✓

Complexity: n + 1 calls → Time O(n), Space O(n). (The formula n(n+1)/2 gives O(1), but the point here is to practise the pattern.)

4cExample: Reverse a string

Question

Return the string written backwards: "abc" → "cba".

Base case & recursive case

Base: a string of length 0 or 1 is its own reverse. Recursive: reverse the rest (everything after the first character), then stick the first character at the end. "abc" → reverse("bc") + "a" = "cb" + "a".

def reverse_string(s):
    if len(s) <= 1:                         # base case: "" or one letter
        return s
    return reverse_string(s[1:]) + s[0]     # reverse the rest, first letter goes last

Dry run for "abc"

rev("abc") = rev("bc") + "a"   → "cba"
   └─ rev("bc") = rev("c") + "b" → "cb"
        └─ rev("c")  base          → "c"

Complexity: n calls in a chain. Each call also copies the slice s[1:], which costs up to n, so the time is really O(n²) in Python. The stack is O(n). (To keep it O(n), swap characters in a list with two pointers. That's the string pattern in Part C.)

5Pattern template

def solve(n):
    if n == 0:                         # 1. smallest input: answer known directly
        return BASE_ANSWER
    smaller = solve(n - 1)             # 2. ONE call on a smaller input (leap of faith)
    return combine(n, smaller)         # 3. add my small piece on the way back up

6Remember

Part B · Pattern 2: Divide & conquer

1What the pattern is

Break the problem into two (or more) smaller sub-problems, solve each one recursively, then combine their answers to get the final answer. Breaking = divide, combining = conquer. If you have seen merge sort, you've already seen this pattern.

2How to recognise it

• The input can be split: an array into two halves, a tree into left subtree and right subtree.
• After the calls come back, there is a decision or a computation on their results: add the two sums, merge the two sorted halves, check whether both sides are true.
• Typical questions: binary search, merge sort, and many tree questions (left subtree sum + right subtree sum, and so on).

3Intuition

A manager splits a big job between two team members, waits for both reports, and combines them into one answer. Each team member does the same thing with their half, until the job is tiny enough to do directly.

4aExample: Binary search (recursive)

Question

Given a sorted list nums and a target, return its index, or −1 if it's missing. The teacher's description: if the target is smaller than the middle value, go to the left half. If it's greater, go to the right half. Instead of moving lo/hi pointers in a while loop, we pass the new range to a recursive call.

Base case

• lo > hi → the range is empty → return −1 (not found).
• nums[mid] == target → found → return mid.

Recursive case

Target smaller than the middle → search (lo, mid − 1). Target larger → search (mid + 1, hi). Only one half is ever searched, because sorting tells us which half can't contain the target.

def binary_search(nums, target, lo, hi):
    if lo > hi:                          # empty range: not found
        return -1
    mid = (lo + hi) // 2
    if nums[mid] == target:              # found it
        return mid
    if target < nums[mid]:               # target can only be on the left
        return binary_search(nums, target, lo, mid - 1)
    return binary_search(nums, target, mid + 1, hi)   # else only on the right

def search(nums, target):
    return binary_search(nums, target, 0, len(nums) - 1)

Dry run: nums = [1, 3, 5, 7, 9, 11, 13], target = 11

bs(lo=0, hi=6)  mid=3, nums[3]=7  < 11 → go right    → returns 5
   └─ bs(lo=4, hi=6)  mid=5, nums[5]=11 = 11 found     → returns 5

1. bs(0, 6): mid 3, value 7. 11 is bigger, so call bs(4, 6). bs(0,6) waits.
2. bs(4, 6): mid 5, value 11 → found → returns 5.
3. bs(0, 6) passes the 5 straight up → final answer 5 ✓

Complexity

Each call halves the range: 7 → 3 → 1 → 0. That's at most about log₂ n + 1 calls → Time O(log n), stack O(log n).

4bExample: Merge sort

Question

Sort a list. The teacher mentions that you can write the merge step with pointers in a loop, but the splitting itself is a natural recursive call.

Base case

A list with 0 or 1 elements is already sorted → return it.

Recursive case

Divide: sort the left half and the right half (two calls, trusting both). Conquer: merge the two sorted halves by repeatedly taking the smaller front element.

def merge_sort(arr):
    if len(arr) <= 1:                    # base case: already sorted
        return arr
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])         # divide: sort left half
    right = merge_sort(arr[mid:])        #         sort right half
    return merge(left, right)            # conquer: combine

def merge(a, b):
    out, i, j = [], 0, 0
    while i < len(a) and j < len(b):     # take the smaller front element
        if a[i] <= b[j]:
            out.append(a[i]); i += 1
        else:
            out.append(b[j]); j += 1
    out.extend(a[i:])                    # leftovers are already sorted
    out.extend(b[j:])
    return out

Dry run: [5, 2, 4, 1]

                ms([5,2,4,1]) → [1,2,4,5]
               /                        \
     ms([5,2]) → [2,5]            ms([4,1]) → [1,4]
       /         \                  /          \
ms([5])→[5]  ms([2])→[2]     ms([4])→[4]  ms([1])→[1]

1. ms([5,2,4,1]) splits and calls ms([5,2]) first. The top call waits.
2. ms([5,2]) calls ms([5]) → base → [5]. Then ms([2]) → base → [2].
3. ms([5,2]) merges [5] and [2] → [2,5] and returns.
4. The top call now calls ms([4,1]) → ms([4]) → [4], ms([1]) → [1] → merge → [1,4].
5. The top call merges [2,5] and [1,4]: 1, 2, 4, 5 → [1,2,4,5] ✓

Complexity

Count by levels: the list halves each level, so there are about log₂ n levels. Each level merges n elements in total → Time O(n log n). Calls: about 2n − 1 (7 calls for n = 4). The stack is only log n tall, but the merged lists use O(n) extra memory.

4cExample: Sum of a tree (left subtree + right subtree)

Question

Return the sum of all values in a binary tree. The teacher's tree example: to know a node's subtree sum, get the left subtree sum and the right subtree sum (divide), then add them to the node's own value (combine).

A subtree is a node together with everything below it. An empty tree (None) has sum 0.

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val, self.left, self.right = val, left, right

def tree_sum(root):
    if root is None:                     # base case: empty subtree
        return 0
    left = tree_sum(root.left)           # divide: left subtree sum
    right = tree_sum(root.right)         #         right subtree sum
    return root.val + left + right       # conquer: combine

Dry run

        1                 sum(1) = 1 + 6 + 3        → 10
       / \                  ├─ sum(2) = 2 + 4 + 0   → 6
      2   3                 │    ├─ sum(4) = 4+0+0  → 4
     /                      │    └─ sum(None)       → 0
    4                       └─ sum(3) = 3 + 0 + 0   → 3

Complexity: one call per node plus one per empty child → Time O(n). The stack is as tall as the tree: log n when balanced, n when it's a straight line.

5Pattern template

def solve(problem):
    if is_small(problem):                    # 1. small enough: answer directly
        return direct_answer(problem)
    part1, part2 = split(problem)            # 2. divide
    a = solve(part1)                         # 3. trust both calls
    b = solve(part2)
    return combine(a, b)                     # 4. conquer: merge / add / decide

6Remember

Part C · Pattern 3: Recursion on strings

1What the pattern is

The recursion walks over a string, usually with an index or two pointers as parameters, and at every call it checks or computes something on the characters: do they match, should this one be removed, and so on. The answer (True/False, or a new string) is decided along the way.

2How to recognise it

• The input is a string, and the loop version would move an index or two pointers.
• Usually there's one call per step, so the stack is a straight line. Technically that's linear recursion.
• Typical questions: palindrome check, remove characters, different ways to add parentheses.

3Intuition

Replace the loop's l += 1; r -= 1 with a new call that receives l + 1, r - 1. The parameters do the pointer moving for you.

4aExample: Check if a string is a palindrome

Question

A palindrome reads the same forwards and backwards. The first character must equal the last, the second must equal the second-last, and so on. Return True or False.

Recursive case (the main check)

Pass the string and two pointers l (left) and r (right). If s[l] != s[r], it's not a palindrome → return False immediately. Otherwise this pair is fine, so call the same function with l + 1 and r - 1, and return whatever it returns.

Base case (how the teacher finds it)

In her dry run (a 6-letter word like "abccba", indices 0 to 5), the pairs (0,5), (1,4), (2,3) all match. The next call has l = 3 and r = 2: l has crossed r. Everything was already checked, so there's nothing left to compare. So she continues only while l < r. Otherwise she returns True, because reaching this point means every pair matched.

def is_pal(s, l, r):
    if l >= r:                       # pointers met or crossed: all pairs matched
        return True
    if s[l] != s[r]:                 # one mismatch is enough
        return False
    return is_pal(s, l + 1, r - 1)   # the call moves both pointers inward

def is_palindrome(s):
    return is_pal(s, 0, len(s) - 1)

Dry run: "abccba"

is_pal(0,5)  'a'=='a' ✓                 → True
  └─ is_pal(1,4)  'b'=='b' ✓            → True
       └─ is_pal(2,3)  'c'=='c' ✓       → True
            └─ is_pal(3,2)  l > r base  → True

1. (0,5): a = a → call (1,4).
2. (1,4): b = b → call (2,3).
3. (2,3): c = c → call (3,2).
4. (3,2): l has crossed r → return True. Each waiting call passes True back up.

Complexity: about n/2 + 1 calls → Time O(n), stack O(n). It's a straight chain, so this is linear recursion.

4bExample: Remove a character from a string

Question

The teacher lists "remove characters" in this pattern. A common version: remove every occurrence of a given character ch from s. Example: remove 'a' from "banana" → "bnn".

Base case & recursive case

Base: the empty string has nothing to remove → "". Recursive: solve the rest of the string (s[1:]), then decide about the first character. Drop it if it's ch, otherwise put it back in front.

def remove_char(s, ch):
    if s == "":                          # base case: nothing left
        return ""
    rest = remove_char(s[1:], ch)        # trust: rest is already cleaned
    if s[0] == ch:                       # decide about my character
        return rest
    return s[0] + rest

Dry run: remove 'a' from "bat"

rc("bat") 'b' kept   → "b" + "t" = "bt"
  └─ rc("at") 'a' dropped → "t"
       └─ rc("t") 't' kept → "t" + "" = "t"
            └─ rc("") base   → ""

Complexity: n + 1 calls. Each slice copies up to n characters, so the time is O(n²) in Python, and the stack is O(n). (Passing an index instead of slicing makes the call count the only cost.)

"Different ways to add parentheses" is also in the teacher's list for this pattern, but it splits at every operator and makes many calls, so it's really a non-linear question. It's solved later in the sheet.

5Pattern template

def check(s, l, r):
    if l >= r:                         # 1. nothing left to compare
        return True
    if not ok(s[l], s[r]):             # 2. decide at this step
        return False
    return check(s, l + 1, r - 1)      # 3. parameters move the pointers

6Remember

Part D · Pattern 4: Recursion on stacks & linked lists

1What the pattern is

Changing a data structure (a stack, a queue, a linked list) using recursion instead of a second, helper data structure. We hold elements "in our hands" inside the waiting calls while we go down, and put them back in the order we want while we come back up.

2How to recognise it

• The question says "reverse / sort / delete the bottom / delete the middle of a stack" and often adds "without using another stack".
• Linked list questions like "merge two sorted lists" can also be written this way.
• The normal answer would need an extra stack or array to hold things temporarily.

3Intuition: why recursion helps

The teacher's example: reverse the stack 1, 2, 3, 4 (4 on top). The normal way uses a second stack: pop 4 and push it into stack 2, then 3, then 2, then 1. Stack 2 is now reversed, but we needed a whole extra stack.

With recursion, we do nothing on the way down except pop and hold each element in a waiting call. On the way back up, we put the elements back in the order we want. No second stack is created.

4aExample: Reverse a stack using recursion

Question

Reverse a stack (a Python list, where the end of the list is the top) using only append / pop and recursion. No second stack. The teacher only describes the idea in this video. The full code is here so you can trace it.

Base case & recursive case

• reverse(st): base case is an empty stack (nothing to reverse). Recursive case: pop the top x, reverse the rest (trust it), then put x at the bottom.
• insert_at_bottom(st, x): base case is an empty stack → just push x. Recursive case: pop the top, insert x at the bottom of the rest, then push the top back.

def insert_at_bottom(st, x):
    if not st:                       # empty: x becomes the bottom
        st.append(x)
        return
    top = st.pop()                   # hold the top in this call
    insert_at_bottom(st, x)          # put x under the rest
    st.append(top)                   # on the way back up, restore top

def reverse_stack(st):
    if not st:                       # base case: nothing to reverse
        return
    x = st.pop()                     # hold the top
    reverse_stack(st)                # trust: the rest is now reversed
    insert_at_bottom(st, x)          # old top goes to the bottom

Dry run: [1, 2, 3] (3 on top)

rev([1,2,3]) holds 3            → stack [3,2,1]
  └─ rev([1,2]) holds 2         → stack [2,1]
       └─ rev([1]) holds 1      → stack [1]
            └─ rev([]) base     → returns
          then insert_at_bottom(1) on []     → [1]
     then insert_at_bottom(2) on [1]         → [2,1]
then insert_at_bottom(3) on [2,1]            → [3,2,1]

1. Going down: rev pops 3, then 2, then 1. The list is now empty. Three calls are waiting, holding 3, 2, 1.
2. rev([]) returns.
3. The call holding 1 inserts it at the bottom of [] → [1].
4. The call holding 2 inserts it at the bottom: pop 1, place 2, push 1 back → [2, 1].
5. The call holding 3 inserts it at the bottom → [3, 2, 1]. Now 1 is on top. Reversed ✓

Complexity

reverse_stack makes n + 1 calls. Each one calls insert_at_bottom, which digs through up to n elements: 1 + 2 + … + n ≈ n²/2 calls → Time O(n²). The deepest stack is about 2n calls → Space O(n) on the call stack, with no extra list.

4bExample: Delete the bottom (and the middle) element of a stack

Question

Deleting the top is just pop(). The teacher asks how to delete the bottom one: recursively go down to the last element, remove it, then put all the others back while returning. The same trick deletes the middle element: stop after the right number of pops instead of at the bottom.

Base case & recursive case

• delete_bottom: base case is a stack with one element → pop it (that's the bottom). An empty stack → nothing to delete. Recursive case: pop the top, delete the bottom of the rest, then push the top back.
• delete_middle: count how many elements are still to skip (k). When k == 0, pop that element. Otherwise pop, recurse with k - 1, then push back. For size n, the middle counted from the top is position n // 2 (0-based), the GFG convention.

def delete_bottom(st):
    if not st:                       # empty: nothing to delete
        return
    if len(st) == 1:                 # base case: this IS the bottom
        st.pop()
        return
    top = st.pop()                   # hold it on the way down
    delete_bottom(st)
    st.append(top)                   # put it back on the way up

def delete_k_from_top(st, k):
    if k == 0:                       # reached the element to delete
        st.pop()
        return
    top = st.pop()
    delete_k_from_top(st, k - 1)
    st.append(top)

def delete_middle(st):
    if st:
        delete_k_from_top(st, len(st) // 2)

Dry run: delete_bottom([1, 2, 3, 4]) (4 on top)

db([1,2,3,4]) holds 4   → pushes 4 back → [2,3,4]
  └─ db([1,2,3]) holds 3 → pushes 3 back → [2,3]
       └─ db([1,2]) holds 2 → pushes 2 back → [2]
            └─ db([1])  base: pop 1     → []

Complexity: n calls going down and n pushes coming back → Time O(n), call stack O(n), no extra list. delete_middle is the same, with about n/2 calls.

4cExample: Merge two sorted linked lists (recursively)

Question

LeetCode 21. Merge two sorted linked lists into one sorted list. The teacher mentions it as a linked list question that can also be solved by recursion.

Base case & recursive case

Base: if one list is empty, the answer is the other list. Recursive: the smaller head goes first. Its next becomes "the merge of everything that's left" (trust the call).

class ListNode:
    def __init__(self, val=0, next=None):
        self.val, self.next = val, next

class Solution:
    def mergeTwoLists(self, l1, l2):
        if l1 is None:                   # base: nothing left in l1
            return l2
        if l2 is None:                   # base: nothing left in l2
            return l1
        if l1.val <= l2.val:             # l1's head is smaller: it goes first
            l1.next = self.mergeTwoLists(l1.next, l2)
            return l1
        l2.next = self.mergeTwoLists(l1, l2.next)
        return l2

Dry run: 1→3 and 2→4

m(1→3, 2→4)  1 smaller → 1.next = m(3, 2→4)   → returns 1→2→3→4
  └─ m(3, 2→4)  2 smaller → 2.next = m(3, 4)  → returns 2→3→4
       └─ m(3, 4)  3 smaller → 3.next = m(None, 4) → returns 3→4
            └─ m(None, 4) base               → returns 4

Complexity: one call per node → Time O(n + m), call stack O(n + m). (The loop version needs only O(1) memory. For very long lists, raise the recursion limit or use the loop.)

5Pattern template

def fix(st):
    if base_condition(st):            # 1. empty / one element / reached target
        handle_base(st)
        return
    held = st.pop()                   # 2. way down: hold one element
    fix(st)                           # 3. trust the smaller stack
    put_back(st, held)                # 4. way up: place it where it belongs

6Remember

Part E · Revision page

print(fact(5), sum_n(3), reverse_string("abc"))          # 120 6 cba
print(search([1, 3, 5, 7, 9, 11, 13], 11))               # 5
print(merge_sort([5, 2, 4, 1]))                          # [1, 2, 4, 5]
print(tree_sum(TreeNode(1, TreeNode(2, TreeNode(4)), TreeNode(3))))   # 10
print(is_palindrome("abccba"), is_palindrome("abcxba"))  # True False
print(remove_char("banana", "a"))                        # bnn
st = [1, 2, 3]; reverse_stack(st); print(st)             # [3, 2, 1]
st = [1, 2, 3, 4]; delete_bottom(st); print(st)          # [2, 3, 4]
st = [1, 2, 3, 4, 5]; delete_middle(st); print(st)       # [1, 2, 4, 5]

Based on this video: Recursion Patterns