3.7 Factorial

Factorial is a classic example of recursive procedure. A recursive function may be used to calculate the factorial of a natural number. The general form of factorial(n) is 1*2*..*n, but recall that n must be at least zero, and factorial(0) is 1.

Time Complexity
It will go through all function calls with input from 1 to n, which takes linear time, so the time complexity is O(n)

SpaceComplexity
Recursion holds the stack memory for function calls, so the space complexity strictly depends on the number of function calls, which is O(n).
(Note that iterative method can make space complexity to be reduced to O(1))

Pseudo Code

factorial(n)
   if n == 0 then
       return 1
   else
       return n * factorial(n - 1)
© The University of Hong Kong Algorithms Library - hkual@cs.hku.hk