Memoization or memoisation is an optimization technique used in computing to accelerate program execution. It involves storing the results of costly function calls, particularly to pure functions, and retrieving the cached result when the same inputs are encountered again. By saving the outcomes of previous operations in a data structure like an array or hash table, subsequent calculations can be avoided by simply looking up the precomputed answer. This technique helps improve program performance by reducing redundant computations.
Tabulation is an optimization technique used in computing to enhance program efficiency. Unlike recursion, where subproblems are solved starting from the top, tabulation takes a bottom-up approach. It involves calculating values in advance and storing them in a table. This iterative process allows for efficient lookup of precomputed results when needed. By systematically working from the bottom and progressively building up the solution, tabulation avoids redundant computations and significantly speeds up program execution.
For example, to calculate the Fibonacci numbers
- fb(0) = 0
- fb(1) = 1
- fb(n) = fb(n-1) + fb(n-2)
The series is 0,1,1,2,3,5,8,13……
Write a recursive function to find the Fibonacci numbers
int fb(int n) {
if (n == 0 || n == 1)
return n;
return fb(n-1) + fb(n-2);
}Write a recursive function with Memoization to find the Fibonacci numbers
#include <vector>
#include <iostream>
using namespace std;
int fb_mem(int n, vector<int> & memo){
if (memo[n] != -1){
cout<<"n = "<<n<<" memo["<<n<<"] = "<<memo[n]<<endl; // Only call when memo has previously cached
return memo[n];
}
if (n<=2){
return 1; //base case
}
memo[n] = fb_mem(n-1, memo) + fb_mem(n-2, memo); //saving the outcome for further use
return memo[n];
}
int main(){
int n=7;
vector<int> memo(n+1, -1);
cout << fb_mem(n,memo) << endl;
}Result
That means firstly memo[3] is retrieved when n=3 is encountered again, then memo[4] and finally memo[5]. The result Fibonacci numbers at position 7 is 13.
Refer to the following diagram, the recursive function is called from step 1 to 10 (blue circle with number in white color). Step 7 retrieves cached result memo[3], step 9 and 10 retrieves memo[4] and memo[5]. The numbers with red stroke and subsequent calculations are avoided as the callers (with red circle) simply look up the precomputed answer.
