Solving a problem with a smaller copy of itself — and being able to say what that costs.

Three lessons, written to the course standard. The first teaches the technique, the second teaches how to price it, and the third is the shortcut for when the shape is standard.

Why recursion is filed under algorithms rather than under programming fundamentals. Programming fundamentals covers the mechanics — what a frame is, how a call returns. This folder is about recursion as a problem-solving and cost-analysis technique: how to decompose a problem so a recursive solution exists, and how to get from recursive code to a complexity. Nearly everything later in this course is a recursion with a particular shape, so this is the folder they all point back to.

The lessons

  1. Recursion Fundamentals — [Beginner → Intermediate] — the three questions that produce a recursive function; base case, recursive case and progress; winding and unwinding through the call stack; why space is the depth and time is the call count; the three ways recursion fails; and memoisation as the fix for repeated subproblems — 2,692,537 calls down to 59.
  2. Recursion Trees and Recurrences — [Intermediate] — turning code into ; drawing the tree; computing nodes, size and work at level ; the three cases — leaves dominate, levels equal, root dominates; subtractive recurrences; the substitution method; and the doubling test for checking a complexity claim without reading the code.
  3. The Master Theorem — [Intermediate → Advanced] — the same three cases as a theorem with precise conditions; what “polynomially larger” means and why Case 3 needs it; the regularity condition; and the three situations where the theorem genuinely fails, including the trap that produces a confidently wrong answer.

The thread through all three

Recursion is induction executed by a machine. The base case is the base step, the recursive case is the inductive step, and progress is what guarantees the two meet. That is why the method for writing one is three questions rather than a mental trace — you are constructing a proof, and a proof does not require you to picture every case.

The cost of a recursion is a recurrence, and a recurrence is a tree. Once you can compute the work at an arbitrary level, every divide-and-conquer complexity in the course falls out of the same three-way comparison. Merge sort’s , binary search’s , tree traversal’s and Strassen’s are four readings of one table.

Time and space are different questions. Naive Fibonacci at makes 2.7 million calls at a depth of 30. The call count is the time; the depth is the memory, and the stack is a small fixed resource — about 996 usable frames in CPython by default. This is why DFS ships in a recursive and an iterative form.

The routing question for everything downstream is: do the recursive calls overlap?

  1. If two branches ever solve the identical subproblem, cache it — you are in dynamic programming, and the cache is the whole algorithm.
  2. If they never do, a cache is pure overhead, and you are in divide and conquer or traversal.
  3. If the recursion makes a choice and then undoes it, you are in backtracking.

What is verified

Every lab was executed and its expected output generated from that run:

LessonWhat the lab demonstrates
fundamentalssys.getrecursionlimit() reports 1,000 but only 996 frames are usable; naive Fibonacci making 242,785 calls for 26 distinct subproblems; a base case the argument steps over, failing on odd input only; and a tail call blowing the stack, because Python does not eliminate them
recursion treesthe level-by-level work table for five recurrences, each matching its exact closed form; and the doubling test returning 2.00 for linear, 4.00 for quadratic, 3.02 for , and a slowly-falling 2.2 for
Master Theoremeach case’s verdict checked against measured work; Strassen’s constant ratio to holding at 2.32; and the gap case measuring 2.55/2.49/2.44 — distinguishable from the wrong answer by the numbers alone

Question banks

One bank per lesson: micro-questions with the answers hidden behind toggles, for closed-book recall rather than reading. Method explained in the arrays bank.


↑ Back to Algorithms