Fw: Recursive Function
- To: mathgroup at smc.vnet.net
- Subject: [mg35886] Fw: [mg35874] Recursive Function
- From: "Constantine Elster" <celster at cs.technion.ac.il>
- Date: Mon, 5 Aug 2002 06:02:08 -0400 (EDT)
- Sender: owner-wri-mathgroup at wolfram.com
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: [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: [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
>
>
>
>
- Follow-Ups:
- Re: Fw: Recursive Function
- From: Ken Levasseur <Kenneth_Levasseur@uml.edu>
- Re: Fw: Recursive Function