Interactive Lab · Python Foundations

A function that calls itself, why isn't that an infinite loop?

Recursion sounds like a snake eating its tail. But each call works on a smaller input, piling a new frame onto the call stackuntil it hits a base case that stops the descent. Then the stack unwinds, returning values back up to whoever asked. Watch the pile grow and collapse, then flip on memoization to see it turn exponential work linear.

🎬 Watch the 45-second explainer, then try it yourself below ↓

▶ The playground, step through the calls, watch the stack grow & unwind

The pile is the CALL STACK. A new call pushes a frame on top; a return pops it and flows its value back to the caller below.

running (top frame) paused, waiting on its child returned a value

stack depth 0 total calls 0 result

n (factorial) 5

110

🧭 Where this fits

Recursion + memoization is the shape of half of computing: file-system walkers, JSON parsers, compilers (recursive descent), React's component tree rendering, and memoization IS dynamic programming, functools.lru_cache, and React's useMemo. The exponential-to-linear collapse you just watched is among the most-asked interview transformations.

The code that's actually running, the highlighted line is executing now

🔮 Predict, then test

Switch to fibonacci, set n = 6, leave memoize off and hit Run. Predict first: how many total calls? (Naive fib(6) makes 25.) Notice the stack keeps re-descending to recompute fib(2), fib(3)… over and over. Now turn memoize on and Run again, total calls collapses. Why does caching turn an exponential number of calls into a linear one? (Hint: with a cache, each distinct fib(k) is computed once; every later request for it is a lookup, so you do work proportional to how many different k's existjust n of them, instead of the whole doubling tree.)

The takeaway

Your new mental model of recursion & the call stack

Recursion = a function calling itself on a smaller input until a base case stops it. No base case (or one you never reach) → infinite recursion → stack overflow.
Every call pushes a frame onto the call stack. A caller pauses, waiting on its child; when the child returns, its value flows back down and the caller resumes. The stack unwinds in the exact reverse order it was built.
Factorial is linearone straight chain of n frames down, then n returns back up. Naive fibonacci is exponential: it branches into two calls that recompute the same subproblems again and again (a doubling tree).
Memoization caches each result the first time. Overlapping subproblems become instant lookups, so fib drops from ~2ⁿ calls to just ~nexponential → linear, no new math, just remembering.

◈ Python Foundations Try: Big-O Complexity Continue the journey →