Tail recursion and exceptions in F#

.net, f#, tail-recursion

Solution

If you wrap the body of some (tail) recursive function in a `try` ... `with` block then the function is not tail recursive anymore, because the call frame cannot be discarded during the recursive call - it needs to stay in the stack with a registered exception handler.

For example, say you have something like `iter` function for `List`:

let rec iter f list =
  try
    match list with
    | [] -> ()
    | x::xs -> f x; iter f xs
  with e ->
    printfn "Failed: %s" e.Message

When you call `iter f [1;2;3]` then it will create 4 nested stack frames with exception handlers (and if you added `rethrow` into the `with` branch, then it would actually print the error message 4 times).

You cannot really add exception handlers without breaking tail-recursion. However, you do not usually need nested exception handlers. So the best solution is to rewrite the function so that it does not need to handle exceptions in every recursive call:

let iter f list =
  let rec loop list =
    match list with
    | [] -> ()
    | x::xs -> f x; loop xs
  try loop list
  with e -> printfn "Failed: %s" e.Message

This has a little different meaning - but it does not create nested exception handlers and `loop` can still be fully tail recursive.

Another option would be to add exception handling only over the body excluding the tail-recursive call. Realistically, the only thing that can throw an exception in this example is the call to `f`;

let rec iter f list =
  match list with
  | [] -> ()
  | x::xs -> 
    try
      f x
    with e ->
      printfn "Failed: %s" e.Message
    iter f xs

Problem

I've been googling for ages and still can't find the answer. From what I understand F# 3.0 runnning on .NET 4.5 will not use tail recursion for a recursive method if the invoker has wrapped the call in a try/catch and/or try/finally block. What is the situation if there is a try/catch or try/finally a few levels up the stack?

Original source