MathGroup Archive 2007

[Date Index] [Thread Index] [Author Index]

Search the Archive

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)