Followed 3 functions written in Haskell language, which are fac1, fac2 and fac3. They are all for calculating factorial. The performance of them are different.
'fac1 10000' takes (0.97 secs, 104695704 bytes)
'fac2 10000' takes (1.04 secs, 115210800 bytes)
'fac3 10000' takes (0.52 secs, 113564104 bytes)
The performance differences are because of many facts of Haskell language, including Tail Recutsion and Lazy Evaluation.
'fac1' is not tail-recursive, while 'fac2' and 'fac3' are tail-recursive. If a function's last expression is merely calling the function itself, we call it tail-recursive. In this case, reserving stack spaces for function calls is unnecessary. Haskell compiler (Most Functional Programming Compiler) can optimize tail-recursive function calls to loop.
But why fac2 spends more time and memory, since it has tail-recursive optimization? This is because Haskell is a lazy evaluation language. It computes an expression whenever necessary, otherwise, it store pending unresolved expressions as thunks.
Sometimes strict evaluation is preferred. This can be obtained through `seq` or $!. f $! x = x `seq` f x. They both first evaluate x and then apply f on it. We can see that fac3 spends less time than fac2 and fac1.