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.