Tail recursion and exceptions in F#

问题:

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?

回答1:

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