## With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

No credit card required

# 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;;

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

## With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

No credit card required