Re: why do recursive function calculations take so long in Mathematica?
- To: mathgroup at smc.vnet.net
- Subject: [mg43575] Re: why do recursive function calculations take so long in Mathematica?
- From: "Steve Luttrell" <luttrell at _removemefirst_westmal.demon.co.uk>
- Date: Sun, 21 Sep 2003 05:42:15 -0400 (EDT)
- References: <bkhbk7$7lr$1@smc.vnet.net>
- Sender: owner-wri-mathgroup at wolfram.com
You need to memorise the intermediate results thus: 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]; -- Steve Luttrell West Malvern, UK "G Feigin" <g.feigin at verizon.net> wrote in message 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. >