I recently wanted to calculate some binomial coefficients in Erlang, and so needed an implementation of the factorial function. No problem. The factorial function is the canonical illustration of how to define a recursive function in Erlang. It goes something like this:

fac(0) -> 1;
fac(N) -> N * fac(N-1).

I have to confess that definition has always bothered me because it is not tail recursive. And it only takes one more line to write a tail recursive version, just the way God intended:

fac1(N) -> fac1(N,1).
fac1(0,R) -> R;
fac1(N,R) -> fac1(N-1, N*R).

The advantage of fac1 over fac is that fac1 operates in constant space, while fac requires space linear in N. For large N one has to wonder whether fac's chain of deferred multiplications will overflow the stack. But is this really a problem? Just how large a value of N is required to overflow the stack? I decided to try to find out.

I ran some test cases: fac(1000), fac(10000), fac(50000). No stack overflow yet, but I could see it might get old waiting for the enormous answers to be computed and displayed. I decided to switch gears. To avoid suffering through monster integers, I modified the test. Rather than testing with fac, I settled on using the structurally similar function sum:

sum(0) -> 0;
sum(N) -> N + sum(N-1).

Just for grins, I decided to try the same thing in a couple of other languages. Here is sum in Clojure:

(defn sum [n]
   (if (= n 0)
       (+ n (sum (- n 1)))))

And here it is in Haskell, where I changed the spelling to summ to avoid a name collision with a Prelude function called sum:

summ 0 = 0
summ n = n + summ (n-1)

I was surprised by the results of my tests.

Just to build up the suspense, I'll pause to describe the test machine. It's a Dell T105, quad-core AMD Opteron, 8GB of ram, running Ubuntu Intrepid. Clojure is revision 1173, running on top of Java 1.6.0_10. Haskell is ghci 6.10.1, and Erlang is R12B-5.

On to the results. First up is Clojure:

user=> (sum 10000)
user=> (sum 20000)
user=> (sum 30000)
user=> (sum 40000)
java.lang.StackOverflowError (NO_SOURCE_FILE:0)

The stack overflow is just the sort of thing that makes me prefer fac1 over fac. Let's see what happens in Haskell.

*Main> summ 10000
*Main> summ 30000
*Main> summ 40000
*Main> summ 50000
*Main> summ 75000
*Main> summ 100000
*Main> summ 150000
*Main> summ 175000
*** Exception: stack overflow

Haskell, or rather ghci, did roughly four times better. It's probably worth pointing out that this is not really a comparison of the languages so much as a comparison of how the language implementations handle one very specific detail.

Here I need to point out that I am quite aware than both the Clojure and Haskell examples could be (and normally ought to be) modified so as not to blow the stack. My purpose here is to see what it takes to blow the stack. I want to blow the stack.

Time to see how the Erlang virtual machine fares. I stuck the sum function in a module called fac. No matter.

Eshell V5.6.5  (abort with ^G)
1> fac:sum(1000).
2> fac:sum(10000).
3> fac:sum(50000).
4> fac:sum(100000).
5> fac:sum(200000).
6> fac:sum(500000).
7> fac:sum(1000000).
8> fac:sum(5000000).
9> fac:sum(10000000).
10> fac:sum(50000000).
11> fac:sum(100000000).
12> fac:sum(200000000).

At that point I went for broke, and tried to compute sum(1000000000). Maybe it would have worked eventually, but I killed it. My machine had gone nearly non-responsive, and I could hear my hard drive thrashing. Those disk sounds incline me to guess that when Erlang ran out of stack space, it moved the computation into virtual memory and soldiered on. Whatever the actual means, N=200,000,000 is pretty impressive. That's three orders of magnitude better than ghci or the jvm. Kudos to the authors of the Erlang virtual machine.

One final thought. In spite of what I saw here, I'll still go with the tail recursive version of the factorial function. It better satisfies my sense of aesthetics. But it's nice to know I don't have to.