Recursive Functions

A recursive function is one that may make calls to itself in its body. In ATS, the keyword fun is used to initiate the definition of a recursive function. Clearly, a non-recursive function is just a special kind of recursive function: the kind that does not make any calls to itself in its body. If one prefers, one can use fun (instead of fn) to initiate the definition of a non-recursive function.

I consider recursion the most enabling feature a programming language can provide. With recursion, we are enabled to do problem-solving based on a strategy of reduction: In order to solve a problem to which a solution is difficult to find immediately, we reduce the problem to problems that are similar but simpler, and we repeat this reduction process if needed until solutions become apparent. Let us now see some concrete examples of problem-solving that make use of this reduction strategy.

Suppose that we want to sum up all the integers ranging from 1 to n, where n is a given integer. This can be readily done by implementing the following recursive function sum1:

fun sum1
  (n: int): int =
  if n >= 1 then sum1 (n-1) + n else 0
// end of [sum1]

We can also solve the problem by implementing the following recursive function sum2 that sums up all the integers in a given range:

fun sum2
  (m: int, n: int): int =
  if m <= n then m + sum2 (m+1, n) else 0
// end of [sum2]

Given integers m and n, there is another strategy for summing up all the integers from m to n: If m does not exceed n, we can find the sum of all the integers from m to (m+n)/2-1 and then the sum of all the integers from (m+n)/2+1 to n and then sum up these two sums and (m+n)/2. The following recursive function sum3 is implemented precisely according to this strategy:

fun sum3
  (m: int, n: int): int =
  if m <= n
    then let
      val mn2 = (m+n)/2
    in
      sum3 (m, mn2-1) + mn2 + sum3 (mn2+1, n)
    end // end of [then]
    else 0 // end of [else]
// end of [sum3]