It's actually not where you would first look.The reason is in your tail recursion method, you are doing more work with its multiply. Try swapping around the order of the params n and s in the recursive call and it will even out.
def tailRecFact(n: BigInt, s: BigInt): BigInt = if (n == 1) s else tailRecFact(n - 1, n * s)
Moreover, most of the time in this sample is taken up with the BigInt operations which dwarf the time of the recursive call. If we switch these over to Ints (compiled to Java primitives) then you can see the how tail recursion (goto) compares to method invocation.
object Test extends App {
val N = 2000
val t0 = System.nanoTime()
for ( i <- 1 to 1000 ) {
factorial(N)
}
val t1 = System.nanoTime
for ( i <- 1 to 1000 ) {
tailRecFact(N, 1)
}
val t2 = System.nanoTime
println((t1 - t0) / 1000000f) // get milliseconds
println((t2 - t1) / 1000000f)
def factorial(n: Int): Int = if (n == 1) 1 else n * factorial(n - 1)
@tailrec
final def tailRecFact(n: Int, s: Int): Int = if (n == 1) s else tailRecFact(n - 1, s * n)
}
95.16733
3.987605
For interest, the decompiled output
public final scala.math.BigInt tailRecFact(scala.math.BigInt, scala.math.BigInt);
Code:
0: aload_1
1: iconst_1
2: invokestatic #16 // Method scala/runtime/BoxesRunTime.boxToInteger:(I)Ljava/lang/Integer;
5: invokestatic #20 // Method scala/runtime/BoxesRunTime.equalsNumObject:(Ljava/lang/Number;Ljava/lang/Object;)Z
8: ifeq 13
11: aload_2
12: areturn
13: aload_1
14: getstatic #26 // Field scala/math/BigInt$.MODULE$:Lscala/math/BigInt$;
17: iconst_1
18: invokevirtual #30 // Method scala/math/BigInt$.int2bigInt:(I)Lscala/math/BigInt;
21: invokevirtual #36 // Method scala/math/BigInt.$minus:(Lscala/math/BigInt;)Lscala/math/BigInt;
24: aload_1
25: aload_2
26: invokevirtual #39 // Method scala/math/BigInt.$times:(Lscala/math/BigInt;)Lscala/math/BigInt;
29: astore_2
30: astore_1
31: goto 0
public scala.math.BigInt factorial(scala.math.BigInt);
Code:
0: aload_1
1: iconst_1
2: invokestatic #16 // Method scala/runtime/BoxesRunTime.boxToInteger:(I)Ljava/lang/Integer;
5: invokestatic #20 // Method scala/runtime/BoxesRunTime.equalsNumObject:(Ljava/lang/Number;Ljava/lang/Object;)Z
8: ifeq 21
11: getstatic #26 // Field scala/math/BigInt$.MODULE$:Lscala/math/BigInt$;
14: iconst_1
15: invokevirtual #30 // Method scala/math/BigInt$.int2bigInt:(I)Lscala/math/BigInt;
18: goto 40
21: aload_1
22: aload_0
23: aload_1
24: getstatic #26 // Field scala/math/BigInt$.MODULE$:Lscala/math/BigInt$;
27: iconst_1
28: invokevirtual #30 // Method scala/math/BigInt$.int2bigInt:(I)Lscala/math/BigInt;
31: invokevirtual #36 // Method scala/math/BigInt.$minus:(Lscala/math/BigInt;)Lscala/math/BigInt;
34: invokevirtual #47 // Method factorial:(Lscala/math/BigInt;)Lscala/math/BigInt;
37: invokevirtual #39 // Method scala/math/BigInt.$times:(Lscala/math/BigInt;)Lscala/math/BigInt;
40: areturn