SML# Document Version 3.7.1
7 Introduction to ML programming

7.16 Loop and tail recursion

The basis of designing a loop program are the following.

  1. 1.

    Design a state of computation that leads to the desired result.

  2. 2.

    Set up variables that hold the computation state, and the progress of computation.

  3. 3.

    Write a code to iteratively update the variables until the desired result is obtained.

A program that sums up 1 through n can be designed as follows.

  • the state of computation: s=i*(i+1)*...*n(1in)

  • variables:s,i

  • update code: s:=s+1;i:=i-1

This design yields the C function fact in Section 7.15.

This way of designing an iterative computation is not limited to procedural languages. A code to update the current state can be understood as a function that takes the current state and generate the next state. Then a loop program is represented a recursive function that takes the current state and call itself with the generated next state. The loop code of the C function fact can be written as the following ML code:

  fun loop (0, s) = s
     | loop (n, s) = loop (n - 1, s * n)
  fun fact n = loop (n, 1)

This form of recursion is called tail recursion, which is evaluated efficiently.