Recursion in Standard ML

Our example demonstrates recursive functions in Standard ML. Here’s a classic example of factorial calculation using recursion.

(* This fact function calls itself until it reaches the
   base case of fact(0). *)
fun fact 0 = 1
  | fact n = n * fact(n-1)

(* Main function to test our factorial function *)
fun main() =
    let
        val result = fact 7
        val _ = print("Factorial of 7: " ^ Int.toString(result) ^ "\n")

        (* In Standard ML, we can define local recursive functions 
           without explicit type annotations *)
        fun fib n =
            if n < 2 then n
            else fib(n-1) + fib(n-2)

        val fibResult = fib 7
        val _ = print("Fibonacci of 7: " ^ Int.toString(fibResult) ^ "\n")
    in
        ()
    end

(* Call the main function *)
val _ = main()

In this Standard ML code:

1. We define the fact function using pattern matching. The base case fact 0 = 1 is explicitly defined, and the recursive case fact n = n * fact(n-1) handles all other inputs.

2. The main function demonstrates the usage of both the fact function and a locally defined fib function.

3. In Standard ML, we don’t need to explicitly declare the type of recursive functions before defining them, as was necessary in the original example. The language’s type inference system can handle recursive definitions.

4. We use let ... in ... end construct to define local bindings within the main function.

5. String concatenation is done using the ^ operator, and we use Int.toString to convert integers to strings for printing.

To run this program, you would typically save it in a file (e.g., recursion.sml) and then use an Standard ML interpreter or compiler. For example, with the Standard ML of New Jersey (SML/NJ) system:

$ sml recursion.sml
Factorial of 7: 5040
Fibonacci of 7: 13

This demonstrates how recursion works in Standard ML, both for explicitly defined functions like fact and for locally defined functions like fib.