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.