A helpful comment on a post over at HubFS by Brian McNamara really helped me wrap my mind around tail recursion and why it’s immensely important to understand in F#. Brian coined the phrase “tail recursion police”, hence the title 
Recursion pops up quite a bit in functional programming so it’s a good idea to understand the risks/tradeoffs/benefits. A gross simplification of an analogy would be:
For loops : C# :: Recursion : F#
Sure, you can do for-loops and imperative-style coding in F#, but it doesn’t showcase the beauty of the functional style programming that F# offers.
Recursive functions (in both C# and F#) are just functions that call themselves. They do so by pushing the current state of the function onto the stack, popping them off when calls start completing. Because the stack is a limited resource, it can be exhausted (StackOverflowException) if the function is called recursively too many times.
These kinds of runtime exceptions can be difficult to find unless explicitly tested for, leading to hard-to-find bugs. Oftentimes tests will only exercise simple cases of algorithms and then fail at runtime when large (real-world) inputs are used. After all, “everything works for small N”.
F#, however, has a very interesting feature where (under certain conditions), it can recognize recursive functions and perform a “tail call optimization”, turning the recursive function into a while-loop that uses no stack space whatsoever. This is called tail recursion.
The rule for tail-recursion is simple:
If the recursive call to the function is the very last thing that happens in the algorithm, then the function can be made tail-recursive.
In most cases a recursive algorithm can be expressed in both recursive and tail-recursive forms. Other times, it may not even be possible to implement a specific algorithm tail-recursively.
Let’s look at some examples.
Tail Recursive or Not?
One way to implement the “map” function that applies a specific function, f, to every element in a list would be:
let rec map f l =
match l with
| [] -> []
| h::t -> f h :: map f t
While this implementation easily expresses the algorithm (splitting a list into its head and tail, applying the function f to the head, and consing it to the list obtained from applying the function to the tail), it is NOT tail recursive! The recursive call to “map” must happen, then f is applied to h, and then the results are cons’d (:: operator). The recursive call to “map” is not last in this instance, so it’s not tail-recursive.
How can we make this map operation tail-recursive? Typically this involves 2 things — factoring out an inner loop that is recursive and threading an accumulator through that inner loop:
let mapTR f l =
let rec loop f2 l2 acc =
match l2 with
| [] -> acc
| h::t -> loop f2 t ((f2 h)::acc)
loop f l [] |> List.rev
In the 2nd-to-last line, f2 is applied to the head, then cons’d with the accumulator, and that result (along with f2 and the tail) are passed to the recursive call to “loop”. In this case, “loop” is the very last thing that happens, so the F# compiler can implement this tail-recursively.
Double-Check with Reflector
We can double-check that the F# compiler created a recursive function for the “map” case by using Reflector. While F#-compiled-to-IL-decompiled-to-C# can be a bit verbose thanks to all of the generics and partial function application (FastFunc), it can still be seen that the map function recursively calls itself.
If the Tail Recursion Police were out, we’d be totally busted.
For the “mapTR” case, the implementation is a bit hidden behind some closures, but can be found with a little work. The meat of the tail-recursive function is implemented with a while(true) loop! This is fantastic since it uses no stack space. The Tail Recursion Police would let us off clean on this one.
Sidenote: The List<T> type here is not the standard System.Collections.Generic.List<T>. It is a singly-linked list that is part of the F# core libraries. In F# the Generic.List<T> is known as ResizeArray<T> since it more resembles a resizable array than a singly-linked list.
Sidenote 2: I’ve heard some things about the “.tail” IL opcode, but don’t see it popping up anywhere in this code. The while loop seems more efficient to me than a recursive call that drops the current stack frame, though. I’m not entirely sure what the relationship is between the .tail opcode is and tail recursion in F#.
Let’s walk through another example and dig into a little more detail.
Kaboom! StackOverflowException Strikes
When working on some code over the weekend, I ran into the need for a slightly different version of List.map. The “map” function has the signature “(‘a -> ‘b) -> ‘a list -> ‘b list” — that is, it takes a function that takes a ‘a and returns a ‘b as well as a ‘a list to operate on, producing a ‘b list. It simply applies the given function to each item in the list and returns a new list with the result of each function application.
What I needed, however, was a method that took a list of one type and returned a list of another type, but applied a function that accepted a list of values and produces a resulting value. That is, I needed a function with a signature “(‘a list -> ‘b) -> ‘a list -> ‘b list”. When you think about this, I needed an algorithm that would operate on the initial list by calling a method by “snapping off” successive portions of the list, producing another list. So, if we had a list [1;2;3;4], the mapping function would be called in succession with input lists [1;2;3;4], [2;3;4], [3;4], [4], and []. Since it’s still doing a mapping, though making the entire list (instead of just the head of the list) available to the mapping function, I decided to call it “mapl” for “map list”.
My first stab at an implementation was straightforward:
module List =
let rec mapl f l =
match l with
| [] -> []
| h::t -> f l :: mapl f t
> let test = [1;2;3;4];;
val test : int list
> test |> List.mapl (printfn “%A”);;
[1; 2; 3; 4]
[2; 3; 4]
[3; 4]
[4]
Good so far. However, it’s not tail-recursive, so let’s see if we can break it:
> [1..100000] |> List.mapl List.hd;;
Process is terminated due to StackOverflowException.
Session termination detected. Press Enter to restart.
Kaboom! The Tail Recursion Police are already on the scene, cleaning up the remains of fsi.exe…
Tail-Recursion Tweaks and Performance
Ok, so let’s make this “mapl” function tail-recursive. I wanted to investigate 3 different approaches and compare the performance based on slight nuances between the implementations.
Here’s my code for mapl_tr1, mapl_tr2, and mapl_tr3:
module List =
let mapl_tr1 f l =
let rec loop l2 acc =
match l2 with
| [] -> acc
| h::t -> loop t ((f l2)::acc)
loop l []
let mapl_tr2 f l =
let rec loop f2 l2 acc =
match l2 with
| [] -> acc
| h::t -> loop f2 t ((f2 l2)::acc)
loop f l []
let mapl_tr3 f l =
let rec loop (f2, l2, acc) =
match l2 with
| [] -> acc
| h::t -> loop (f2, t, ((f2 l2)::acc))
loop (f, l, [])
You can see that we factored out an inner loop that is recursive, added an accumulator list, and made sure that the loop function call was the last operation before recursing.
- mapl_tr1: This function captures the function “f” (a closure) from within the inner loop.
- mapl_tr2: This function explicitly passes the function “f” to the inner loop to test if a closure slows things down
- mapl_tr3: This function creates tuples when passing values to the inner loop and recursing to test if tuples are faster than partial function applications
To test these functions out, I used a simple test harness:
let main () =
printfn “Tail Recursion Test”
let run_test m =
time_iter 10 (fun () -> [1 .. 100000] |> m List.hd |> ignore)
let methods = [List.mapl_tr1; List.mapl_tr2; List.mapl_tr3]
let names = ["mapl_tr1"; "mapl_tr2"; "mapl_tr3"]
methods
|> List.map run_test
|> List.zip names
|> List.iter (fun i -> printfn “%s: %f ms” (fst i) (snd i))
press_enter ()
This takes a list of the three methods (isn’t it great to pass around code as data in functional languages?), run a test by timing it and taking the average of 10 executions, then print out the results.
Tail Recursion Test
mapl_tr1: 46.616836 ms
mapl_tr2: 42.788645 ms
mapl_tr3: 65.175500 ms
Press Enter to continue…
Wow, that’s really interesting. mapl_tr1 and mapl_tr2 are almost the same running time, but mapl_tr2 is slightly faster. So we can conclude that the closure adds a very small amount of overhead, which isn’t surprising. What caught me off guard is that mapl_tr3 takes more than 50% longer than mapl_tr2, owing to the constant creation of tuple objects under the hood. Looks like we have a winner, mapl_tr2!
For completeness, the implementations of time_iter and press_enter are given below:
#light
open System
open System.Diagnostics
let press_enter () =
printfn “Press Enter to continue…”
Console.ReadLine() |> ignore
let time f =
let sw = new Stopwatch()
sw.Start()
f ()
sw.Stop()
sw.Elapsed.TotalMilliseconds
let time_iter n f =
[0 .. n]
|> List.map (fun _ -> time f)
|> List.average
(time_iter can be optimized so it doesn’t create a 0..n list and uses sequence expressions…)
Conclusions
F# makes it really easy to write recursive functions that succinctly express our algorithms, but care must be taken to address tail recursion so that StackOverflowExceptions aren’t encountered in production code. Also, tail-recursive functions can be further optimized by ensuring that tuple objects aren’t created at each iteration, and by explicitly passing functions to inner loops and not relying on closures.
Whenever you write “let rec”, don’t give the Tail Recursion Police reason to take you downtown…
Hope that helps someone and eliminates some of the smoke/mirrors surrounding tail recursion!
tags.
