Prove that the algorithm shown above for computing n! when n is a non-negative integer is correct.

Question

procedure factorial(n: nonnegative integer)

if n=0 then return 1

else return n . factorial(n-1)

{output is n!}

Answer 1

Ex. N=4

Factorial(4)=

4* factorial(3)=

4*3*factorial(2)=

4*3*2*factorial (1)=

4*3*2*1*factorial(0)=

4*3*2*1*1=

24

Done

You can then argue by induction that it will work for any positive integer N

Since N! Is correct then

(N+1)! = (n+1)*n! Must also be correct

Except for possible overflow error