The fun syntax allows recursive function definitions. The function name funName being defined in this declaration can be used in the defining body expr of this declaration.

A recursive function can naturally be designed in the following step.

1. 1.

   Presume the expected behavior of the function funName for all the cases, and assume that such function exists.

2. 2.

   For each case of the parameter param, write the expr using param and funName for that case.

For example，function fact shown in Section 7.2 is designed in the following steps.

1. 1.

   Assume that you have the function fact that correctly computes the factorial of any non-negative number.

2. 2.

   Using fact, write down the body of each case as follows.

   1. (a)

      If the parameter is 0, then since $0!=1$, the expr is 1,

   2. (b)

      otherwise, from the definition of the factorial function, the expr is n * fact(n - 1).

This yields the following recursive function definition.

# fun fact 0 = 1
>   | fact n = n * fact (n - 1);
val fact = fn : int -> int

The summation function sum and exponentiation function power, for example, can similarly be written by presuming that these functions were already given.

fun sum 0 = 0
  | sum n = n + sum (n - 1)
fun power 0 = 1
  | power n = c * power (n - 1)

Under the presumed behavior of sum and power, each case correctly computes the expected value, and therefore the entire definitions are correct.

This is a recursive way of reasoning. Think in this recursive way, and you can naturally write various recursive functions.