       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  for general
information about the technique, and  and  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, f, ... , 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:= Clear[f]
f = 1; f = 1;
f[n_] := f[n - 1] + f[n - 2]
Table[First@Timing[f[n]], {n, 1, 40, 5}]

Out= {0., 0., 0., 0.015, 0.063, 0.953, 9.516, 216.843}

(* Timing for recursive Fibonacci WITH memoization *)

In:= Clear[f]
f = 1; f = 1;
f[n_] := f[n] = f[n - 1] + f[n - 2]
Table[First@Timing[f[n]], {n, 1, 40, 5}]

Out= {0., 0., 0., 0., 0., 0., 0., 0.}

 "Memoization", _Wikipedia, the free encyclopedia_
http://en.wikipedia.org/wiki/Memoization

 "2.5.9 Functions That Remember Values They Have Found",  _The
Mathematica Book Online_,
http://documents.wolfram.com/mathematica/book/section-2.5.9

 "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)