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

• To: mathgroup at smc.vnet.net
• Subject: [mg43582] Re: [mg43566] why do recursive function calculations take so long in Mathematica?
• From: Murray Eisenberg <murray at math.umass.edu>
• Date: Sun, 21 Sep 2003 05:42:21 -0400 (EDT)
• Organization: Mathematics & Statistics, Univ. of Mass./Amherst
• References: <200309201039.GAA07655@smc.vnet.net>
• Sender: owner-wri-mathgroup at wolfram.com

```The reason it takes so long is that at each stage of the recusrion,
prevously-calculated values have to be re-calculated.  To speed it up,
cache the values in the recursive relation (and you might as well may
dr[0,0] to be a Set, with =, instead of a SetDelayed, with := ):

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];

Timing[dr[16, 15]]
{0. Second, 9694845}

That's on my 933 MHz Pentium III with 512 MB RAM.

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

--
Murray Eisenberg                     murray at math.umass.edu
Mathematics & Statistics Dept.
Lederle Graduate Research Tower      phone 413 549-1020 (H)
University of Massachusetts                413 545-2859 (W)
710 North Pleasant Street            fax   413 545-1801
Amherst, MA 01003-9305

```

• Prev by Date: Re: why do recursive function calculations take so long in Mathematica?
• Next by Date: Re: Re: Re: Finding the Path to/Directory for the current EvaluationNotebook?
• Previous by thread: why do recursive function calculations take so long in Mathematica?
• Next by thread: Re: why do recursive function calculations take so long in Mathematica?