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

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.
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

🧠 Review & recall

Active recall is what moves a topic into long-term memory. Flip each card before revealing, then test yourself — your results are saved on this device.

Flashcard

What two parts must every well-formed recursive function have, and which should you design first?

tap to reveal →

A base case (the simplest instance, solved directly, which stops further recursion) and a recursive case (which calls the function on a strictly smaller input). Always identify the base case first, since it is what prevents infinite recursion.

💡 Russian dolls: open down to the smallest doll (base case), then reassemble on the way back up.

Flashcard

In a recursive function, what is the difference between the prologue and the epilogue?

tap to reveal →

The prologue is the work done before the recursive call; the epilogue is the work done after the recursive call returns. Their order matters: e.g., printing n before the call vs. after produces opposite output orders.

💡 Prologue = on the way down; epilogue = on the way back up.

Flashcard

Name the five recursion types from the lessons and how many recursive calls each makes.

tap to reveal →

Linear (single call), Tail (single call, as the last operation/empty epilogue), Binary (two calls, e.g., splits in half), Multiple/multi-way (more than two calls), and Indirect/multi-level (a function calls another that eventually calls it back).

💡 1, 1-last, 2, many, and 'A calls B calls A'.

Flashcard

Why is tail recursion special, and what classic problems use binary recursion?

tap to reveal →

Tail recursion has the recursive call as the very last operation (empty epilogue), so it can be easily translated to an iterative loop. Binary recursion (two calls) naturally fits Merge Sort, Quick Sort, binary tree traversals, tree height, Tower of Hanoi, and the Fibonacci function.

💡 Tail = 'last call, easy to loop'; binary = 'split into two.'

Flashcard

What is a recurrence relation, and what three techniques analyze recursive time complexity?

tap to reveal →

A recurrence relation mathematically captures a recursive algorithm's running time in terms of T of smaller inputs (e.g., T(n)=2T(n/2)+O(n) for Merge Sort). The three standard techniques are the recursion tree method, the substitution method (guess and prove by induction), and the master theorem.

💡 Tree, Substitute, Master — the three ways to crack a recurrence.

Flashcard

What are the time and space complexities of recursive factorial, binary search, and Pow(x,n) by halving?

tap to reveal →

Factorial: O(N) time and O(N) space (N stack frames). Recursive binary search: O(log n) time and O(log n) space (call stack). Pow(x,n) using x^(2k)=(x^k)^2 halving: O(log n) time and O(log n) space.

💡 Linear shrink = O(N); halving = O(log n) for both time and stack.

Flashcard

Why does naive Fibonacci motivate memoization, and what does it cost?

tap to reveal →

Naive Fibonacci is binary recursion with overlapping subproblems, causing exponential repeated work. Memoization stores each computed Fibonacci number in a table so each is computed once, giving O(n) time and O(n) space (table plus recursion stack).

💡 Cache the overlaps: exponential becomes linear.

Q1. Which recursion type is defined by the recursive call being the LAST operation in the function (empty epilogue)?

Q2. For Merge Sort, which recurrence and complexity match the lessons?

Q3. The recursive GCD algorithm returns calculateGCD(B, A % B) until B is 0. Which principle is this?

Q4. Recursive binary search has which time and space complexity, and why is the space non-constant?

Q5. Which best describes the recursion tree method for analyzing complexity?