Recursive algorithms that halve the problem size use space for the call stack. For example, binary search's recursive version has recursion depth .
Each recursive call adds a stack frame. With levels of recursion, you use stack frames, each holding a constant amount of data.
You can often convert recursive solutions to iterative ones to reduce space from to , but the time complexity stays the same.