Convert c function from recursive to iterations with stack-CodePudding

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.

CodePudding user response：

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});
// ^^^^^^

CodePudding user response：

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();
}