MathGroup Archive 2007

[Date Index] [Thread Index] [Author Index]

Search the Archive

performance of tail-recursion

  • To: mathgroup at
  • Subject: [mg73699] performance of tail-recursion
  • From: "厉正吉" < at>
  • 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];]

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