While or Tail Recursion in F#, what to use when?

Question

Ok, only just in F# and this is how I understand it now :

• Some problems are recursive in nature (building or reading out a treestructure to name just one) and then you use recursion. In these cases you preferably use tail-recursion to give the stack a break

• Some languagues are pure functional, so you have to use recursion in stead of while-loops, even if the problem is not recursive in nature

So my question : since F# also support the imperative paradigm, would you use tail recursion in F# for problems that aren't naturally recursive ones? Especially since I have read the compiler recongnizes tail recursion and just transforms it in a while loop anyway?

If so : why ?

Answer 1

The best answer is 'neither'. :)

There's some ugliness associated with both while loops and tail recursion.

While loops require mutability and effects, and though I have nothing against using these in moderation, especially when encapsulated in the context of a local function, you do sometimes feel like you're cluttering/uglifying your program when you start introducing effects merely to loop.

Tail recursion often has the disadvantage of requiring an extra accumulator parameter or continuation-passing style. This clutters the program with extra boilerplate to massage the startup conditions of the function.

The best answer is to use neither while loops nor recursion. Higher-order functions and lambdas are your saviors here, especially maps and folds. Why fool around with messy control structures for looping when you can encapsulate those in reusable libraries and then just state the essence of your computation simply and declaratively?

If you get in the habit of often calling map/fold rather than using loops/recursion, as well as providing a fold function along with any new tree-structured data type you introduce, you'll go far. :)

For those interested in learning more about folds in F#, why not check out my first three blog posts in a series on the topic?

Answer 2

In order of preference and general programming style, I will write code as follows:

Map/fold if its available

let x = [1 .. 10] |> List.map ((*) 2)

Its just convenient and easy to use.

Non-tail recursive function

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

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

> [1 .. 10] |> map ((*) 2);;
val it : int list = [2; 4; 6; 8; 10; 12; 14; 16; 18; 20]

Most algorithms are easiest to read and express without tail-recursion. This works particularly well when you don't need to recurse too deeply, making it suitable for many sorting algorithms and most operations on balanced data structures.

Remember, log₂(1,000,000,000,000,000) ~= 50, so log(n) operation without tail-recursion isn't scary at all.

Tail-recursive with accumulator

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

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

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

> [1 .. 10] |> map ((*) 2);;
val it : int list = [2; 4; 6; 8; 10; 12; 14; 16; 18; 20]

It works, but the code is clumsy and elegance of the algorithm is slightly obscured. The example above isn't too bad to read, but once you get into tree-like data structures, it really starts to become a nightmare.

Tail-recursive with continuation passing

> let rec map cont f = function
    | [] -> cont []
    | x::xs -> map (fun l -> cont <| f x::l) f xs;;

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

> [1 .. 10] |> map id ((*) 2);;
val it : int list = [2; 4; 6; 8; 10; 12; 14; 16; 18; 20]

Whenever I see code like this, I say to myself "now that's a neat trick!". At the cost of readability, it maintains the shape of the non-recursive function, and found it really interesting for tail-recursive inserts into binary trees.

Its probably my monad-phobia speaking here, or maybe my inherent lack of familiarity with Lisp's call/cc, but I think those occasions when CSP actually simplifies algorithms are few and far between. Counter-examples are welcome in the comments.

While loops / for loops

It occurs to me that, aside from sequence comprehensions, I've never used while or for loops in my F# code. In any case...

> let map f l =
    let l' = ref l
    let acc = ref []
    while not <| List.isEmpty !l' do
        acc := (!l' |> List.hd |> f)::!acc
        l' := !l' |> List.tl
    !acc |> List.rev;;

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

> [1 .. 10] |> map ((*) 2);;
val it : int list = [2; 4; 6; 8; 10; 12; 14; 16; 18; 20]

Its practically a parody of imperative programming. You might be able to maintain a little sanity by declaring let mutable l' = l instead, but any non-trivial function will require the use of ref.

Answer 3

Many problems have a recursive nature, but having thought imperatively for a long time often prevents us from seeing this.

In general I would use a functional technique wherever possible in a functional language - Loops are never functional since they exclusively rely on side-effects. So when dealing with imperative code or algorithms, using loops is adequate, but in functional context, they're aren't considered very nice.

Functional technique doesn't only mean recursion but also using appropriate higher-order functions.

So when summing a list, neither a for-loop nor a recursive function but a fold is the solution for having comprehensible code without reinventing the wheel.

Answer 4

Honestly, any problem that you can solve with a loop is already a naturally recursive one, as you can translate both into (usually conditional) jumps in the end.

I believe you should stick with tail calls in almost all cases where you must write an explicit loop. It is just more versatile:

• A while loop restricts you to one loop body, while a tail call can allow you to switch between many different states while the "loop" is running.
• A while loop restricts you to one condition to check for termination, with the tail recursion you can have an arbitrarily complicated match expression waiting to shunt the control flow off somewhere else.
• Your tail calls all return useful values and can produce useful type errors. A while loop does not return anything and relies on side effects to do its work.
• While loops are not first class while functions with tail calls (or while loops in them) are. Recursive bindings in local scope can be inspected for their type.
• A tail recursive function can easily be broken apart into parts that use tail calls to call each other in the needed sequence. This may make things easier to read, and will help if you find you want to start in the middle of a loop. This is not true of a while loop.

All in all while loops in F# are only worthwhile if you really are going to be working with mutable state, inside a function body, doing the same thing repeatedly until a certain condition is met. If the loop is generally useful or very complicated, you may want to factor it out into some other top level binding. If the data types are themselves immutable (a lot of .NET value types are), you may gain very little from using mutable references to them anyway.

I'd say that you should only resort to while loops for niche cases where a while loop is perfect for the job, and is relatively short. In many imperative programming languages, while loops are often twisted into unnatural roles like driving stuff repeatedly over a case statement. Avoid those kinds of things, and see if you can use tail calls or, even better, a higher order function, to achieve the same ends.

Answer 5

for problems that aren't naturally recursive ones .. just transforms it in a while loop anyway

You answered this yourself. Use recursion for recursive problems and loop for things that aren't functional in nature. Just always think: Which feels more natural, which is more readable.