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 integerslet 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 ...