       Re: why do recursive function calculations take so long in Mathematica?

• To: mathgroup at smc.vnet.net
• Subject: [mg43577] Re: why do recursive function calculations take so long in Mathematica?
• From: "Peter Pein" <peter1963 at totalise.co.uk>
• Date: Sun, 21 Sep 2003 05:42:17 -0400 (EDT)
• References: <bkhbk7\$7lr\$1@smc.vnet.net>
• Sender: owner-wri-mathgroup at wolfram.com

```Hello G. Feigin,
have a look at The Mathematica Book 2.4.9:

dr[0, 0] := 0;
dr[n_, n_] := 0;
dr[n_, 0] := 1;
dr[n_, k_] := dr[n, k - 1] + dr[n - 1, k];
In:=
Timing[dr[16, 15]]
Out=
{320.38 Second, 9694845}

In:= (* function will remember the computed values*)
Remove[dr];
dr[0, 0] = 0;
dr[n_, n_] = 0;
dr[n_, 0] = 1;
dr[n_, k_] := dr[n, k] = dr[n, k - 1] + dr[n - 1, k];
In:=
Timing[dr[16, 15]]
Out=
{0. Second, 9694845}

Peter

"G Feigin" <g.feigin at verizon.net> schrieb im Newsbeitrag
news:bkhbk7\$7lr\$1 at smc.vnet.net...
> I defined the following simple recursive function:
>
> dr[0,0] := 0; dr[n_,n_]:= 0;
> dr[n_,0]:=1;dr[n_,k_]:=dr[n,k-1]+dr[n-1,k];
>
> To evaluate dr[16,15] takes about 5 minutes on a Pentium class
> machine, an absurdly long time.  Why? And what can I do to speed
> things up?  By the way,
> if I perform the recursion in an Excel spreadsheet on the same
> machine, the calculation time is practically instantaneous.
>