```1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 ``` ```#include #include #include // memoizer. // usage: m(f, a) // returns f(a), memoizing the result. f should invoke 'm(f, x)' to recurse. template < class Result, class Arg, class ResultStore = std::map > class memoizer1{ public: template const Result& operator()(F f, const Arg& a){ typename ResultStore::const_iterator it = memo_.find(a); if(it == memo_.end()) { it = memo_.insert(make_pair(a, f(a))).first; } return it->second; } private: ResultStore memo_; }; // driver function, forward declaration int fib(int); namespace { int total_ops = 0; // implementation int fib_(int n){ ++total_ops; if(n == 0 || n == 1) return 1; else // recurse into driver, not implementation, to ensure // intermediate results are memoized. return fib(n-1) + fib(n-2); } } // driver function int fib(int n) { static memoizer1 memo; return memo(fib_, n); } using namespace std; int main(){ total_ops = 0; cout << "fib(8) == " << fib(8) << endl; cout << "cost was " << total_ops << endl; total_ops = 0; cout << "fib(9) == " << fib(9) << endl; cout << "cost was " << total_ops << endl; } ```
 ```1 2 3 4 ``` ```fib(8) == 34 cost was 9 fib(9) == 55 cost was 1 ```