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