Convert c++ function from recursive to iterations with stack

Question

I'm trying to convert this function from recursive to iterations with stack but I can't figure out how and I keep failing

int F(int n)
{
    if (n <= 1) return 1;
    int a = n + F(n - 1);
    cout << a << endl;
    int b = n * F(n / 2);
    int c = n - 2 - (a + b) % 2;
    int d = F(c);
    return a + b + d;
}

I tried to debug the code and break it down but luck was not on my side

edit: these are the requirements

• You are not allowed to use any built-in functions except those from: <cstdlib>, <cstdio>, <cstring>, <iostream> and <stack>.
• You are not allowed to use string, vector, or anything from STL libraries except stack.

Moreover, I attempted to make multiple stack for each variable to store the results then substitute the answer but am still working on it.

Answer 1

Let's look at the single parts of the recursion:

We have f(n-1), f(n/2) and f(n-2-[0 or 1], no matter how big a or b might ever get. All these recursive calls fall back to a lower value.

First few values:

f(n) = 1; // n <= 1
f(2) = (2 + f(1)) + (2 * f(1)) + f(-1) // (c = 2 - 2 - 5 % 2)
     = 6
f(3) = (3 + f(2)) + (3 * f(1)) + f(1) // (c = 3 - 2 - 12 % 2)
     = 13
f(4) = (4 + f(3)) + (4 * f(2)) + f(1)  // (c = 4 - 2 - 41 % 2)
     = 42
f(5) = (5 + f(4)) + (5 * f(2)) + f(2)  // (c = 5 - 2 - 77 % 2)
     = 83

Obviously we can calculate a new value based on old ones – and if we calculate these first, we can simply look them up – apart from n == 2 where we'd get a negative lookup index. So we might initialise a std::vector with f(0), f(1) and f(2) (i.e. 1, 1, 6) and then iterate from 3 onwards until n calculating new values based upon the lookups of old ones:

    if n <= 1:
        return 1;
    std::vector v({1, 1, 6});
    if n >= v.size():
        v.reserve(n + 1); // avoid unnecessary re-allocations
        iterate i from v.size() up to n inclusive:
            v.push_back(calculate, instead recursive calls look up in vector!);
    return v[n]; 

Optimisation opportunity: If you retain results from previous calculations you don't need to re-calculate the values again and again (for the price of constantly instead of temporarily consuming quite a bit of memory!); all you have to do for is making the vector static:

   static std::vector v({1, 1, 6});
// ^^^^^^

Edit – according to the edits of the question (referring to version 4):

As you are not allowed to use std::vector as proposed above instead allocate an array:

auto v = new unsigned int[std::max(3, n + 1)] { 1, 1, 6};
// I personally prefer unsigned int as negative values aren't possible anyway...

// calculate as with the vector

auto result = v[n];
delete[] v;
return result;

Keeping old values for future calls still is possible, but more complicated; you need to remember how large your array is and if n is greater than the size re-allocate a new array, copy values from old one to and delete the latter.

This approach keeps the requirements of the task as using std::stack is not explicitly requested... If that gets enforced then the algorithm won't change – solely the lookup gets pretty ugly; you need in addition to your main stack a temporary one to be able to backup the elements on top of those you want to lookup up:

// lookup the three values in DESCENDING order, each one
// as follows:
while(stack.size() > lookupIndex)
{
    backup.push(stack.top());
    stack.pop();
}
// now top elements have been moved away from main stack and
// backed up; the element to be looked up is moved, too;
// for illustration: consider lookupIndex == 0; what would be
// the main stack's size after popping the surplus elements???
lookupValue = backup().top();

// now as you have looked up all three values move the elements
// in the backup stack back to the main stack:
while(!backup.empty()) { /* analogously to above */ }

You can spare moving back if you are calculating the final value for n – unless you retain the main stack for future calls analogously to the static vector above (make it static analogously...).

Final note: I think more than anything else you can learn from this example how much additional effort – in coding and in runtime – you will load upon your shoulders if you chose a bad data structure compared to having chosen a suitable one...

Answer 2

Consider that

F(n) = 1 for all n <= 1, especially
F(0) = 1  and  F(1) = 1

This is basically all you need to get the solution with a loop:

int F2(int n) {
    std::vector<int> F{1,1};
    for (int i=2;i <= n; ++i) {
        int a = i + F[i-1];
        int b = i * F[i/2];
        int x = i-2-(a+b)%2;   // might be negative
        int d = x>0 ? F[x] : 1;        
        F.push_back(a+b+d);
    }
    return F.back();
}