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