3

If I got right, smart compilers detect tail-recursive functions and convert it to an iterative function.

So besides the benefits of writing in a functional style (immutability, function-independence etc.) what are other benefits with tail-recursion and should I considor writing iterative solutions when possible (in C#)?

Zaid Ajaj
  • 680
  • 8
  • 16
  • 1
    For F# see: [Can an F# fuction be considered tail recursive it uses the TailCall .net opcode](http://stackoverflow.com/a/9694718/1243762) and [Tail calls in F#](http://blogs.msdn.com/b/fsharpteam/archive/2011/07/08/tail-calls-in-fsharp.aspx) – Guy Coder Dec 01 '13 at 14:51
  • 1
    See: [Why doesn't .NET/C# optimize for tail-call recursion?](http://stackoverflow.com/q/491376/1243762) – Guy Coder Dec 01 '13 at 14:57
  • @GuyCoder The F# blog post was very helpful, thanks man – Zaid Ajaj Dec 01 '13 at 15:12

1 Answers1

3

From my experience, I'll go with readability over "performance". We came a long way from the days in which we had to consider shifting a number right or left instead of multiply or divide by 2.

Having said that, back at Uni we had to solve the Eight queen puzzle recursively. Once done, I figured I could run it for any board size really. I think the recursive method crashed on a 11x11 board if my memory serves me right (pun intended). Since I had an iterative solution as well (they are quite equivalent really), I decided to run that one, and could easily solve much bigger boards with no problem.

You could benchmark til your happy, and argue until your fingers bleed on the keyboard, but in the end it usually doesn't matter. If your solution works, use it. If you think you might run into memory issues because the recursion keep allocation new memory on the stack, go with iterative. In either case, having readable code will serve you better in any case :)

Noctis
  • 11,507
  • 3
  • 43
  • 82
  • I agree with you, tail-recursive functions are alot more readable, however til now, I haven't encountered a perf. problem using recursion. I think then I will stick to it for a while . . . ! – Zaid Ajaj Dec 01 '13 at 14:39
  • 1
    :). Give the good old queen problem a go ... probably with today's hardware you'll be able to use a bigger board, but eventually you'll hit a limit. Then you can see the iteration benefits. But for most cases, same same, but different. – Noctis Dec 01 '13 at 14:40
  • 1
    Beginner programmers usually need some getting used to recursion before they are readable. The same goes for tail recursion. When you've seen and written some I think it's no different in readability. – Sylwester Dec 01 '13 at 15:29
  • Beginner programmers usually need some getting used to iteration too! When I went to university the first programming course was actually taught in Haskell, so naturally recursion came up before we were taught about for loops. I don't think this made learning to program fundamentally any harder (or easier for that matter), it just meant we became familiar with different concepts earlier. – Ben Dec 02 '13 at 04:57
  • 2
    :) We went java , c++, c, lisp and assembler. Drove me mad after doing high level OO to talk to the CPU pushing values to the registers ... I guess if it would have been the other way around, it would have driven me mad to lose the control you get from lower levels :) – Noctis Dec 02 '13 at 05:09