Example of Space Inefficiency

int factorial(int n)
{ return (n==0) ? 1 : n * factorial(n-1); }

To compute factorial(20) requires 21 words of local memory:

factorial(20) -- allocate 1 word of memory,
   call factorial(19) -- allocate 1 word of memory,
        call factorial(18) -- allocate 1 word of memory,
              .
               .
                .
                   call factorial(2) -- allocate 1 word of memory,
                        call factorial(1) -- allocate 1 word of memory,
                             call factorial(0) -- allocate 1 word of memory,

at this point 21 words of memory and 21 activation records have been allocated.

                             return 1.         -- release  1 word of memory.
    
                        return 1*1.       -- release  1 word of memory.
                   return 2*1.       -- release  1 word of memory.

Yet, as we shall see later, it is trivial to modify our solution to produce an algorithm that executes in constant space.