4
$\begingroup$

This one can not remember the value. Code 1.

f[x_] := f[x] = f[x - 1] + f[x - 2];
f[1] = f[2] = 1;
f[5]
?f

The 2nd one can keep the value it finds. Code 2.

    ClearAll[f]
    f[x_] := f[x - 1] + f[x - 2];
    f[1] = f[2] = 1;
    f[5]
    ?f

But if you want to calculate f[4] after you calculate f[5], in the Code 1 Mathematica would fetch the values of f[4] from the memory when it calculates f[5] , while in the Code 2 Mathematica would preform following procedures:

f[3] = f[2] + f[1] = 1 + 1 = 2;
f[4] = f[3] + f[2] = 2 + 1 = 3

I thought these 2 should have the same number of steps to calculate f[5] for the first time. Here are procedures I thought Mathematica would do.

f[3] = f[2] + f[1] = 1 + 1 = 2;
f[4] = f[3] + f[2] = 2 + 1 = 3;
f[5] = f[4] + f[3] = 3 + 2 = 5

I'm not sure whether my thoughts is correct or not. Please point out the mistakes if I have.

 g[x_]  = g[x - 1] + g[x - 2];
    g[1] = [2] = 1;

g[3] is calculated once when finding g[4].

g[3] is calculated twice when finding g[5].

g[3] is calculated 3 times when finding g[6].

g[3] is calculated 5 times when finding g[7].

g[3] is calculated 8 times when finding g[8].

...

$\endgroup$

2 Answers 2

2
$\begingroup$

For purposes of discussion, rather than calling both variations f let us call the memoizing version f and the non-memoizing version g:

ClearAll[f]
f[x_] := f[x] = f[x - 1] + f[x - 2];
f[1] = f[2] = 1;

ClearAll[g]
g[x_] := g[x - 1] + g[x - 2];
g[1] = g[2] = 1;

f[5] with no prior memoization vs g[5]

If we show the traces of the f[5] and g[5] as graphs, we see this (click to enlarge):

f[5] vs. g[5]

The diagrams show 33 evaluation steps for f and 34 for g. In actual fact there are a total of 88 steps for both, but the diagrams suppress inert expressions for readability. Even though the two functions perform the same number of steps, they are qualitatively different. Close inspection will reveal, for example, that the value for f[3] is saved and reused, whereas the value for g[3] is calculated twice. But in this small example, the savings are not apparent because all of the assignments performed by f offset the extra calculations.

f[6] with prior memoization vs g[6]

But the difference is much more apparent if we subsequently calculate f[6] and g[6], where we retain the memoized f results from the previous evaluation:

f[6] vs g[6]

This time, f has far fewer steps due to the reuse of previously calculated results.

f[10] with no prior memoization vs g[10]

The fact that f and g both required 88 steps in the first example was but a coincidence. We a significant different if we clear the definitions of f (so as to forget the memoized values) and then calculate a larger example, f[10] and g[10]:

f[10] vs. g[10]

Labels are suppressed to keep the diagram manageable, f is on the left. With this larger example, the payoff of memoization is much more apparent. f requires 89 non-inert steps vs. 433 for g (228 vs 1138 including inerts).


Update

f[6] with no prior memoization vs g[6]

By request in the comments, here are the graphs for f[6] and g[6] with no prior memoization. They show 45 steps for f and 57 for g (116 and 151 steps respectively including inerts).

f[6] no memoization vs. g[6]

$\endgroup$
5
  • $\begingroup$ Can you show the tree graph code here? $\endgroup$
    – kile
    Commented Sep 11, 2020 at 3:56
  • $\begingroup$ Would you give a comparison f[6] without prior memorization vs g[6]? $\endgroup$
    – kile
    Commented Sep 11, 2020 at 4:02
  • $\begingroup$ And the f[5] with no prior memorization vs g[5]. The diagrams show 33 evaluation steps for f and 32 for g. If you count every line segment as a step, g[5] should be 32. $\endgroup$
    – kile
    Commented Sep 11, 2020 at 4:28
  • $\begingroup$ I have added the unmemoized f[6] comparison as requested. As for the step counts, I am counting the nodes not edges in the graphs. Each node represents a single step as reported by TraceScan. I choose to include the root node as a "step" because it is processed by the evaluator. $\endgroup$
    – WReach
    Commented Sep 11, 2020 at 13:38
  • $\begingroup$ As for the code that generates these graphs, I regret that it is not easy for me to include it here. It is part of a larger work-in-progress package and is not easily extracted into a small standalone form. As a consolation, perhaps the answers from The clearest way to represent Mathematica's evaluation sequence would be useful for continued investigation. $\endgroup$
    – WReach
    Commented Sep 11, 2020 at 13:48
5
$\begingroup$
Clear["Global`*"]

f[x_] := f[x] = f[x - 1] + f[x - 2];
f[1] = f[2] = 1;
f[5]
?f

(* 5 *)

enter image description here

Note the saved definitions

Trace[f[6]]

enter image description here

The Trace shows that lookup values were used

ClearAll[f]
f[x_] := f[x - 1] + f[x - 2];
f[1] = f[2] = 1;
f[5]
?f

(* 5 *)

enter image description here

Note that the only saved values are the two initial values.

Trace[f[6]]

enter image description here

The second Trace is much more extensive since there are no saved values other than the two initial values.

EDIT: One approach to implement a pseudo-Trace for this

ClearAll[f, f2, trace]

f[x_] := f[x - 1] + f[x - 2]
f[1] = f[2] = 1;

Format[f2] := f

f2[x_] := Inactive[Plus][Inactive[f2][x - 1], Inactive[f2][x - 2]]
f2[1] = f2[2] = 1;

trace[n_] := 
 Module[{sum = NestList[Activate[#, f2] &, Inactive[f2][n], n - 1]},
  Append[sum, sum[[-1]] // Activate]]

n = 6;

trace[n]

enter image description here

%[[-1]] == f[n]

(* True *)
$\endgroup$
1
  • $\begingroup$ The original List is difficult to understand. Could you rewrite the output form of Trace[f[6]]? Something like this below f[3] = f[2] + f[1] = 1 + 1 = 2; f[4] = f[3] + f[2] = 2 + 1 = 3; f[5] = f[4] + f[3] = 3 + 2 = 5; f[6] = f[5] + f[4] = 5 + 3 = 8 $\endgroup$
    – kile
    Commented Sep 9, 2020 at 5:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.