Recursion & the Call Stack

Function

Input n 8

Memoize (cache repeated calls)

Playback speed 6/s

Live State

Stack: —

Last return: —

Calls so far

Stack depth

Max depth

Cache hits

Legend

Active call (on the stack) Returned normally Returned from cache

How it works

Every recursive call pushes a new stack frame holding that call's arguments; the call only pops off — and returns a value to its parent — once its own recursive calls have finished. Drawing every call as a node and every "calls" relationship as an edge produces the recursion tree on the left; the column on the right is the actual call stack at this instant, i.e. the path from the root to whichever node is currently active.

fib(n) = n                       if n <= 1
fib(n) = fib(n-1) + fib(n-2)      otherwise

Calls made (no memo):  T(n) = T(n-1) + T(n-2) + 1  =  2*fib(n+1) - 1
Calls made (memoized): at most  2n + 1
Max stack depth (either way):   n

Without memoization, fib(n-2) gets recomputed from scratch every time it appears as a sub-problem of fib(n-1), so the call count grows exponentially — O(2ⁿ). Turning on Memoize caches every fib(k) the first time it's computed; every later call with the same k returns instantly from the cache (shown in blue) instead of re-expanding its own sub-tree, dropping the work to O(n). Factorial has only one recursive call per frame, so its tree is a single chain and memoization would not help it — the checkbox is disabled in that mode.

Orange node = currently on the call stack, not yet returned.
Green node = returned after doing real work.
Blue node = returned instantly from the memo cache.

⚠ Couldn't load the 3D engineThree.js failed to load from the CDN. Check your connection and reload.

Recursion & the Call Stack: Fibonacci vs Factorial