RE: Recursive Function
- To: mathgroup at smc.vnet.net
- Subject: [mg35885] RE: [mg35874] Recursive Function
- From: "DrBob" <majort at cox-internet.com>
- Date: Mon, 5 Aug 2002 06:02:00 -0400 (EDT)
- Reply-to: <drbob at bigfoot.com>
- Sender: owner-wri-mathgroup at wolfram.com
>>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
Subject: [mg35885] [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