Prove that the factorial function n! is primitive recursive. This proof should f

Question

Prove that the factorial function n! is primitive recursive. This proof should follow the following pattern:

You start with a 3-dot expression

First you write a for-loop corresponding to this function

Then you describe this for-loop in mathematical terms

Then, to prepare for a match with the general expression for primitive recursion, you rename the function to f and the parameters to n1, ..., m

Then you write down the general expression of primitive recursion for the corresponding k

Then you match: find g and h for which the specific case of primitive recursion will be exactly the functions corresponding to initialization and to what is happening inside the loop

Then, you get a final expression for the function n! that proves that this function is primitive recursive, i.e., that it can be formed from 0, ki, and by composition and primitive recursion.

Explanation / Answer

Factorial of a number is defined as n! = 1 * 2 * … * n.

Program output should look as follows:
0! = 1
1! = 1
2! = 2
3! = 6
4! = 24
5! = 120
6! = 720
7! = 5040
8! = 40320
9! = 362880
10! = 3628800
11! = 39916800
12! = 479001600
13! = 6227020800
14! = 87178291200
15! = 1307674368000
16! = 20922789888000

Note that this example can be implemented in several ways:

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.