Question-78

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.

 

 

Leave a Reply