Re: why do recursive function calculations take so long in Mathematica?
- To: mathgroup at smc.vnet.net
- Subject: [mg43570] Re: why do recursive function calculations take so long in Mathematica?
- From: bobhanlon at aol.com (Bob Hanlon)
- Date: Sun, 21 Sep 2003 05:42:11 -0400 (EDT)
- References: <bkhbk7$7lr$1@smc.vnet.net>
- Sender: owner-wri-mathgroup at wolfram.com
Add memory to the recursion definition.
Clear[dr];
dr[n_,n_]:=0;
dr[n_,0]:=1;
dr[n_,k_]:=dr[n,k]=dr[n,k-1]+dr[n-1,k];
dr[16,15]//Timing
{0.01 Second,9694845}
Bob Hanlon
In article <bkhbk7$7lr$1 at smc.vnet.net>, g.feigin at verizon.net (G Feigin) wrote:
<< 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.