Convert this recursive function to iterative
c++, iteration, recursion
Solution
The main reason why this function is slow is because it has exponential complexity, and it keeps recalculating the same members again and again. One possible cure is memoize pattern (handily explained with examples in C++ here). The idea is to store every result in a structure with a quick access (e.g. an array) and every time you need it again, retrieve already precomputed result. Of course, this approach is limited by the size of your memory, so it won't work for extremely big numbers...
In your case, we could do something like that (keeping the recursion but memoizing the results):
#include <cmath>
#include <map>
#include <utility>
std::map<std::pair<int,int>,int> MM;
int M(int H, int T){
std::pair<int,int> key = std::make_pair(H,T);
std::map<std::pair<int,int>,int>::iterator found = MM.find(key);
if (found!=MM.end()) return found->second; // skip the calculations if we can
int result = 0;
if (H == 0) result = T;
else if (H + 1 >= T) result = pow(2, T) - 1;
else result = M(H - 1, T - 1) + M(H, T - 1) + 1;
MM[key] = result;
return result;
}
Regarding time complexity, C++ maps are tree maps, so searching there is of the order of N*log(N) where N is the size of the map (number of results which have been already computed). There are also hash maps for C++ which are part of the STL but not part of the standard library, as was already mentioned on SO. Hash map promises constant search time (the value of the constant is not specified though :) ), so you might also give them a try.
Problem
How can I convert this recursive function to an iterative function? ``` #include <cmath> int M(int H, int T){ if (H == 0) return T; if (H + 1 >= T) return pow(2, T) - 1; return M(H - 1, T - 1) + M(H, T - 1) + 1; } ``` Well it's a 3-line code but it's very hard for me to convert this to an iterative function. Because it has 2 variables. And I don't know anything about `Stacks` so I couldn't convert that. My purpose for doing this is speed of the function. This function is too slow. I wanted to use `map` to make this faster but I have 3 variables `M`, `H` and `T` so I couldn't use `map`