Factorial (Primitive Recursion)

Definition

Factorial ( Primitive Recursion)

Factorial , with , is primitive-recursive. Its recursive equations are

The base returns ; each step multiplies the previous result by the next natural number . Thus

Here, is a constant with no arguments, is the successor function, is multiplication, and denotes a projection function.

Construction

Factorial has no unchanged parameters: its only input is the recursion argument. The base therefore takes no arguments and supplies the constant .

The step function receives the previous index and previous result . The projections select these two inputs:

If , then . Starting at , the successive factors therefore produce .

Example

Building successive factorials