Step-by-Step Space Complexity Analysis

Step 1: Recognize the Depth of Recursion

The depth of recursion refers to the maximum number of recursive calls active at any one time.

1. For factorial(n), the recursion depth depends on n because each call to factorial makes a single recursive call with n - 1.
2. Starting with factorial(n), the function calls factorial(n - 1), then factorial(n - 2), and so on, until reaching the base case when n = 0 or 1.
3. So, if n = 5, the call stack will hold factorial(5), factorial(4), factorial(3), factorial(2), and factorial(1) before reaching the base case.

In this case, the recursion depth is n.

Step 2: Determine Memory Used per Recursive Call (Stack Frame)

Each recursive call to factorial requires a stack frame. A stack frame is a memory block that stores:

• Parameters (n in this case)
• Local variables (none here, as there’s no additional variable in the function)
• Return address (to continue execution after a recursive call)

In general, each call to factorial has constant space usage, or O(1), because the amount of memory required per call does not change with n.

Step 3: Calculate Total Space Complexity

The total space complexity is the product of the recursion depth and the space per call.

1. Recursion Depth: O(n) (from Step 1).
2. Space per Call: O(1) (from Step 2).

Thus, the overall space complexity of factorial(n) is:

Time Complexity = O(n) \times O(1) = O(n)

In recursive functions, each call occupies a new place in memory, even though it performs a similar task as the previous call. Each call is saved in memory until it completes, which is why the stack grows with each recursive call. For factorial(n), the stack holds up to n calls at once, so it grows linearly with n.