Recursion

Why does a deeply recursive function crash with a stack overflow while an equivalent loop happily processes a million elements? Why does passing an array into a function sometimes mutate the caller's data and sometimes not? The answers all live one level below your code, in the runtime **memory model** that decides where every variable, object, and function call physically lives. This lesson opens up that model. You will see the difference between the **stack** (small, fast, organized into per-call frames) and the **heap** (larger, manually or garbage-collected, where objects and arrays actually live), watch how every function call pushes a stack frame and every `return` pops one, and trace how recursion stacks frames on top of frames until the base case unwinds them. You will also meet references and pointers conceptually, learn what triggers a stack overflow, and get a working mental model of garbage collection and memory leaks. This lesson builds on **Space Complexity Fundamentals**, where you learned to count auxiliary versus total space and saw why some algorithms claim `O(1)` space while others need `O(n)`. Memory Models gives you the underlying picture: those `O(...)` numbers describe stack frames, heap allocations, and reference graphs that you can now visualize concretely. Next, you will pivot to the mathematical side of the foundations track with **Discrete Mathematics Basics**, picking up the sets, relations, and logic vocabulary that algorithm analysis depends on.

When you stare at merge sort or binary search, the running time is not naturally a simple sum like `n^2/2 + n/2`. It is something more interesting: the cost of a problem of size `n` is built out of the cost of smaller problems plus a little glue. That self-referential structure is captured by a **recurrence relation**, an equation of the form `T(n) = ...` written in terms of `T` on smaller inputs. This lesson teaches you to spot, write, and classify recurrences directly from recursive code. You will identify the two ingredients every recurrence needs (the recursive case and the base case), then translate familiar algorithms into their `T(n)` equations: factorial gives `T(n) = T(n-1) + 1`, binary search gives `T(n) = T(n/2) + 1`, merge sort gives `T(n) = 2 T(n/2) + n`, and naive Fibonacci gives `T(n) = T(n-1) + T(n-2) + 1`. You will also group recurrences into three families (linear, divide-and-conquer, and multi-branch) and recognize the Big-O class each typically produces. This lesson builds on **Big-O Notation (Upper Bound)**, which gave you the language for expressing complexity, and on **Mathematical Sequences**, which gave you experience with arithmetic, geometric, and Fibonacci-style sequences, exactly the patterns you will see when a recurrence is expanded. Writing a recurrence is half the battle; the other half is converting it into a closed-form Big-O. That is the subject of the very next lesson, **Solving Recurrence Relations**.

Run an inorder traversal on a **Binary Search Tree (BST)** of any size and the keys come out sorted, in `O(n)` time and `O(h)` space, with no separate sort step. That single property (an ordering invariant baked into the structure itself) is what turns a generic binary tree into a logarithmic-time search container that powers Java's `TreeMap`, C++ `std::map`, and the conceptual model behind every database index. This lesson covers the BST property (left subtree keys less than the node, right subtree keys greater), search and insert that follow the invariant, the three deletion cases (leaf, one child, two children resolved by inorder successor or predecessor), and the validation problem that interviewers love because the naive `node.left.val < node.val` check is wrong. You will also analyze the gap between the balanced `O(log n)` and the degenerate `O(n)` chain that motivates the next lesson. In **Trees: Binary Tree Fundamentals**, you implemented preorder, inorder, postorder, and level-order traversals; the BST property is what makes inorder special, because it now produces sorted output for free. Next, **Balanced BST (AVL / Red-Black)** addresses the elephant in the room: an unlucky insertion order can degrade a BST to a linked list, and self-balancing rotations are the fix.

Cloning a 100k-element segment tree before every update so the previous version stays queryable costs `O(n)` time and space per update, which is unworkable. **Persistent Data Structures** achieve the same 'every past version is still queryable' guarantee in `O(log n)` extra time and space per update by sharing the unchanged subtrees between versions and only allocating new nodes along the path that actually changed. This lesson covers the path-copying technique on a persistent segment tree (each update returns a brand-new root that shares everything except a thin spine of new nodes with the previous version), the `O(log n)` point update and range query on any historical version, persistent arrays built on top of persistent segment trees, and persistent stacks and queues using the cons-list approach from functional programming. You will analyze the total space (`O(n + q log n)` for `q` updates) and apply the structure to k-th smallest in subarrays, time-travel queries, and offline-query reductions. In **Trees: Binary Tree Fundamentals**, a recursive subtree was a self-contained piece of data; structural sharing exploits exactly that property to reuse old subtrees in new versions. **Segment Tree** built the recursive aggregate-over-intervals shape that the persistent variant adapts directly, swapping in-place updates for path copying. Next, **Treap (Randomized BST)** returns to the BST family with a different twist: random priorities for expected balance and `O(log n)` split and merge primitives.

Given an array and a stream of mixed queries (`sum(L, R)`, `min(L, R)`, plus single-index updates), prefix sums answer the queries in `O(1)` but pay `O(n)` for every update, while a raw array does the opposite. Neither extreme is acceptable when both updates and queries are frequent. A **Segment Tree** balances the two: every operation runs in `O(log n)` after an `O(n)` build. This lesson covers the recursive segment-tree shape (a binary tree where each node stores the aggregate over an array interval, and children split the parent's interval in half), the `4n` flat-array layout that maps perfectly onto an iterative or recursive implementation, point update and range query in `O(log n)`, and lazy propagation, where range updates deposit a tag at the highest covering node and push it down only when a later query forces it. You will apply the structure to range sum, range minimum, and range maximum queries, and see why the same template extends to any associative aggregate. In **Arrays & Strings**, a flat array gave you `O(1)` indexed access but no aggregate support; the segment tree layers a hierarchy of precomputed aggregates on top of that array. **Trees: Binary Tree Fundamentals** is where the recursive shape and the `O(h)`-stack traversal pattern came from, and you reuse both directly here. Next, **Fenwick Tree (BIT)** solves a narrower version of the same problem (prefix-only aggregates) with simpler code and half the memory.

Listing every subset of a 20-element set produces over a million results, and there is no shortcut: you have to enumerate them. The trick is to do it without writing 20 nested loops. Backtracking solves the entire family of "generate all configurations" problems with a single recursive template that walks an implicit decision tree. **Backtracking (Intro)** introduces that template as the "choose, explore, unchoose" pattern. You will see how each recursive frame picks an option, recurses into the resulting state, and then undoes the choice on the way back up so the next branch starts from a clean slate. Classic problems include generating all subsets and permutations, the N-Queens placement puzzle, and a first look at Sudoku. The lesson also introduces pruning, where invalid partial solutions are cut off early so the algorithm explores far less than the full `O(2^n)` or `O(n!)` worst case. In **Recursion Fundamentals**, you learned to define a problem in terms of smaller subproblems. Backtracking adds one more idea: state mutated during recursion has to be restored before returning, so siblings in the call tree see the same starting state. From here, **BFS & DFS (Intro)** generalizes the same tree-of-states view to actual graphs.

Multiplying two `n`-bit integers the way you learned in school takes `O(n^2)` digit operations. In 1960, Karatsuba showed that the same product can be computed with three recursive multiplications instead of four, dropping the cost to `O(n^1.585)`. A few years later Strassen pulled the same trick on matrix multiplication, replacing eight recursive multiplications with seven and breaking the `O(n^3)` barrier for the first time. Both algorithms are pure divide-and-conquer with cleverly engineered combine steps, and they remain the gateway to a deeper view of D&C as algebraic restructuring. **Divide and Conquer (Advanced)** walks through that view. You will derive Karatsuba multiplication and apply the Master Theorem to its `T(n) = 3T(n/2) + O(n)` recurrence. You will work through Strassen's seven-multiplication identity for `2 x 2` blocks and discuss when its higher constant factor pays off in practice. You will solve closest-pair-of-points in 2D in `O(n log n)` via the strip optimization in the combine step, and look at convex-hull computation through a divide-and-conquer lens. In **Divide and Conquer (Intro)**, you applied the Master Theorem to merge sort and quick sort. **Recursion Fundamentals** gave you the call-stack model these algorithms still inhabit. This lesson keeps the recurrence framework but engineers cleverer combine steps. Next, **Mathematical Algorithms** turns to number-theoretic computation.

Merge sort and quick sort both run in `O(n log n)`, and once you write down their recurrences (`T(n) = 2T(n/2) + O(n)` and its expected-case sibling) the same `n log n` falls out of both. That is not a coincidence: divide and conquer is a paradigm with a precise mathematical signature, and the Master Theorem reads it directly off the recurrence. **Divide and Conquer (Intro)** introduces the three-step pattern (divide, conquer, combine) and the recurrence-relation toolkit that comes with it. You will analyze merge sort and quick sort as canonical D&C algorithms, look at binary search through the same lens, walk through the divide-and-conquer maximum subarray algorithm, and meet the closest-pair-of-points problem in 1D. Along the way the lesson formalizes the Master Theorem template `T(n) = aT(n/b) + f(n)` and shows you how to read time complexity off it without solving the recurrence by hand. It also draws the line between D&C (independent subproblems) and DP (overlapping subproblems) so you can spot which paradigm fits. In **Recursion Fundamentals**, you saw recursion as one frame calling another. D&C is the case where a frame makes _multiple_ recursive calls and combines their results. Next, **Matrix Algorithms** turns to two-dimensional arrays.

Naive recursive Fibonacci computes `fib(40)` in seconds, `fib(50)` in minutes, and gives up on `fib(60)`, all because it recomputes the same subproblems exponentially many times. Cache the result of each `fib(k)` the first time you compute it and the same recursion runs in linear time. That single change, remembering answers, is the entire content of dynamic programming. **Dynamic Programming (Intro)** turns that observation into a complete problem-solving framework. You will identify overlapping subproblems and optimal substructure (the two properties a problem must have for DP to apply), and master both approaches: top-down memoization (recursion plus a cache) and bottom-up tabulation (iteratively filling a table). Classic 1D problems include Fibonacci, climbing stairs, coin change, house robber, and a first look at Kadane's algorithm. The lesson teaches you to define state precisely ("what does `dp[i]` represent?"), write the transition ("how does `dp[i]` follow from earlier states?"), set base cases, and apply rolling-variable space optimization that drops `O(n)` to `O(1)`. In **Recursion Fundamentals**, you treated each recursive call as a stack frame. Memoization just attaches a cache so identical inputs return immediately. Next, **Bit Manipulation (Intro)** turns to a different toolkit, where bitwise operators give elegant `O(1)` solutions.

Two players take turns removing stones from piles, the player who takes the last stone wins, and the entire winning strategy boils down to one calculation: XOR all pile sizes together, and you win if and only if the result is non-zero. That is Nim, and the surprise is not that it has a strategy but that the strategy is so compact. The Sprague-Grundy theorem extends the same idea to every impartial combinatorial game. **Game Theory** introduces the algorithmic side of two-player game analysis. You will work through Nim and its XOR strategy, then see how the Sprague-Grundy theorem assigns a Grundy number (nimber) to every position and how XOR-of-nimbers solves any sum of games. The lesson then moves to general game trees: minimax for optimal play, alpha-beta pruning for cutting branches that cannot affect the result, and move ordering for better pruning. You will analyze game states using DP, classifying positions as winning or losing by computing backward from terminal states, and meet retrograde analysis as a complete-game-state technique. In **Dynamic Programming (Intro)**, you learned to recurse on subproblems and cache results. **Recursion Fundamentals** gave you the call-stack model behind minimax and Grundy computation. Game theory recasts those tools as adversarial search. Next, **Randomized Algorithms** turns to a different way of taming worst-case inputs.

The mathematical definition `factorial(n) = n * factorial(n - 1)` defines a function in terms of itself, with `factorial(0) = 1` as the stopping point. That two-line definition is also a complete program if your language lets a function call itself. Recursion is what turns self-referential definitions into runnable code, and many problems (tree traversal, graph search, divide and conquer, dynamic programming) describe themselves most naturally that way. **Recursion Fundamentals** breaks down how that machinery actually works. You will learn to identify a base case (when the recursion stops) and a recursive case (how the problem reduces to a smaller instance), trace the call stack as frames are pushed and popped, and reason about return values flowing back up the chain. Examples run through factorial, naive Fibonacci, sum of an array, and integer power, plus a first look at recursion-tree intuition, tail recursion, stack overflow, and the `O(depth)` space cost of deep recursion. In **How to Read Code (JS & Python)**, you saw functions call other functions. **Debugging by Tracing** taught you to follow those calls step by step. Recursion is the case where the function on the call stack is the same function, again and again, with smaller inputs each time. Next, **Backtracking (Intro)** extends recursion with an explicit undo step to systematically explore combinatorial search spaces.

An invert-binary-tree problem famously got Max Howell rejected from Google in 2015, and the joke landed because the canonical solution is three lines of recursion. Trees show up everywhere in interviews precisely because they reward a particular kind of thinking: the answer for a node is almost always a function of the answers for its left and right subtrees, computed recursively, combined at the parent. **Tree Algorithms** trains that decomposition habit across a wide range of problems. You will implement BST insert, search, delete, validation, and the kth-smallest in-order trick. You will compute lowest common ancestor in both a generic binary tree and a BST. You will measure height, diameter, and width, and walk through path-sum problems, root-to-leaf enumeration, and the deceptively tricky maximum-path-sum-between-any-two-nodes. Structural operations include invert, mirror check, flatten to linked list, and serialize and deserialize. The lesson finishes with reconstructing a tree from inorder plus preorder or inorder plus postorder. In **Trees: Binary Tree Fundamentals**, you learned how nodes, children, and the four traversal orders work. **Recursion Fundamentals** gave you the call-stack mental model that every tree algorithm here relies on; tree recursion is essentially recursion with two recursive calls per frame. Next, **Graph Algorithms (Core)** removes the tree assumption (no cycles, no shared nodes) and tackles the more general traversal problems that result.