11

I'm learning F# (new to functional programming in general though used functional aspects of C# for years but let's face it, that's pretty different) and one of the things that I've read is that the F# compiler identifies tail recursion and compiles it into a while loop (see http://thevalerios.net/matt/2009/01/recursion-in-f-and-the-tail-recursion-police/).

What I don't understand is why you would write a recursive function instead of a while loop if that's what it's going to turn into anyway. Especially considering that you need to do some extra work to make your function recursive.

I have a feeling someone might say that the while loop is not particularly functional and you want to act all functional and whatnot so you use recursion but then why is it sufficient for the compiler to turn it into a while loop?

Can someone explain this to me?

hackerhasid
  • 11,699
  • 10
  • 42
  • 60
  • possible duplicate of [While or Tail Recursion in F#, what to use when?](http://stackoverflow.com/questions/1797241/while-or-tail-recursion-in-f-what-to-use-when) – nawfal Dec 14 '13 at 07:43

4 Answers4

18

You could use the same argument for any transformation that the compiler performs. For instance, when you're using C#, do you ever use lambda expressions or anonymous delegates? If the compiler is just going to turn those into classes and (non-anonymous) delegates, then why not just use those constructions yourself? Likewise, do you ever use iterator blocks? If the compiler is just going to turn those into state machines which explicitly implement IEnumerable<T>, then why not just write that code yourself? Or if the C# compiler is just going to emit IL anyway, why bother writing C# instead of IL in the first place? And so on.

One obvious answer to all of these questions is that we want to write code which allows us to express ourselves clearly. Likewise, there are many algorithms which are naturally recursive, and so writing recursive functions will often lead to a clear expression of those algorithms. In particular, it is arguably easier to reason about the termination of a recursive algorithm than a while loop in many cases (e.g. is there a clear base case, and does each recursive call make the problem "smaller"?).

However, since we're writing code and not mathematics papers, it's also nice to have software which meets certain real-world performance criteria (such as the ability to handle large inputs without overflowing the stack). Therefore, the fact that tail recursion is converted into the equivalent of while loops is critical for being able to use recursive formulations of algorithms.

kvb
  • 54,864
  • 2
  • 91
  • 133
  • then maybe it's because i still feel more comfortable with a while loop that i ask the question... – hackerhasid May 06 '11 at 19:26
  • @statichippo - Yes, your question is quite reasonable if you find while loops easier to reason about than recursion. However, with more exposure to the functional style, you may start to see cases where recursion fits better. – kvb May 06 '11 at 19:35
  • 1
    @statichippo - Of course you will be more comfortable with writing what you know but consider this. *Before I started to code I was **very** comfortable with not writing code.* – ChaosPandion May 06 '11 at 20:11
  • 2
    +1 for the point about reasoning. Although I would claim it makes it easier to reason about (partial) correctness as well termination. This point really needs to be emphasised more often - programmers prove properties about their programs all the time (usually informally in their head). Reasoning about functional programs (using induction) is very natural. Reasoning about imperative programs isn't. – petebu May 07 '11 at 13:42
7

A recursive function is often the most natural way to work with certain data structures (such as trees and F# lists). If the compiler wants to transform my natural, intuitive code into an awkward while loop for performance reasons that's fine, but why would I want to write that myself?

Also, Brian's answer to a related question is relevant here. Higher-order functions can often replace both loops and recursive functions in your code.

Community
  • 1
  • 1
Joel Mueller
  • 28,324
  • 9
  • 63
  • 88
  • 2
    The only snag is that the "most natural way to work with certain data structures" is usually not tail-recursive. So we are left to transform it into something less readable by ourselves. Still better than while loops though. :-) – petebu May 06 '11 at 19:08
  • @petebu - That's why I brought up Brian's post. Neither loops nor recursive functions are without warts, which is why `map` and `fold` can be so nice to have. – Joel Mueller May 06 '11 at 19:17
5

The fact that F# performs tail optimization is just an implementation detail that allows you to use tail recursion with the same efficiency (and no fear of a stack overflow) as a while loop. But it is just that - an implementation detail - on the surface your algorithm is still recursive and is structured that way, which for many algorithms is the most logical, functional way to represent it.

The same applies to some of the list handling internals as well in F# - internally mutation is used for a more efficient implementation of list manipulation, but this fact is hidden from the programmer.

What it comes down to is how the language allows you to describe and implement your algorithm, not what mechanics are used under the hood to make it happen.

BrokenGlass
  • 158,293
  • 28
  • 286
  • 335
  • 3
    I don't think "tail optimization is just an implementation detail". Is garbage collection just an implementation detail? If you turn either off it won't just make some programs run slower, they will crash with a stack-overflow or out-of-memory exception. Knowing that certain programs will consume only a constant amount of stack space (cf. heap) is incredibly useful. I wish the F# spec made some guarantees about it. Many programs assume the presence of tail-call elimination (even more assume garbage collection) and will break otherwise. – petebu May 06 '11 at 19:05
  • 1
    @petebu: Agreed - what I meant to say was *how* F# performs tail optimization (i.e. by turning it into a while loop) is not important, the fact *that it does* is certainly part of the language spec and hence required by some programs. – BrokenGlass May 06 '11 at 19:09
  • Also it's worth noting that the F# compiler doesn't **always** turn tail-recursive functions into while loops. Depending on the circumstance, it may do that or it might emit the `.tail` IL instruction instead. – Joel Mueller May 06 '11 at 19:14
  • Do you have a reference for where the spec guarantees anything about tail calls? I tried to find it (by searching for "tail") but couldn't. – petebu May 06 '11 at 19:15
  • @petebu: obviously that statement was wrong, this optimization is not part of the language but a property of the F# compiler, my bad - should have read your first comment more closely ;-) – BrokenGlass May 06 '11 at 19:21
2

A while loop is imperative by its nature. Most of the time, when using while loops, you will find yourself writing code like this:

let mutable x = ...
...
while someCond do
    ...
    x <- ...

This pattern is common in imperative languages like C, C++ or C#, but not so common in functional languages.

As the other posters have said some data structures, more exactly recursive data structures, lend themselves to recursive processing. Since the most common data structure in functional languages is by far the singly linked list, solving problems by using lists and recursive functions is a common practice.

Another argument in favor of recursive solutions is the tight relation between recursion and induction. Using a recursive solution allows the programmer to think about the problem inductively, which arguably helps in solving it.

Again, as other posters said, the fact that the compiler optimizes tail-recursive functions (obviously, not all functions can benefit from tail-call optimization) is an implementation detail which lets your recursive algorithm run in constant space.

Alex
  • 2,040
  • 2
  • 19
  • 29