##### ###### ##### ### # # ### # # ###### ## ## ## ## ## ## ## # # # # # ## ##### #### ##### # # # # # # # #### ## # ## ## ## ## # # # # # ## ## # ###### ## ### # ### # ######
##### ###### ##### ### # # ### # # ###### ## ## ## ## ## ## ## # # # # # ## ##### #### ##### # # # # # # # #### ## # ## ## ## ## # # # # # ## ## # ###### ## ### # ### # ######
(Call stack depth)
Every recursive call adds a frame to the call stack. If you recurse n times, you use O(n) space.
Factorial and Fibonacci (without memoization) recurse linearly, so space is O(n). Binary search recurses log n times, so space is O(log n).
Tail-call optimization can reduce this to O(1), but not all languages support it.
