[Date Index]
[Thread Index]
[Author Index]
Re: Recursive function
*To*: mathgroup at smc.vnet.net
*Subject*: [mg83764] Re: Recursive function
*From*: Jean-Marc Gulliet <jeanmarc.gulliet at gmail.com>
*Date*: Fri, 30 Nov 2007 05:14:20 -0500 (EST)
*Organization*: The Open University, Milton Keynes, UK
*References*: <fim91k$rpi$1@smc.vnet.net>
Miguel wrote:
> How can I accelerate the execution of the recursive function?. Perhaps
> with Compile?
By using *memoization*, that is by defining functions that remember the
intermediate values they have already found. See [1] for general
information about the technique, and [2] and [3] for specific examples
applied to Mathematica.
Basically, rather than defining, say, the general term of the recursive
function f as f[n_] := body_of_the_function, you define it as f[n_] :=
f[n] = body_of_the_function, so the intermediate values are going to be
stored in the symbol f[1], f[2], ... , f[n-1], and finally f[n].
Here is an example with the classic Fibonacci sequence and the timing
for the versions without and with memoization.
(* Timing for recursive Fibonacci WITHOUT memoization *)
In[32]:= Clear[f]
f[0] = 1; f[1] = 1;
f[n_] := f[n - 1] + f[n - 2]
Table[First@Timing[f[n]], {n, 1, 40, 5}]
Out[35]= {0., 0., 0., 0.015, 0.063, 0.953, 9.516, 216.843}
(* Timing for recursive Fibonacci WITH memoization *)
In[36]:= Clear[f]
f[0] = 1; f[1] = 1;
f[n_] := f[n] = f[n - 1] + f[n - 2]
Table[First@Timing[f[n]], {n, 1, 40, 5}]
Out[39]= {0., 0., 0., 0., 0., 0., 0., 0.}
[1] "Memoization", _Wikipedia, the free encyclopedia_
http://en.wikipedia.org/wiki/Memoization
[2] "2.5.9 Functions That Remember Values They Have Found", _The
Mathematica Book Online_,
http://documents.wolfram.com/mathematica/book/section-2.5.9
[3] "Functions That Remember Values They Have Found", _Mathematica
Tutorial_,
http://reference.wolfram.com/mathematica/tutorial/FunctionsThatRememberValuesTheyHaveFound.html
Regards,
--
Jean-Marc
Prev by Date:
**Re: Reading excel data**
Next by Date:
**Re: FindInstance puzzler**
Previous by thread:
**Re: Recursive function**
Next by thread:
**Re: Convert nxn matrix to a column vector with (n^2)**
| |