Memoization means almost optimal number of unique calculations.
The first guy is the worst: keeps repeating same calculation again and again and again and doesn't have the benefit of aggregating sums. (i.e. look at the output of
Trace[fib1] -- it's splitting the evaluation tree every level, recursing all the way down, so not summing until it sees actual number, meaning maximal number of repeated evaluations.).
The third has the benefit of addition regrouping. You can see this from something as simple as coding up your own version of
FixedPoint, which giving us the benefit of allowing a window of what happens on each level:
ClearAll[c]; Timing[FixedPoint[(# /. frules // Echo) &, fib3]]
1+fib3+2 fib3+2 (1+fib3+fib3)+fib3
See how at level 2, since the sum happened before the rule is applied, there's already an improvement over naive w/
2 fib3 only needing one replacement of
fib3 instead of the two that happens in
fib1 evaluations at this level. And this happens more and more as you progress in levels, which really adds up. This means huge gains relative to naive especially once we start w/ something that allows a nice eventual depth like
This also suggests an improvement over the original repeated rule application, which is an
Expand that means each rule only has to apply once per level. This isn't going to beat memorizing all output so you only have to calculate a minimal number of times, and there's an expense with the expand, but it more than makes up for itself eventually against straight repeated rules. It achieves parity with
//. for my laptop at around depth 10, and absolutely dominates by 35:
Timing[ FixedPoint[(# /. frules // Expand) &, fib3]]
Timing[fib3 //. frules]