Tail recursion

Tail recursion is a special case of recursion where the calling function does no more computation after making a recursive call.
...
Tail recursion is important because it can be implemented more efficiently than general recursion. When we make a normal recursive call, we have to push the return address onto the call stack then jump to the called function. This means that we need a call stack whose size is linear in the depth of the recursive calls. When we have tail recursion we know that as soon as we return from the recursive call we're going to immediately return as well, so we can skip the entire chain of recursive functions returning and return straight to the original caller. That means we don't need a call stack at all for all of the recursive calls, and can implement the final call as a simple jump, which saves us space.

Matt Lewis, Stack Exchange

F#'s support for tail call optimisation "allows the F# compiler to optimize [a tail recursive function] to be just as fast as if you had written something like a while loop".

Let's take a look at an example.

Without tail recursion - stack overflow exception

Imagine that we have the following Tree type and want to write a function that gets the values from all the leaves in the tree.

type Tree =
    | Leaf of int
    | Node of Tree list

Our first attempt might be a naive function that simply puts each leaf value into a list, and aggregates them at each node using List.collect.

let leaves tree =
    let rec loop tree =
        match tree with
        | Leaf n -> [ n ]
        | Node branches -> branches |> List.collect loop
    loop tree

Because the inner loop function isn't tail recursive (the state of a stack frame has to be maintained while recursing so that the later aggregation can happen), sufficiently deep input data will cause a stack overflow.

let makeTree depth =
    let rec loop currentDepth acc =
        if currentDepth = depth then
            acc
        else
            let children = if currentDepth > 0 && currentDepth % 10 = 0 then [ acc; Leaf currentDepth ] else [ acc ]
            loop (currentDepth + 1) (Node children)
    loop 0 (Leaf 0)

makeTree 1_000_000 |> leaves // Stack overflow

With tail recursion - no stack overflow exception

Remember, for a function to be tail recursive, there must be no more computation after making a recursive call.

One way of finishing computation before recursing is to start from the root node and look at successive "generations" (nodes of equal distance from the root) in turn, completely processing the leaves in that generation before moving to the next one. The key "trick" here is that the input to the inner loop can be a list of Trees, rather than a single Tree.

let children tree =
    match tree with
    | Leaf _ -> []
    | Node branches -> branches

let leavesTailRecursive tree =
    let rec loop accumulatedLeaves currentGen =
        let currentGenLeaves = currentGen |> List.choose (function Leaf n -> Some n | Node _ -> None)
        // Note: using (@) is inefficient; there are more efficient alternatives (some of which are tail recursive).
        let accumulatedLeaves = currentGenLeaves @ accumulatedLeaves

        match currentGen |> List.collect children with
        | [] -> accumulatedLeaves
        | nextGen -> loop accumulatedLeaves nextGen

    loop [] [ tree ]

makeTree 100_000_000 |> leavesTailRecursive // Ok

Tail recursion isn't always necessary

The tail recursive function above is a little bit harder to understand than the recursive version. It's useful to know that this optimisation exists, but in many cases sticking with a non-tail recursive implementation is fine. In plenty of use cases you know that the call stack is never going to be so deep that stack overflows are a concern.

Summary

F# has support for tail call optimisation: if the only recursive call in a recursive function is in the tail position (the very last thing before returning), then the F# compiler can optimise away the call stack. This can be useful when you're dealing with deep recursive data structures and are facing stack overflows. Making a function tail recursive can sometimes detract from readability, so make sure your function needs to be tail recursive before worrying about whether or not it is.