performance of tail-recursion
- To: mathgroup at smc.vnet.net
- Subject: [mg73699] performance of tail-recursion
- From: "厉正吉" <zhengji.li at gmail.com>
- Date: Mon, 26 Feb 2007 06:03:58 -0500 (EST)
Dear all, It's sure that Mathematica supports tail-recursion. But the performance does not seems that good. Here is my test code. $RecursionLimit = Infinity; $IterationLimit = Infinity; fact1[1] = 1; fact1[n_] := n fact1[n - 1]; (* tail-recursion *) auxfact[1, m_] := m; auxfact[n_, m_] := auxfact[n - 1, m n]; fact2[n_] := auxfact[n, 1]; (* Testbench *) nn = 10000; AbsoluteTiming[b = fact1[nn];] AbsoluteTiming[a = fact2[nn];] AbsoluteTiming[Times @@ Range[nn];] AbsoluteTiming[nn!;] ============ Output ============= {0.2703942 Second, Null} {0.3004380 Second, Null} {0.0400584 Second, Null} {0. Second, Null} Why fact2 is slower than fact1? Tail-recursion can be transformed to "iteration", then typically, it should be faster than recursion. I guess that it is because auxfact's definition is more complex than that of fact1, so it takes more time for the pattern matcher to find a proper downvalue of auxfact to evaluate. If I update the definition of fact1 to something like this: fact1[1, m_] = 1; fact1[n_, m_] := n fact1[n - 1, m]; It's slower than before but still a little bit faster than fact2. I hope that tail-recursion is not flowery in Mathematica, is it? -- Li Zhengji ------------------------------------------------------------- If all you have is a hammer, everything is a nail. -------------------------------------------------------------