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