2

Software developers in functional programming languages have been told that tail-recursive calls are better than non-tail-recursive ones. A classic example in textbooks is the tail-recursive factorial function (written in F#)

let rec faci n r = 
  if n = 0 then r else faci (n-1) (r * n)

versus its non-tail-recursive counter-part.

let rec facr n = 
  if n = 0 then 1 else n * facr(n-1)

It is relatively clear that faci above does not need an extra stack frame when calling itself as facr would do. But I am looking for a more vivid example, preferable in F#, from which one can demonstrate why tail-recursive-functions are better than non-tail-recursive ones. Ideally, the improvement can be visualized, e.g., with a memory profiler, or by printing some debugging info. Any idea about such an example?

zell
  • 9,830
  • 10
  • 62
  • 115
  • 3
    Tail recursion depends on an accumulator. If the accumulator is just a single, computed value like in your example, tail recursion requires less memory. However, if it accumulates the result of each recursive step without information loss (in a list, for instance), you essentially trade call stack for heap. It might still be more memory efficient, though. –  Nov 05 '20 at 13:36
  • Good to know this. Thanks! – zell Nov 05 '20 at 13:39
  • tbh, this might not be as straightforward as you think. Some tailcalls will be optimized away into a loop by the compiler for example. Recursive functions are only better if they are tail recursive, otherwise they will eat you stack for lunch. – s952163 Nov 05 '20 at 14:31
  • 1
    I'd agree with the above, I would demonstrate it by demonstrating factorial using a loop (in C#), and then factorial recursively. – MrD at KookerellaLtd Nov 05 '20 at 15:19

0 Answers0