Recursion is when something is defined by referencing it’s self. Google has an amazing explanation for recursion, just Google search “recursion” (no need to click on any links even! it’s right there in Google).

Tail call recursion is when something references it’s self at the end. It’s hard to explain so I’ll just explain by example. Lack of proper tail call recursion leads to major slow downs as well. I had heard that but never put it to the test so I wrote a couple of programs to show how detrimental improper tail call recursion can be.

The simplest example is the factorial function, it has a nice recursive definition. (Note to self, add MathML magic to this Tumblr, until then take images from Wikipedia).

I wanted to see how bad implementing this naively would be so I wrote two programs in F# to find the factorial of 1000. (F# has a BigInteger class built in so that’s awesome).

#light
let rec badFact n =
  if n <= 1I then 1I
  else n * (badFact n-1I);;
(* bad because no tail call optimize *)
let bigI = 1000I;;printfn "%A! has %A digits" bigI (string (badFact bigI)).Length;;

And I wrote another version that can be tail call optimized.

#light
let rec goodFact n prod =
  if n <= 1I then prod
  else goodFact (n-1I) (prod*n);;
let bigI = 1000I;;
printfn "%A! has %A digits" bigI (string (goodFact bigI 1I)).Length;; 

The difference is subtle but the performance difference is significant. As it turns out, the naive implementation stackoverflows. The good one finishes in less than a second.

I thought this may be because it’s running on .NET which isn’t exactly designed for lots of functional things (it’s still good though, as the proper implementation ran very fast). I decided to write these in Haskell to see Haskell with it’s trampoline-like calling system be able to handle the bad version.

The Haskell version successfully ran the bad version but so quite slowly, as expected. On my Macbook it ran in 0.413 seconds. That may seem fast but the better one only required 0.007 seconds. This may be a reason why people sometimes think Haskell’s performance is unpredictable, improper recursive calls that, if not for Haskell’s beastly function calling mechanism, would cause stack overflows.

Why?

I should probably explain why the “bad version” is bad and why the good version runs circles around it. This has to do with how functions are called. Down at the assembler level there is a “stack” used for function calling. When in one function and calling another, the function “pushes” it’s location onto the stack so that the function that it calls knows where to (jmp) return to. When the program does “n * (badFact (n-1))” it has to call badFact and then return and finally multiply with “n”. In the goodFact it returns the result of goodFact directly, no multiplying by “n” at the end. This allows the compiler to optimize and turn this into a loop, i.e. no need for the calling stack. This is why the good version doesn’t stackoverflow and the bad one does. (Also Haskell’s calling system might not overflow as fast but it certainly adds overhead to the calculation, making the bad version very slow).