# 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

## Feedback

Submit and view feedback for