Lesson 15: Recursion, backtracking & intro DP

You've reached the capstone — well done! Let's start with a matryoshka doll: a doll with a smaller doll inside, down to the tiny one that no longer opens. That's exactly 'recursion': a function that calls itself on a smaller version of the same problem, and the doll that won't open is the 'base case

Recursion is like a Russian nesting doll: each doll opens a smaller one, until you reach the tiny one that doesn't open (the base case). Backtracking is trying a path, and if it's a dead end — closing it and trying another. Memoization is jotting answers you already computed on a note, so you don't compute them again.

recursion & backtracking: Recursion: a function that calls itself on a smaller subproblem until a base case. Backtracking: try a choice, recurse, and undo the choice to explore all possibilities.
base case: The condition that stops the recursion and returns a direct answer without another call — without it the recursion never ends.
memoization: Caching results of subproblems (e.g. in a dict) so they aren't recomputed — it avoids repeated work and can dramatically speed things up (e.g. naive Fibonacci from O(2ⁿ) to O(n)).