Recurrence Equations and Option Remember

The Fibonacci numbers are defined by the linear recurrence , , and . This can be coded directly by

F := proc(n) 
    if n = 0 then 0 elif n = 1 then 1 else F(n-1)+F(n-2) fi
end;

Here are the first few Fibonacci numbers

> seq( F(i), i=0..10 );

                      0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55

However this is a not an efficient way to compute the Fibonacci numbers. In fact, you will never be able to compute F(100) using this procedure even on the fastest computer. If you count the number of calls to the F procedure, you will see that it is called repeatedly on the same arguments. It is clear that one should remember the previous two values when computing the next value. This could be done in a loop in the following way

F := proc(n) local fnm1,fnm2,f;
    if n = 0 then RETURN(0) fi;
    fnm2 := 0;
    fnm1 := 1;
    for i to n do f := fnm1 + fnm2; fnm2 := fnm1; fnm1 := f od;
    fnm1
end;

Another way to code this is to use option remember. This option is used to store values as they are computed so that they can be used when they are needed. Consider

F := proc(n) option remember;
    if n = 0 then 0 elif n = 1 then 1 else F(n-1)+F(n-2) fi
end;

This program computes quite quickly. Each Maple procedure has an associated remember table. The table index is the arguments and the table entry is the function value. When is called with , Maple first looks up 's remember table to see if has already been computed. If it has, it returns the result from 's remember table. Otherwise, it executes the code for the procedure , and automatically stores the pair in 's remember table.

We also illustrate the possibility of explicitly saving values in a remember table by using the so called functional assignment. This is more flexible than the remember option because it allows one to save only selected values in the remember table.

F := proc(n) F(n) := F(n-1)+F(n-2) end;
F(0) := 0;
F(1) := 1;