Example 1: Factorial

Let's look at the classic problem of computing the factorial of a number. We'll discuss both the iterative case and the recursive solution.

Iterative Solution

The pseudo-code for the iterative solution is given below:

1Function: factorial(n)
2Returns:  Factorial of the number n
3
4Method:
5result = 1
6for i = (1..n)
7{
8	result = result * i
9}
10
11return result

When we look at the factorial function, we can see that it uses the variable n, result and i. No matter how large the number n is, we always use these three variables to compute the factorial. Hence, the space complexity of this function is O(1). It means we can compute the factorial of any number in constant space.

Recursive Solution

The following is a recursive solution to computing the factorial:

1Function: factorialRecursive(n)
2Returns:  Factorial of the number n
3
4Method:
5if n==0
6	return 1
7
8result = factorialRecursive(n-1)*n
9return result

When we look at the recursive solution, we can see that there are n recursive calls to factorialRecursive function. Each call maintains a record on the activation stack. The stack holds a copy of the variables n and result. Hence, the space complexity of the recursive version of factorial is O(n).