DSA sheet · Recursion Patterns
Recursion DSA Notebook
My study notes from the Recursion Patterns playlist. Each page is written so that a beginner (or me, after forgetting everything) can read it once and understand the base case, the recursive case, why trusting the smaller call works, the Python code line by line, and a full dry run with the recursion tree and the call stack drawn.
The one idea behind every page
A recursive function solves a big problem by calling itself on a smaller version of the same problem, and a base case stops it when the problem is small enough to answer directly.
The shape of the calls decides the cost: one call per level (a chain, n levels), two or more calls (a branching tree, up to 2ⁿ calls), or halving each time (log n levels).
The shape of the calls decides the cost: one call per level (a chain, n levels), two or more calls (a branching tree, up to 2ⁿ calls), or halving each time (log n levels).
Every page follows the same order:
① question in simple words → ② constraints → ③ intuition → ④ base case & recursive case from examples → ⑤ approach steps → ⑥ code → ⑦ line by line → ⑧ recursion tree + call stack dry run → ⑨ complexity & remember
Start here
One call per step (linear)
Halving the problem (logarithmic, divide & conquer)
- 3Pow(x, n)log n
- 6Divide & Conquer (Binary Search)concept
- 8Median of Two Sorted Arraysdivide & conquer
Many calls per step (non-linear / branching)
Numbers are the order in the playlist. "Next →" at the top of each page follows that order.