Factorial

A classic example of a recursive procedure is the function used to calculate the factorial of a natural number:

{\displaystyle \operatorname {fact} (n)={\begin{cases}1&{\mbox{if }}n=0\\n\cdot \operatorname {fact} (n-1)&{\mbox{if }}n>0\\\end{cases}}}

function factorial is:

input: integer n such that n >= 0

output: [n × (n-1) × (n-2) × … × 1]


    1. if n is 0, return 1
    2. otherwise, return [ n × factorial(n-1) ]


end factorial

The function can also be written as a recurrence relation:

$$b_n=nb_{n-1}$$

This evaluation of the recurrence relation demonstrates the computation that would be performed in evaluating the pseudocode above:

b4           = 4 * b3

             = 4 * (3 * b2)
             = 4 * (3 * (2 * b1))
             = 4 * (3 * (2 * (1 * b0)))
             = 4 * (3 * (2 * (1 * 1)))
             = 4 * (3 * (2 * 1))
             = 4 * (3 * 2)
             = 4 * 6
             = 24

You have no rights to post comments