In this lab we will see why recursion by itself could be stupid and wasteful and we will see how one can take the stupidity out of this very useful technique. While doing that we will also learn how to use STL maps.
int fibonacci(int i){
cout << "computing fibonacci(" << i << ")" << endl;
if ((i==1)||(i==2))
return 1;
return fibonacci(i-1)+fibonacci(i-2);
}
The complete program is as follows:
#include <iostream>
using namespace std;
int fibonacci(int i){
cout << "computing fibonacci(" << i << ")" << endl;
if ((i==1)||(i==2))
return 1;
return fibonacci(i-1)+fibonacci(i-2);
}
int main(int argc, char** argv){
if (argc!=2){
cout << "parameters: n" << endl;
return 1;
}
cout << fibonacci(atoi(argv[1])) << endl;
return 0;
}
If you try running it for 4 here is what you get:
./fibonacci.o 4 computing fibonacci(4) computing fibonacci(3) computing fibonacci(2) computing fibonacci(1) computing fibonacci(2) 3As you can see the fibonacci was called for i=2 twice. While repeating a subproblem twice is not desirable it may not be the end of the world either. But, what if sometimes we run the recursive function for the same parameters tens or hundreds of times? Try running fibonacci.o for 40 and see if you can count how many times fibonacci(1) was computed.
STL map is an associative container. It keeps pairs of key, values. In our case, we want to keep the frequency of number i when fibonacci is called on it. So, keys and values are both integers. Therefore we need a map<int,int>. Here is how we can use a map for this purpose: (code is here)
#include <iostream>
#include <map>
using namespace std;
map<int,int> freq;
int fibonacci(int i){
//cout << "computing fibonacci(" << i << ")" << endl;
freq[i]++;
if ((i==1)||(i==2))
return 1;
return fibonacci(i-1)+fibonacci(i-2);
}
int main(int argc, char** argv){
if (argc!=2){
cout << "parameters: n" << endl;
return 1;
}
cout << fibonacci(atoi(argv[1])) << endl;
for (map<int,int>::iterator itr=freq.begin(); itr!=freq.end(); itr++)
cout << itr->first << " :" << itr->second << endl;
return 0;
}
We keep a variable of type map<int,int> (named freq) and whenever we see i as the parameter of fibonacci function, we increase freq[i]. STL map has overloaded operator[] to retrieve the value for the given key but also it inserts a default value into the map if the key doesn't exist. Where the value is of type int, we can trust the map to insert a 0 if we use [] on a key that didn't previously exist in the map.
In the main, we try printing everything in the map using its iterator. Unlike in vectors, iterators are our only way to traverse a map. Since each item in the map is a pair of key-values, itr->first will give us the key, and itr->second will give us the value. So, after computing the fibonacci, we are printing all i's on which fibonacci was called, along with number of times that particular i was the parameter of the fibonacci.
Now, try running the program again on 40. Make sure you comment out the cout statement inside the recursive function and also remember to compile again. You may need to wait one or two minutes for it to finish. How many times did we call the fibonacci function on 1, 2, or 3? Is this acceptable?
Here we revisit the same problem in computing c(n,k), that is the number of ways we can choose k items out of n distinct items not caring about the order.
We can write a recursive formula for c(n,k). In fact, we either chose item number n or we don't. If we do, we would have to choose k-1 items from the remaining n-1 items. If we don't pick the nth item, we would have to choose all k items from the remaining n-1 items. Therefore:
c(n,k) = c(n-1,k) + c(n-1,k-1)
The two base cases are when n==k, in which case we have to pick all the items, so c(n,n)=1; and when k=1, in which case we can pick any of the n items, so c(n,1)=n. As a result, a recursive function for choose can be implemented as follows:
int choose(int n, int k){
if (k==n)
return 1;
if (k==1)
return n;
return choose(n-1,k)+choose(n-1,k-1);
}
Again, we want to use STL maps to keep the number of times the function choose is called on parameters n and k. Here, our key is a pair (namely (n,k)), and the values are integers (the counts). So, the variable freq will be of type map<pair<int,int>,int> as opposed to the previous map<int,int>. Here is the whole program that keeps the frequencies and also prints them at the end. (code is here)
#include <iostream>
#include <map>
using namespace std;
map<pair<int,int>,int> freq;
int choose(int n, int k){
//cout << "computing choose(" << n << "," << k << ")" << endl;
freq[make_pair(n,k)]++;
if (k==n)
return 1;
if (k==1)
return n;
return choose(n-1,k)+choose(n-1,k-1);
}
int main(int argc, char** argv){
if (argc!=3){
cout << "parameters: n and k" << endl;
return 1;
}
cout <<"result:" << choose(atoi(argv[1]), atoi(argv[2])) << endl;
cout << "counts: " << endl;
for (map<pair<int,int>,int>::iterator itr=freq.begin(); itr!=freq.end(); itr++){
pair<int,int> key = itr->first;
int value = itr->second;
cout << "(" << key.first << "," << key.second << "): " << value << endl;
}
return 0;
}
Notice that we used the std::make_pair function to wrap n and k in a pair. Also, notice that the type of iterator in the main function changed to the iterator type for map<pair<int,int>,int> that is map<pair<int,int>,int>::iterator. This means itr->first (which is the key), is of type pair<int,int> itself.
Now try running this program for n=10 and k=5 or for n=100 and k = 5. Here is what I get for n=10 and k=5:
./choose.o 10 5 result:252 counts: (2,1): 35 (2,2): 35 (3,1): 20 (3,2): 35 (3,3): 15 (4,1): 10 (4,2): 20 (4,3): 15 (4,4): 5 (5,1): 4 (5,2): 10 (5,3): 10 (5,4): 5 (5,5): 1 (6,1): 1 (6,2): 4 (6,3): 6 (6,4): 4 (6,5): 1 (7,2): 1 (7,3): 3 (7,4): 3 (7,5): 1 (8,3): 1 (8,4): 2 (8,5): 1 (9,4): 1 (9,5): 1 (10,5): 1So, recursive computation of choose is also wasteful.
We will see how we can use memoization in computing c(n,k). Your job is to use the same technique for computing the ith element in fibonacci series. Memoization is the technique of storing the result of the recursion for each parameter and using them if needed again. Another technique is dynamic programming but it is out of the scope of this lab.
We will use a map to store the result of c(n,k). Just like when we were counting the number of times c(n,k) was called for a specific pair (n,k), the keys of the map are of type pair<int,int> and the values are of type int. So, just like the variable freq we used there, we need a variable of type map<pair<int,int>,int> which we call memo. Here is how we can use this variable to avoid re-computing c(n,k) if we have computed it before: (code is here)
map<pair<int,int>,int> memo;
int choose(int n, int k){
//cout << "computing choose(" << n << "," << k << ")" << endl;
freq[make_pair(n,k)]++;
if (k==n){
memo[make_pair(n,k)]=1;
return 1;
}
if (k==1){
memo[make_pair(n,k)]=1;
return n;
}
int c_1, c_2;
map<pair<int,int>,int>::iterator itr1 = memo.find(make_pair(n-1,k));
if (itr1!=memo.end())
c_1 = itr1->second;
else
c_1 = choose(n-1,k);
map<pair<int,int>,int>::iterator itr2 = memo.find(make_pair(n-1,k-1));
if (itr2!=memo.end())
c_2 = itr2->second;
else
c_2 = choose(n-1,k-1);
memo[make_pair(n,k)] = c_1 + c_2;
return c_1 + c_2;
}
Notice how we are using the find method of map to search for a key and get its position as an iterator. If the key doesn't exist in the map, the map will return the iterator end(). If it does, we can use *itr to get the key-value pair, which means itr->first will be the key and itr->second will be the value.
Try running the new program for n=10 and k=5 and verify that you get the same answer and also that the counts are all 1's. Now, go ahead, and do the same thing for fibonacci.