F # Tail recursion. Underwater rake. Part 1

Winnie the Pooh: Oh, what happened to your tail?
Ia: And what could have happened to him?
Winnie the Pooh: He is not.
Ia: You were not mistaken?
Winnie the Pooh: Tail or there is or not at all! There can not be wrong.
Ia: And what then is there?
Winnie the Pooh: Nothing!

In our project, in one of the server components, after the next refactoring, memory began to flow. It would seem. NET, F #, managed code, garbage collection, all things, but the memory flowed somewhere. At the cost of sleepless nights and damaged nerves, the source of the leak was found. It turned out that the problem was caused by a piece of code that was copied almost from one to one from the F # tutorial.

The whole thing was in tail recursion, or rather, as it turned out in its absence in unexpected places.

Tail recursion

Recursion, this is probably one of the most important tools in the arsenal of functional programming. And since recursive calls use a stack, which, as is known, is not unlimited, it may seem that the use of recursion is limited and the depth of recursion is finite.
')
However, everything is not so gloomy, almost all compilers of functional languages ​​have such useful stuff as tail recursion optimization, with which you can use recursion without using the stack, which in turn removes the restriction on recursion nesting.

Tail recursion is a special case of recursion when the recursive call can be replaced by iteration. On the one hand, it is up to the programmer’s conscience to write logic in the “tail” style, on the other hand, the compiler must also “find” tail recursion and unleash recursion in iteration.

Usually the beginner “functionalist” quickly fills the eye and hand and uses tail recursion everywhere. But there are several special cases where the function, which, it would seem, is the iron “tail” is not really such. These special cases can lead to very unpleasant consequences, and can kill a lot of time and nerves.

Let's consider the first such case and formulate a rule by which you can avoid “trouble”.

Let's start with a simple function that adds up all the numbers from one to N:

let rec sum i = if i <= 0L then 0L else i + sum (i - 1L) > sum 10L;; val it : int64 = 55L 

All is well, except for one moment. If we try to calculate the amount for at least 100,000, we get a StackOverflowException in the forehead. Those. we simply did not have enough stack for calculations:

 > sum 100000L;; Process is terminated due to StackOverflowException. 

The answer to this problem, the use of the battery, as an argument of the recursive function:

 let sumTailRec i = let rec loop acc i = if i <= 0L then acc else loop (acc + i) (i - 1L) loop 0L i 

We rewrote our function in such a way that it doesn’t need a stack, instead of going back to summing up, we forward the accumulator as an argument.

To illustrate the order of calculation (for argument 5), you can. Without tail recursion:

 sum: 5 + (4 + (3 + (2 + (1 + (0))))) –       ,  ,      .         . 

Tail recursion:

 sumTailRec: (((0 + 5) + 4) + 3) + 2) + 1) – ,      ,       ,       . 

A new function can already digest an arbitrarily large number (as long as int64 is enough).

 > sumTailRec 10000000L;; val it : int64 = 50000005000000L 

Now, let's write a little more generalized function, which summarizes not the numbers themselves, but the result of some given function of the current number.

 let sumFTailRec fi = let rec loop acc i = if i <= 0L then acc else loop (acc + fi) (i - 1L) loop 0L i 

In the new version, we have another parameter - a function, the result of whose calculation needs to be summed up. Here is an option that sums up the numbers themselves:

 > sumFTailRec (fun i -> i) 10000000L val it : int64 = 50000005000000L 

And here, which summarizes the squares:

 > sumFTailRec (fun i -> i*i) 10000000L val it : int64 = 1291990006563070912L 

So far so good. But there is a small nuance, the function that is passed, can “throw” an exception. Here is an example:

 > let someProblemFun i = i/((i+1L) % 1000L) > sumFTailRec someProblemFun 10000000L System.DivideByZeroException: Attempted to divide by zero. Stopped due to error 

Problem

When the value i = 999, we have a division by zero. Suppose that we want an exception, not to crash the calculation, but simply to ignore the problem element. We will need exception handling. A logical and expected solution suggests itself:

 let sumFTailRecWithTry fi = let rec loop acc i = if i <= 0L then acc else try loop (acc + fi) (i - 1L) with exc -> printfn "exn raised:%s" exc.Message loop acc (i - 1L) loop 0L i 

So try:

 > sumFTailRecWithTry someProblemFun 10000L exn raised:Attempted to divide by zero. ... exn raised:Attempted to divide by zero. val it : int64 = 351405L 

The result was received, exceptions were caught, everything seems to be fine. Now we try to feed a more serious number:

 > sumFTailRecWithTry someProblemFun 10000000L exn raised:Attempted to divide by zero. ... exn raised:Attempted to divide by zero. Process is terminated due to StackOverflowException. 

Oops ... What's the matter? At first glance, we have a function with tail recursion, why did the stack suddenly end?

As you might guess, the problem is in the try ... with design. The fact is that if a recursive call is executed in a try block, then the tail recursion falls off the tail, and it becomes an ordinary recursion. Why? Because in any of the subsequent recursive calls loop, theoretically, an exception can fall out, but since if we need to process it, then we need to memorize in the stack the place where we need to return when the exception is “dropped”.

Decision

Which of such unpleasant situation is the way out? Very simple, you do not need to wrap the recursive call with a try ... with block , because we expect an exception only when you call the "external" function f, then you only need to wrap this call:

 let sumFReallyTailRecWithTry fi = let rec loop acc i = if i <= 0L then acc else let fRes = try fi with exc -> //printfn "exn raised:%s" exc.Message 0L loop (acc + fRes) (i - 1L) loop 0L i 

We try:

 > sumFReallyTailRecWithTry someProblemFun 10000000L val it : int64 = 374200932236L 

Voila! Stack this time was enough, or rather he was left untouched.

So the rule is: never put a tail call on a try ... with block.

In the second series there will be shocking revelations concerning tail recursion for async {...} and MailboxProcessor.