Services & ResourcesWolfram ForumsMathGroup Archive

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

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>