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:
In[1]:= (* your definition *)
dr[0, 0] := 0;
dr[n_, n_] := 0;
dr[n_, 0] := 1;
dr[n_, k_] := dr[n, k - 1] + dr[n - 1, k];
In[5]:=
Timing[dr[16, 15]]
Out[5]=
{320.38 Second, 9694845}
In[6]:= (* 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[11]:=
Timing[dr[16, 15]]
Out[11]=
{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.
>
> Please reply by email.
>