Knowledge Guide
Home › DSA

Recursion

Step 10 in the DSA path · 25 concepts · 19 problems

0 / 44 complete

📘 Learn Recursion from zero

Recursion solves a problem by having a function call itself on a strictly smaller input until it hits a trivial base case, then combines the partial answers as the calls unwind. The skeleton is always the same: a base case that stops the descent, and a recursive case that reduces the problem toward it. Trigger: reach for recursion when a problem is naturally self-similar — it can be defined in terms of one or more smaller copies of itself (divide-and-conquer like sorting/search, tree/graph traversal, generating combinations, or any "n depends on n-1"). Below we trace Merge Sort on [5, 2, 4, 1]: it recursively splits the array in half, sorts each half, then merges the sorted halves.

✨ Added by the guide to build intuition — not from the source course.

🏗️ Visual walkthrough — trace it step by step

Step 1 — Enter the top call
mergeSort([5, 2, 4, 1])
 idx:  0  1  2  3
      [5, 2, 4, 1]
       L=0      R=3
       mid = (0+3)/2 = 1

The top call receives the full array. Length is 4 (> 1) so this is the recursive case. We compute mid = 1 and will split into left [5,2] (indices 0..1) and right [4,1] (indices 2..3). Why safe: each half is strictly shorter than the input, guaranteeing progress toward the base case.

Step 2 — Recurse into left half, split again
mergeSort([5, 2])      <-- active frame
 idx:  0  1
      [5, 2]
       L=0 R=1
       mid = 0
  left  = [5]   (idx 0)
  right = [2]   (idx 1)

call stack:
  mergeSort([5,2,4,1])
  └─ mergeSort([5,2])  <-- here

We descend into the left half [5,2] first. It still has length 2, so we split once more into [5] and [2]. Why safe: we always finish the left subtree completely before touching the right, so the call stack mirrors the split structure exactly.

Step 3 — Hit the base case, then merge [5] and [2]
mergeSort([5]) -> returns [5]   (len 1, BASE CASE)
mergeSort([2]) -> returns [2]   (len 1, BASE CASE)

merge step (two sorted 1-element lists):
  [5]   [2]
   ^i    ^j     compare 2 < 5  -> take 2
  result: [2]
  then drain remaining 5
  result: [2, 5]

left half [5,2] is now sorted -> [2, 5]

A length-1 array is already sorted, so it returns immediately — this base case stops the recursion. As the two leaf calls unwind, we merge them: compare fronts, emit the smaller, giving [2,5]. Why safe: both inputs to merge are individually sorted, so a single linear scan produces a correctly sorted output.

Step 4 — Recurse into right half, split and merge [4] and [1]
now back in mergeSort([5,2,4,1]),
left done ([2,5]); recurse RIGHT:

mergeSort([4, 1])
  mergeSort([4]) -> [4]   (BASE CASE)
  mergeSort([1]) -> [1]   (BASE CASE)

  merge:
   [4]   [1]
    ^i    ^j   compare 1 < 4 -> take 1
   result: [1]
   drain 4 -> [1, 4]

right half [4,1] is now sorted -> [1, 4]

With the left half fully resolved, the same process runs on the right half [4,1]: split to leaves, hit base cases, merge to [1,4]. Why safe: the right recursion is independent of the left — recursion handles each subproblem in isolation, so results can't interfere.

Step 5 — Final merge: combine [2,5] and [1,4], compare fronts
top-level merge of two sorted halves:
  left  = [2, 5]   right = [1, 4]
           ^i               ^j
  compare 2 vs 1 -> 1 smaller -> take 1

  result: [1]
  left  = [2, 5]   right = [_, 4]
           ^i                  ^j

Back in the top frame, we merge the two sorted halves. Pointers i and j sit on each half's front; 1 < 2 so 1 is emitted first. Why safe: the overall minimum must be at the front of one of the two sorted halves, so comparing only the two fronts is sufficient.

Step 6 — Continue merging until one half empties
result: [1]
  compare 2 vs 4 -> 2 -> take 2
result: [1, 2]
  left=[_,5]^i   right=[_,4]^j

  compare 5 vs 4 -> 4 -> take 4
result: [1, 2, 4]
  left=[_,5]^i   right=[_,_]  (right empty)

We keep taking the smaller front and advancing that pointer. After emitting 2 then 4, the right half is exhausted. Why safe: each comparison advances exactly one pointer, so the merge runs in O(n) and always terminates when both halves drain.

Step 7 — Drain the leftover and return the sorted array
right empty -> append all of left's remainder:
result: [1, 2, 4, 5]

idx:  0  1  2  3
     [1, 2, 4, 5]   <-- fully sorted, returned to caller

call stack fully unwound (empty)

When one half empties, the remaining tail of the other is already sorted, so we append it wholesale: 5 joins to give [1,2,4,5]. The top call returns and the stack unwinds completely. Why safe: the leftover is the suffix of an already-sorted half, so no further comparisons are needed.

Step 8 — Complexity & recap
recursion tree (depth = log2 n):
        [5,2,4,1]            level 0
        /        \
     [5,2]       [4,1]        level 1
     /   \       /   \
   [5]   [2]   [4]   [1]      level 2 (base)

work per level = O(n) merging
levels         = O(log n)
----------------------------------
Time  = O(n log n)
Space = O(n) buffer + O(log n) stack

Each level of the recursion tree does O(n) total merge work, and there are O(log n) levels, giving O(n log n) time. The O(log n) term is the call-stack depth — a direct cost of recursion. Why safe: the input halves every level, so depth is bounded by log₂ n and the recursion is guaranteed to terminate.

🎯 Guided practice

  1. Easy — Decimal to binary (print the bits). Goal: print the binary representation of a non-negative integer n.

    Write the recurrence: the binary of n is "binary of n//2" followed by the bit n%2. Example: 13 = (binary of 6) then 1; 6 = (binary of 3) then 0; and so on. The remainders are produced least-significant-first, so we want them printed in the reverse order they're computed.

    Base case: n <= 1 — a single bit, print it and stop, since there is nothing smaller left to break down. (Handling n == 0 here is what makes the function print 0 rather than nothing.)

    Order the work to get the right output — recurse first, then print: decToBin(n): if n > 1: decToBin(n // 2); print(n % 2). Because the recursive call runs before the print, the most-significant bit (deepest call) prints first — this is the "work after the call = bottom-up" lever from the intro.

    Trace n=6: decToBin(6) → recurse decToBin(3) → recurse decToBin(1) prints 1 (base case) → back in 3, print 3%2=1 → back in 6, print 6%2=0. Output 110. Correct. Complexity: O(log n) calls (n halves each time), O(log n) stack depth, O(1) extra space. Pattern learned: placing work before vs after the recursive call controls top-down vs bottom-up ordering — the same lever that distinguishes pre-order from post-order tree traversal.

  2. Medium — BST inorder traversal (sorted output). Goal: visit a binary search tree's nodes in ascending key order.

    Recall the BST invariant: for any node, all keys in its left subtree are smaller and all keys in its right subtree are larger. So "everything smaller than me" lives entirely to my left, "everything larger" to my right.

    Self-similar decomposition: the sorted sequence for a node is exactly [sorted left subtree] + [this node] + [sorted right subtree]. Each subtree is itself a BST — the same problem, smaller — so by the recursive leap of faith we assume inorder(left) already emits its keys in order.

    Base case: node is null → return without doing anything. This is what stops the recursion at a leaf's empty children (note: the base case is the empty subtree, not the leaf itself).

    Order the three actions correctly (this IS the algorithm): inorder(node): if node is null: return; inorder(node.left); visit(node.key); inorder(node.right). Left-then-self-then-right yields ascending order.

    Trace a tree with root 5, left child 3, right child 8: inorder(5) → inorder(3) → inorder(null) returns, visit 3, inorder(null) returns → visit 5 → inorder(8) → visit 8. Output 3 5 8, sorted. Complexity: O(n) time (each node visited once), O(h) stack space where h is tree height — O(log n) if balanced, O(n) for a degenerate (insertion-sorted) tree, which is a real stack-overflow risk on large skewed inputs. Pattern learned: swap the visit position to get pre-order (self, left, right) or post-order (left, right, self) — one template, three traversals.

✨ Added by the guide — work these before the full problem set.

Lessons in this topic