Question

Develop a rule of inference for verifying recursive programs and use it to verify the recursive algorithm for computing factorials given as Algorithm 1 in Section 5.4.

\(\)

Short answer

The procedure for\(n\) gives us,\({\rm{n}}\left( {n - 1} \right)!\)

Step-by-step solution

Introduction

Rule of interference means a valid argument is one where the conclusion follows from the truth values of the premises. Rules of Inference provide the templates or guidelines for constructing valid arguments from the statements that we already have.

Basis step

For,\(n = 1\)in this case, the ‘then’ clause is executed.

So the procedure gives 1 which is 1!

Therefore, basis step is correct.

Inductive step

Let u assume that the procedure works fine for\(\left( {n - 1} \right)\).

We will show that it gives correct value for\(n\).

And the procedure gives us \(n\) times the value that we got from input\(\left( {n - 1} \right)\)

Conclusion

Since it have assumed that inductive hypothesis is correct, then the output of\(\left( {n - 1} \right)\)is\(\left( {n - 1} \right)\)!

Therefore, the procedure for\(n\)gives us,

\({\rm{n}}\left( {n - 1} \right)!\)which is\(n!\)

Hence proved