Geek asks and answers

Erlang vs jvm (scala) recursion efficiency

As a scala learning exercise and functional programming, I implemented the following non-tail-recursive def, which calculates the pascal number at any location. The program itself serves as the definition of the Pascal triangle. It looks like this

      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 you try to run for pascal(25,50)Mac OS X 10.6.8 (2.53 GHz Intel Core 2 Duo), it still does not work after 20 minutes .

Just to compare with erlang, I installed R15B02 and wrote an 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)ends in ~ 4 sec .

, , ? jvm , erlang ?

+5
2

Scala, Erlang, . , ?

+13

Pascal

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
+3

More articles:


All Articles