MathGroup Archive 2002

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

Search the Archive

RE: Fw: Recursive Function

  • To: mathgroup at smc.vnet.net
  • Subject: [mg35898] RE: [mg35886] Fw: [mg35874] Recursive Function
  • From: "DrBob" <majort at cox-internet.com>
  • Date: Wed, 7 Aug 2002 05:59:16 -0400 (EDT)
  • Reply-to: <drbob at bigfoot.com>
  • Sender: owner-wri-mathgroup at wolfram.com

If you look at the function a bit, it's not hard to figure out.

s[0, 0] = 1
s[k_, m_] := Which[k < 0, 0, m < 0, 0, True, p*s[k - 1, m] + q*s[k, m -
1]]
Table[s[n, m], {n, 0, 4}, {m, 0, 4}] // TableForm

(output omitted)

Look at the Table and you should notice that diagonals (lower left to
upper right) are the terms of (p+q)^(n+m).  Therefore, the general
formula is

Binomial[n+m,m] p^n q^m

There's a more involved (and general) way of doing this, by defining a
function f[p,q]=Sum[S[n,m],{n,0,Infinity},{m,0,Infinity}] and using the
recurrence relation to work out an equation involving f and then solve
it for f.  Once you know what f is, you find its series expansion, and
that gives you your original S terms.  In a roundabout way (for this
example) you'd wind up making the same discovery that I mentioned above,
just from looking at the Table.

Finally, you could use RSolve to get one row at a time of the Table
above.  Once you've done a few, you should see the pattern.

Using any of those methods, it will be helpful to remember that the
recurrence relation (and hence the Table) is symmetric (with a switch of
p and q).  Hence, figuring out a row also gives you a column.  That
makes it natural, by the way, to look at the diagonals as I did above.

Bobby Treat

-----Original Message-----
From: Constantine Elster [mailto:celster at cs.technion.ac.il] 
To: mathgroup at smc.vnet.net
Subject: [mg35898] [mg35886] Fw: [mg35874] Recursive Function

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: [mg35898] [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: [mg35898] [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
>
>
>
>






  • Prev by Date: Re: Fw: Recursive Function
  • Next by Date: Re: Fw: Recursive Function
  • Previous by thread: Re: Fw: Recursive Function
  • Next by thread: Re: Fw: Recursive Function