[MLton-user] Why is recursion slower than C?

[Matthew Fluet]

Henry Cejtin wrote:
> There is no way to turn the two non-tail calls of fib into loops.

That's a little strong.  There does exist an observationally equivalent 
tail-recursive implementation of fib (given that stack size is not an 
observable in an SML program and probably isn't considered an observable 
in a C program), so a compiler would be free to replace the non-tail 
implementation of fib with the tail-recursive implementation.

Now, I don't know how to automatically transform the one into the other, 
but that doesn't rule out the existence of the transform.

But, in any case, what Scott seems to be observing is that gcc is 
inlining the recursive calls to fib a couple of times.  That seems to 
special case fib(n) for n <= 8.  The naive implementation of non-tail 
fib ends up evaluating fib for small numbers over and over, so 
short-cutting at 8 probably wins big.