F# Tail Recursive Function Example

Question

I am new to F# and was reading about tail recursive functions and was hoping someone could give me two different implementations of a function foo - one that is tail recursive and one that isn't so that I can better understand the principle.

Solution 1

Start with a simple task, like mapping items from 'a to 'b in a list. We want to write a function which has the signature

val map: ('a -> 'b) -> 'a list -> 'b list

Where

map (fun x -> x * 2) [1;2;3;4;5] == [2;4;6;8;10]

Start with non-tail recursive version:

let rec map f = function
    | [] -> []
    | x::xs -> f x::map f xs

This isn't tail recursive because function still has work to do after making the recursive call. :: is syntactic sugar for List.Cons(f x, map f xs).

The function's non-recursive nature might be a little more obvious if I re-wrote the last line as | x::xs -> let temp = map f xs; f x::temp -- obviously its doing work after the recursive call.

Use an accumulator variable to make it tail recursive:

let map f l =
    let rec loop acc = function
        | [] -> List.rev acc
        | x::xs -> loop (f x::acc) xs
    loop [] l

Here's we're building up a new list in a variable acc. Since the list gets built up in reverse, we need to reverse the output list before giving it back to the user.

If you're in for a little mind warp, you can use continuation passing to write the code more succinctly:

let map f l =
    let rec loop cont = function
        | [] -> cont []
        | x::xs -> loop ( fun acc -> cont (f x::acc) ) xs
    loop id l

Since the call to loop and cont are the last functions called with no additional work, they're tail-recursive.

This works because the continuation cont is captured by a new continuation, which in turn is captured by another, resulting in a sort of tree-like data structure as follows:

(fun acc -> (f 1)::acc)
    ((fun acc -> (f 2)::acc)
        ((fun acc -> (f 3)::acc)
            ((fun acc -> (f 4)::acc)
                ((fun acc -> (f 5)::acc)
                    (id [])))))

which builds up a list in-order without requiring you to reverse it.

---

For what its worth, start writing functions in non-tail recursive way, they're easier to read and work with.

If you have a big list to go through, use an accumulator variable.

If you can't find a way to use an accumulator in a convenient way and you don't have any other options at your disposal, use continuations. I personally consider non-trivial, heavy use of continuations hard to read.

Solution 2

An attempt at a shorter explanation than in the other examples:

let rec foo n =
    match n with
    | 0 -> 0
    | _ -> 2 + foo (n-1)

let rec bar acc n =
    match n with
    | 0 -> acc
    | _ -> bar (acc+2) (n-1)

Here, foo is not tail-recursive, because foo has to call foo recursively in order to evaluate 2+foo(n-1) and return it.

However, bar ís tail-recursive, because bar doesn't have to use the return value of the recursive call in order to return a value. It can just let the recursively called bar return its value immediately (without returning all the way up though the calling stack). The compiler sees this and optimized this by rewriting the recursion into a loop.

Changing the last line in bar into something like | _ -> 2 + (bar (acc+2) (n-1)) would again destroy the function being tail-recursive, since 2 + leads to an action that needs to be done after the recursive call is finished.

Solution 3

Here is a more obvious example, compare it to what you would normally do for a factorial.

let factorial n =
    let rec fact n acc =
        match n with
        | 0 -> acc
        | _ -> fact (n-1) (acc*n)
    fact n 1

This one is a bit complex, but the idea is that you have an accumulator that keeps a running tally, rather than modifying the return value.

Additionally, this style of wrapping is usually a good idea, that way your caller doesn't need to worry about seeding the accumulator (note that fact is local to the function)

Solution 4

I'm learning F# too. The following are non-tail recursive and tail recursive function to calculate the fibonacci numbers.

Non-tail recursive version

let rec fib = function
    | n when n < 2 -> 1
    | n -> fib(n-1) + fib(n-2);;

Tail recursive version

let fib n =
    let rec tfib n1 n2 = function
    | 0 -> n1
    | n -> tfib n2 (n2 + n1) (n - 1)
    tfib 0 1 n;;  

Note: since the fibanacci number could grow really fast you could replace last line tfib 0 1 n to
tfib 0I 1I n to take advantage of Numerics.BigInteger Structure in F#

Solution 5

Also, when testing, don't forget that indirect tail recursion (tailcall) is turned off by default when compiling in Debug mode. This can cause tailcall recursion to overflow the stack in Debug mode but not in Release mode.

View more solutions

Comments

[Onorio Catenacci]

In the code immediately below "Continuation Passing" you use the id function without defining it (the line "loop id l". Am I correct in assuming it'd be (fun x->x)?

[Juliet]

@Onorio Catenacci: id is one of the built-in functions which come with F#, and it has the definition let id x = x.

[Onorio Catenacci]

@Juliet--I should have known better than to think you'd miss something so obvious :-) I just thought you'd neglected to copy all of the demonstration code.

[Mark Pearl]

Thanks Batibix for the succint example

[knocte]

sorry if I'm being dense but I'm trying to wrap my head around your first accumulator example and I don't understand one bit: you call the recursive function via loop (f x::acc) xs however the recursive function only receives one argument, so this wouldn't compile? maybe there's something I don't understand about the function keyword which I actually haven't ever used yet (can this use the fun keyword instead?)

[Gabriel]

@knocte the function keyword adds an argument to the function. See markhneedham.com/blog/2010/02/07/f-function-keyword

[costa]

I tried your solution with the continuation and it doesn't work: let accumulate (func: 'a -> 'b) (input: 'a list): 'b list = let rec loop cont = function | [] -> cont [] | x::xs -> loop ( fun acc -> cont (func x::acc) ) xs loop id input with [<Fact()>] let ``Accumulate large data set without stack overflow`` () = accumulate id [1..100000] |> should equal [1..100000] . It doesn't do a tail recursion.

[costa]

I use donet 3.1.101 with Jetbrains Rider on macos. I don't know the exact version of f#.

[costa]

Just to be clear, when I said "it doesn't work" I meant it doesn't do a tail recursion. The test I included in my comment fails.

[Aisah Hamzah]

@costa: I just copied your code snippet and tried it. When compiled as DEBUG, it overflows the stack, when compiled as RELEASE, it doesn't. This is expected, TCO is only on when optimizations are on. This difference can also be observed in FSI (F# Interactive, you can switch TCO off with --tailcalls-)