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)