Phase 3Days 14-17

Recursion Foundations

An unshakable grip on recursion over numbers, arrays and strings

Phase Goal

Make recursion second nature so every later tree, graph and DP topic stands on solid ground.

Progress

Day 14: How recursion actually works

A function that solves a big instance by calling itself on a smaller oneBase case (when to stop) and recursive case (how to shrink)The recursion tree and the call stack side by sideWhy a missing or wrong base case causes a stack overflow

Print 1..N and N..1 (order of work versus order of calls)Sum of first N and factorial by recursionTracing the stack frame by frame on paperThe two moments: on the way down versus on the way back up

Carrying an accumulator down versus returning a value upReturn-value recursion: build the answer from the child callWhere the work happens relative to the recursive callConverting a simple loop into a recursion and back

Choose one core problem from LeetCode, Codeforces, AtCoder, or CSES after checking its prerequisites; hide its technique labelSpend 10–20 minutes retrieving one earlier mechanism and one earlier bug before new work; prioritize weak prerequisitesUse a five-task bank: guided warm-up, core, changed constraint, delayed recall, optional stretch; attempt one or two, not all five on a timerBefore a solution, produce a trace or brute-force plan; when stuck take one hint, act on it, then reassessRecord help used, the failing input, the corrected reasoning, and a next review date; start around 1/3/7/14/30 days and adaptReserve a weekly mixed review; after foundation readiness add a short virtual contest and upsolve one task with known prerequisitesProve progress through a delayed blank-editor reconstruction and a changed problem; a same-day quiz is supporting evidence only

Day 15: Recursion on arrays & strings

Reverse an array with two indices moving inwardCheck a string is a palindrome recursivelySum and max framed recursivelyPassing the array by reference plus an index parameter

Fibonacci by recursion and drawing its call treeCounting repeated subproblems (why it is O(2^n))The idea that remembering answers will later kill the repetitionDepth versus breadth of the recursion tree

Two calls per node (the pick/not-pick shape) on small inputsHow branching factor and depth set the total call countWhen exponential is acceptable (n up to about 20)Turning a recursive count into a recursive enumeration

Day 16: Subsequences & choices (the pick / not-pick engine)

Every element: include it or skip it, giving 2^n subsequencesBuilding the choice tree and reading a leaf as one subsequencePassing a current list down and printing at the base caseBacktracking: undo the choice after the recursive call returns

Print all subsequences with a target sumReturn true if any subsequence hits the sum (short-circuit)Count subsequences with a given sumThe three shapes: print all / return one / count

Stop early when the running sum exceeds the target (pruning)Why pruning changes constants, not always the worst caseRecognizing the pick/not-pick shape in future problemsHandoff to the backtracking phase where this scales up

Day 17: Recursion problem set & stack-based recursion

pow(x, n) recursively with fast exponentiationReverse a stack using recursionSort a stack using recursionDigit-based recursion (count good numbers)

Naming the base case, the state, and the transition every timeWhen to pass an index versus iterate inside the callSpotting infinite recursion and fixing the shrink stepA template you can reuse for the rest of the course

Default stack depth and when deep recursion crashesConverting deep recursion to iteration when neededPrinting the recursion trace to debug a wrong answerThe shared-global-vector bug and how to avoid it

Phase Complete!

After this phase, you'll be able to:

How recursion actually works
Recursion on arrays & strings
Subsequences & choices (the pick / not-pick engine)
Recursion problem set & stack-based recursion

After Phase 3, explain a core invariant, reconstruct a solution after a delay, diagnose a bug, and solve one unlabelled variation. Repair a failed prerequisite before advancing; record help separately from independent work.

Back to all phases

Recursion Foundations

Phase Goal

Day 14: How recursion actually works

The recursion mental model

Your first recursions

Parameterized versus functional recursion

Practice, delayed recall, and independent transfer

Day 15: Recursion on arrays & strings

Traversal by recursion

Fibonacci and the cost of naive recursion

Multiple recursive calls

Practice, delayed recall, and independent transfer

Day 16: Subsequences & choices (the pick / not-pick engine)

The pick / not-pick template

Sum-based subsequence problems

Trimming the tree

Practice, delayed recall, and independent transfer

Day 17: Recursion problem set & stack-based recursion

Classic small recursions

Recursion patterns recap

Depth, limits & debugging

Practice, delayed recall, and independent transfer

Phase Complete!