**Question-78**

A Recursive Algorithm for Computing n!

**Procedure **factorial (n : nonnegative integer)

if n = 0 then

return 1

else return n ·factorial (n – 1 )

{ output is n!}

Trace the algorithm given above when it is given **n = 5** as input. That is , show all steps used by Algorithm **1** to find **5!**.

**Solution**

First , we use the recursive step to write 5! = 5·4! . We then use the recursive step repeatedly to write 4! = 4· 3!, 3! = 3·2!,2! = 2·1!, and 1! = 1·0! . Inserting the value of 0! = 1 , and working back through the steps, we see that 1! = 1·1 = 1,2! = 2·1! = 2·1 = 2, 3!= 3·2! = 3·2 = 6, 4! = 4·3! = 4·6 = 24, and 5! = 5·4! = 5·24 = 120.