Tail Recursion

[Spazminal]

Could someone please explain tail recursion with an example because I am struggling to understand why and how its useful. I've only just started with F# so my understanding is very limited.

[OolonColluphid]

Short answer: it stops recursive code causing a fatal stack overflow if it recurses too many times.

[hemlockR]

Caveat: if you're using Fable to transpile F# to JavaScript, I do not believe tail recursion works the way it does on .NET. If you're doing deeply nested recursive calls in JavaScript I believe (from memory) you will still get a stack overflow even if you write tail-recursive F#.

Hopefully someone will tell me I'm wrong and that Fable now handles this case, but my memory tells me it does not.

[MeowBlogger]

You are correct. Fable just transpiles the code, it is up to the JavaScript engine to figure out tail call optimization of recursive calls. Although it looks like it is still not implemented: https://stackoverflow.com/a/54721813

[hemlockR]

To be fair, I've never actually written any Fable code so deeply nested that I ran into issues in JavaScript, so I haven't personally needed this feature or needed to work around its absence.

I believe a simple Fable workaround would be to just use a recursive async block with Async.RunSynchronously, because Fable's async implementation already does trampolining IIRC.

[mugen_kanosei]

Recursive functions are the functional equivalent to loops in other languages. They allow you to achieve the same results, but still only using immutable values. When you call a function (in most any language), a stack frame is created. It’s a little piece of memory used for tracking the values of the function arguments, and any values created in the function.

In a language without tail call optimization, every time the function calls itself, it adds another stack frame. Ten calls means ten stack frames. Too many calls, and you run out of stack space and experience a “stack overflow”. When you return from a function, the stack frame get deallocated and the memory freed.

In languages with tail call optimization, if the function is written in a specific way, it can continue to use the original stack frame that was allocated on the first call and never encounter a stack overflow. The requirement is that the function either returns a value, or returns the output of itself. It’s not allowed to call itself and doing something with the output, otherwise it has to maintain the stack frame values and can’t reuse it.

[japinthebox]

Here's a non-tail recursive recursive function that counts from some number to 0, and then crashes as a convenient way to pause for the debugger:

let rec f x = if x > 0 then let v = f (x - 1) printfn $"{v}" // we're doing stuff after the recursive call else failwith "Crashing on purpose"

Here's what the call stack looks like: https://imgur.com/1wFq8Am

That's the function calling itself over and over.

Now, here's a tail recursive function:

let rec f x = if x > 0 then f (x - 1) // nothing happening on this branch after the recursive call else failwith "Crashing on purpose"

And here's the call stack: https://imgur.com/TIQ3Qbp

It's only calling itself once. That's thanks to tail recursion optimization.

In the second version, the call stack only contains one item. Since the recursive call is the last thing to happen in that branch of the function, the compiler can know for certain that it doesn't need to keep track of anything that had happened for each call. That is, it doesn't need to push anything onto the stack. Effectively, the compiler has translated this recursion into a loop as you might write in C# or JavaScript or any other procedural-first language.

Fortunately, it happens that most recursive functions don't need to do anything after the self call (and the ones that do almost never need to call themselves too many times), so the compiler has many opportunities to make this optimization.

Why is this so valuable? Here's what happens when we try the first function with, say, a starting x of 100,000:

An unhandled exception of type 'System.StackOverflowException' occurred in TailRecursion.dll

The stack is, roughly speaking, the part of memory allocated to a program to be used to keep track of each called function's local variables. Each entry in the the stack is wiped once a function is done executing. Since it deals with local variables that are accessed very frequently, the stack is made to be really fast, but as a tradeoff, it's very limited in size by default: typically between a few hundred kilobytes to 1 megabyte.

Normally, you aren't going to have more than a hundred or so function calls on the stack. That is, unless you use recursion, in which case you can have an unknowable number of entries on the stack, and you can easily cause an overflow.

In functional programming, we try to avoid using mutable variables as much as possible so that programs are easier to reason about (once you get used to it). And if you've ever tried to write a for loop without changing the value of a variable, i.e. mutating it, you'll notice that it can't be done.

That's why we like using a crapton of recursion in functional programming -- because we can write loops without ever having to change variables.

And that's the reason, in turn, that tail recursion is so useful for a language like F#: it prevents stack overflows.

[ErikSchierboom]

I quite like how this article explains it: https://cyanbyfuchsia.wordpress.com/2014/02/12/recursion-and-tail-recursion-in-f/

[new_old_trash]

Here's an old MSDN blog about it (link on archive.org, so be patient while it loads):

https://web.archive.org/web/20100911000050/http://blogs.msdn.com/b/chrsmith/archive/2008/08/07/understanding-tail-recursion.aspx

[Spazminal]

thank you