Ch.6 Introduction to ML programming

§ 6.16. Loop and tail recursion

The basis of designing a loop program are the following.

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

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

  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 6.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.