Recursive Functions: The rec Keyword

The rec keyword is used together with the let keyword to define a recursive function.

Syntax

// Recursive function:
let rec function-name parameter-list =
    function-body

// Mutually recursive functions:
let rec function1-name parameter-list =
    function1-body

and function2-name parameter-list =
    function2-body
...

Remarks

Recursive functions - functions that call themselves - are identified explicitly in the F# language with the rec keyword. The rec keyword makes the name of the let binding available in its body.

The following example shows a recursive function that computes the n^th Fibonacci number using the mathematical definition.

let rec fib n =
    match n with
    | 0 | 1 -> n
    | n -> fib (n-1) + fib (n-2)

Note

In practice, code like the previous sample is not ideal because it unnecessarily recomputes values that have already been computed. This is because it is not tail recursive, which is explained further in this article.

Methods are implicitly recursive within the type they are defined in, meaning there is no need to add the rec keyword. For example:

type MyClass() =
    member this.Fib(n) =
        match n with
        | 0 | 1 -> n
        | n -> this.Fib(n-1) + this.Fib(n-2)

let bindings within classes are not implicitly recursive, though. All let-bound functions require the rec keyword.

Tail recursion

For some recursive functions, it is necessary to refactor a more "pure" definition to one that is tail recursive. This prevents unnecessary recomputations. For example, the previous Fibonacci number generator can be rewritten like this:

let fib n =
    let rec loop acc1 acc2 n =
        match n with
        | 0 -> acc1
        | 1 -> acc2
        | _ ->
            loop acc2 (acc1 + acc2) (n - 1)
    loop 0 1 n

Generating a Fibonacci number is a great example of a "naive" algorithm that's mathematically pure but inefficient in practice. While this is a more complicated implementation, several aspects make it efficient in F# while still remaining recursively defined:

• A recursive inner function named loop, which is an idiomatic F# pattern.
• Two accumulator parameters, which pass accumulated values to recursive calls.
• A check on the value of n to return a specific accumulator.

If this example were written iteratively with a loop, the code would look similar with two different values accumulating numbers until a particular condition was met.

The reason why this is tail-recursive is because the recursive call does not need to save any values on the call stack. All intermediate values being calculated are accumulated via inputs to the inner function. This also allows the F# compiler to optimize the code to be just as fast as if you had written something like a while loop.

It's common to write F# code that recursively processes something with an inner and outer function, as the previous example shows. The inner function uses tail recursion, while the outer function has a better interface for callers.

Starting with F# 8.0, you can use the TailCall attribute to explicitly state your intention of defining a tail-recursive function to the compiler. The compiler will then warn you if your function makes non-tail recursive calls. You can use the attribute on methods and module-level functions.
For example, using it on the first fib definition:

[<TailCall>]
let rec fib n =
    match n with
    | 0 | 1 -> n
    | n -> fib (n-1) + fib (n-2)

would trigger compiler warnings about the two non-tail recursive calls.

Mutually Recursive Functions

Sometimes functions are mutually recursive, meaning that calls form a circle, where one function calls another which in turn calls the first, with any number of calls in between. You must define such functions together in one let binding, using the and keyword to link them together.

The following example shows two mutually recursive functions.

let rec Even x = if x = 0 then true else Odd(x - 1)
and Odd x = if x = 0 then false else Even(x - 1)

Recursive values

You can also define a let-bound value to be recursive. This is sometimes done for logging. With F# 5 and the nameof function, you can do this:

let rec nameDoubles = nameof nameDoubles + nameof nameDoubles

See also

• Functions