[Solved]: Since we need space for recursive calls, is the space complexity of the recursive factorial is n?

Problem Detail: 

As Wikipedia says, quickSort needs O(log n) extra space when the following conditions are met:

• In-place partitioning is used. This unstable partition requires O(1) space.
• After partitioning, the partition with the fewest elements is (recursively) sorted first, requiring at most O(log n) space. Then the other partition is sorted using tail recursion or iteration, which doesn't add to the call stack. This idea, as discussed above, was described by R. Sedgewick, and keeps the stack depth bounded by O(log n).

Now please consider the following method computing the factorial of n recursively:

private static int fact(int n) {     if (n == 1) {         return n;     }     return n * fact(n - 1); } 

There is no tail recursion. Does it mean that we need O(n) extra space for the call stack?

Asked By : Maksim Dmitriev

Answered By : D.W.

Yes, you need up to $n$ stack frames for the recursion. Therefore, you'll need $\Theta(n)$ space for these stack frames.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/44010