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

```

• Prev by Date: Re: simple question
• Next by Date: Re: deleting a title or subtitle in a notebook
• Previous by thread: Re: conditional is giving wrong value
• Next by thread: I believe I finally figured out what "affects printing but not evaluation" means