Table of contents
Collapse the table of content
Expand the table of content

Recursive Functions: The rec Keyword (F#)

Den Delimarsky|Last Updated: 8/18/2017
1 Contributor

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


// Recursive function:
let rec function-nameparameter-list =

// Mutually recursive functions:
let rec function1-nameparameter-list =
and function2-nameparameter-list =


Recursive functions, functions that call themselves, are identified explicitly in the F# language. This makes the identifer that is being defined available in the scope of the function.

The following code illustrates a recursive function that computes the nth Fibonacci number.

let rec fib n =
   if n <= 2 then 1
   else fib (n - 1) + fib (n - 2)

In practice, code like that above is wasteful of memory and processor time because it involves the recomputation of previously computed values.

Methods are implicitly recursive within the type; there is no need to add the rec keyword. Let bindings within classes are not implicitly recursive.

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 the 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 = 1 then true
   else Even (x - 1)

See Also

Functions (F#)

© 2020 Microsoft