Services & ResourcesWolfram ForumsMathGroup Archive

[Date Index] [Thread Index] [Author Index]

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>
• Reply-to: murray at math.umass.edu
• 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.
> 
> Please reply by email.
> 
> 

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

• References:
  • why do recursive function calculations take so long in Mathematica?
    • From: g.feigin@verizon.net (G Feigin)