Recursive Functions: The rec Keyword
rec keyword is used together with the
let keyword to define a recursive function.
// 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 ...
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 nth Fibonacci number using the mathematical definition.
let rec fib n = match n with | 0 | 1 -> n | n -> fib (n-1) + fib (n-2)
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
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
nto 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
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
[<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)
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