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.
-------------------------------------------------------------