The factorial function

Documentation and user's manual

Table of contents

OCaml programs

The factorial function

In mathematics, the factorial of a natural number n is the product of all positive integers less than or equal to n, with the convention that the product of no numbers at all is 1. This is written as n! and pronounced n factorial.

The factorial function is the function that maps any natural number n to n!.

This is a recursive relation n! = n (n - 1)! for any positive natural number n.

Yet this recursive relation does not give a definition of the factorial function. To get such a definition a basis relation is also needed. The correct basis relation is 0! = 1

From the above basis and recursive relations this Objective Caml recursive definition of the factorial function immediately follows: let rec f = function n -> (* n >= 0 *) if n = 0 then 1 else n * f (n - 1) in f The type of this value is  int -> int .

This code shows that in Objective Caml A functional value can be recursively defined with no name bound to it. In the written code the name  f  is only locally bound to the functional value. So, even anonymous functions can be recursively defined.

Yet a name, for instance  fact , can be bound to such a functional value: let rec fact = function n -> (* n >= 0 *) if n = 0 then 1 else n * fact (n - 1)

Consider the evaluation of fact (i) where i is bound to a non-negative value (obeying the specification given by the comment (* n >= 0 *)). Look at the sub-expression fact (n - 1) in the code. During the evaluation of fact (i), each time the sub-expression n - 1 is evaluated, its value is closer to the basis than the value of the formal parameter n. This guarantees the termination of the evaluation of fact (i). Note that the assumption of i bound to a non-negative value is crucial.

The factorial function

Documentation and user's manual

Table of contents

OCaml programs