You are previewing Programming F#.

Programming F#

Cover of Programming F# by Chris Smith Published by O'Reilly Media, Inc.
O'Reilly logo

Tail Recursion

You can now use lists to process large amounts of data efficiently, but there is trouble looming. Because lists are immutable, the primary way they are built is with recursion. Consider the following two ways to construct two lists of integers:

> // Creating a List<_> of 100,000 integers
open System.Collections.Generic

let createMutableList() =
    let l = new List<int>()
    for i = 0 to 100000 do
        l.Add(i)
    l;;

val createMutableList : unit -> List<int>

> // Creating a list of 100,000 integers
let createImmutableList() =
    let rec createList i max =
        if i = max then
            []
        else
            i :: createList (i + 1) max
    createList 0 100000;;

val createImmutableList : unit -> int list

Both solutions look identical, but the createImmutableList function won’t work. (In fact, it will crash.) I’ll explain the reason why the function is flawed as well as how to fix it by introducing tail recursion.

You may have heard of tail recursion before; in fact, you may have even written tail-recursive functions before without even knowing it. Tail recursion is a special form of recursion, where the compiler can optimize the recursive call to not consume any additional stack space. When a function makes a recursive call, the rest of the calling function may still need to execute some code, so the state of what’s left to execute is stored on the stack.

However, as recursive functions call themselves deeper and deeper, the limited stack space can be exhausted, leading to an unrecoverable type of CLR error: the dreaded ...

The best content for your career. Discover unlimited learning on demand for around $1/day.