Re: Combined Set, SetDelayed
- To: mathgroup at smc.vnet.net
- Subject: [mg100787] Re: Combined Set, SetDelayed
- From: Helen Read <hpr at together.net>
- Date: Sun, 14 Jun 2009 05:38:22 -0400 (EDT)
- References: <h0vteh$6v2$1@smc.vnet.net>
- Reply-to: HPR <read at math.uvm.edu>
Sid wrote:
> Hi,
>
> This may be a silly question but I have not found an answer to it yet
> in the Documentation Centre.
>
> In dynamic programming the following construct
>
>
> f [ x_, y_] := f [x,y] = ......
>
> is used, unless I am mistaken.
>
> I'd like to know if there are other situations where we must write a
> function definition in the above format.
The idea is that the function is not evaluated when it is defined, but
once it is evaluated, it remembers values that have been computed. This
is extremely useful when defining a function recursively.
Try this:
a[0] = 1;
a[1] = 2;
a[n_] := a[n - 1] - a[n - 2]
Table[a[n], {n, 0, 25}] // Timing
And compare with this:
b[0] = 1;
b[1] = 2;
b[n_] := b[n] = b[n - 1] - b[n - 2]
Table[b[n], {n, 0, 25}] // Timing
On my system, the first table, where it has to start over every time and
run through the entire (longer and longer as you go) recursion, took
0.811 seconds. The second version, using the function that remembers
values, took only 1.87003*10^-15 seconds.
And if the table requires more steps than the recursion limit (the
default is 255), it won't even work unless the function is defined to
remember values.
--
Helen Read
University of Vermont