7. Recursion, Call Stack & Dynamic Programming
Master call stack memory frames, base cases, memoization, and top-down vs bottom-up DP.
The "WHY" Core Principle
Naive recursive Fibonacci recalculates identical subproblems millions of times. Memoization stores subproblem outputs in a hash table dict, dropping operations to O(N).
Interactive Visualizer
Interactive Big-O Complexity 2D Graph & Operation Profiler
Move the slider to observe operation growth curves smoothly scale as input size N increases.
Operations at N = 25
def get_first(arr):
return arr[0] # Direct memory offsetAnalogy: Jumping directly to a page number in an indexed book.
Operations at N = 25
while low <= high:
mid = (low + high) // 2 # Halve search spaceAnalogy: Finding a name in a phonebook by opening to the middle repeatedly.
Operations at N = 25
for item in arr:
if item == target: return True # Single sweepAnalogy: Reading every page in a book line by line from front to back.
Operations at N = 25
def merge_sort(arr):
# Divide array (log N) & merge halves (N)Analogy: Sorting a deck of cards by splitting into 2 piles recursively.
Operations at N = 25
for i in range(n):
for j in range(i + 1, n): # Compare every pairAnalogy: Comparing every card in a deck against every other card.
Operations at N = 25
def fib(n):
return fib(n-1) + fib(n-2) # 2 recursive calls per stepAnalogy: Trying every possible combination password lock.
Notice how O(1) and O(log N) remain near the bottom of the graph even as $N$ grows, while O(N²) and O(2ⁿ) curve steeply upward. This difference is why selecting the correct data structure prevents CPU bottlenecks!
Interactive Code Snippets (1 Lessons)
Recursion Benchmark: Naive O(2ⁿ) vs Memoized O(N)
Compare recursive Fibonacci without cache vs with memoization cache.
Memoization stores `memo[n]` in a dict to return cached answers in O(1) time.
CPython C Struct Detail: Python `@functools.lru_cache` decorator wraps function calls with a C hash table cache.
Recursion Benchmark: Naive O(2ⁿ) vs Memoized O(N)
Pyodide WASM EngineType, edit code, and click 'Run & Profile' to see live runtime ms and operation count!