Re: Fw: Recursive Function
- To: mathgroup at smc.vnet.net
- Subject: [mg35894] Re: [mg35886] Fw: [mg35874] Recursive Function
- From: Ken Levasseur <Kenneth_Levasseur at uml.edu>
- Date: Wed, 7 Aug 2002 05:59:12 -0400 (EDT)
- References: <200208051002.GAA18120@smc.vnet.net>
- Sender: owner-wri-mathgroup at wolfram.com
Constantine:
Here's a hint: Evaluate the following with various values of n.
n = 5;
Map[S[#, n - #] & , Range[0, n]]
Ken Levasseur
Math Sci.
UMass Lowell
Constantine Elster wrote:
> Hi, all.
>
> In the help pages I found how to find a non recursive function equivalent to
> a function that has one argument.
> More precisly I'm looking for a general non-recursive formula for the
> following recursive function (has 2 arguments):
>
> S[0,0] = 1
> S[k_,m_] := Which [
> k < 0, 0,
> m < 0, 0,
> True, p*S[k-1,m] + (1-p)*S[k,m-1]]
>
> I'll be very pleasant if anyone can help or give a hint in how to find the
> equivalent non-recursive function.
> Thanks in advance.
> Constantine.
>
> Constantine Elster
> Computer Science Dept.
> Technion I.I.T.
> Office: Taub 411
> Tel: +972 4 8294375
>
> ----- Original Message -----
> From: "DrBob" <majort at cox-internet.com>
To: mathgroup at smc.vnet.net
> Subject: [mg35894] [mg35886] RE: [mg35874] Recursive Function
>
> > >>Can Mathematica find a non-recursive function equivalent to a given
> > recursive function?
> >
> > Sometimes. Look for "recurrence relations" in Help. In general, it
> > requires thought, and that's YOUR job, not Mathematica's. See below for
> > hints.
> >
> > Look up "Recursive functions" in help and read the section on functions
> > that remember their values. Note two important points, in addition to
> > what it says there:
> >
> > 1) You're trading space for time. If the values you're saving take up
> > a LOT of space and/or you're saving a LOT of values, that can become a
> > problem.
> >
> > 2) If you compute, for instance, F[2000] and F is recursive (with or
> > without saving values) you'll run into $RecursionLimit. The simple fix
> > is to make sure you compute things from bottom up rather than top down.
> > If the first thing you need is F[2000], compute the others first like
> > this:
> >
> > Last[F/@Range[2000]]
> >
> > You can also use a non-recursive definition like the following (for the
> > Fibonacci example). If you want the n-th term of the Fibonacci series,
> > do something like this:
> >
> > nxt[{a_, b_}] := {b, a + b}
> > fib[n_] := Last[Nest[nxt, {0, 1}, n - 1]]
> > fib[7]
> > fib /@ Range[10]
> >
> > 13
> > {1, 1, 2, 3, 5, 8, 13, 21, 34, 55}
> >
> > This method is best if you won't need again the values you've already
> > computed; if you will, save values as explained in Help.
> >
> > Bobby Treat
> >
> > -----Original Message-----
> > From: Constantine [mailto:celster at cs.technion.ac.il]
To: mathgroup at smc.vnet.net
> > Sent: Sunday, August 04, 2002 5:01 AM
> > Subject: [mg35894] [mg35886] [mg35874] Recursive Function
> >
> > Hi,
> > Can Mathematica find a non-recursive function equivalent to a given
> > recursive function?
> > Anyone who knows, please, please, please, reply...
> >
> >
> > Constantine Elster
> > Computer Science Dept.
> > Technion I.I.T.
> > Office: Taub 411
> > Tel: +972 4 8294375
> >
> >
> >
> >
- References:
- Fw: Recursive Function
- From: "Constantine Elster" <celster@cs.technion.ac.il>
- Fw: Recursive Function