As an exercise of learning scala and functional programming, I implemented the following non tail-recursive def that calculates the pascal's number at any location. The program itself serves as the definition of pascal's triangle. It looks pictorially as follows
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
...
def pascal(c: Int, r: Int): Int =
if (c == 0 || c == r) 1 else pascal(c - 1, r - 1) + pascal(c, r - 1)
However when trying to run for pascal(25,50)
on Mac OS X 10.6.8 (2.53 GHz Intel Core 2 Duo) it still hasn't finished running after 20 min.
Just to compare with erlang, I installed R15B02 and wrote equivalent program as follows:
-module(pascal).
-export([calc_pascal/2]).
calc_pascal(0,_) -> 1;
calc_pascal(C,R) when C==R -> 1;
calc_pascal(C,R) when C<R -> calc_pascal(C-1,R-1) + calc_pascal(C-1,R).
pascal:calc_pascal(25,50)
finishes in ~4sec.
Why might be the reason for such a huge performance difference? Is jvm not as advanced as erlang runtime for recursive programs?
If I make the same mistake in the Scala program that you made in the Erlang version, it runs very fast. Might this be the reason?
Pascal's number performance in ms
c,r Scala Erlang
10,20 21 22
11,22 6 72
12,24 16 272
13,26 71 1034
14,28 299 3982
15,30 802 16124
16,32 3885 60420
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With