3W4yXo - Online C++ Compiler & Debugging Tool

#include <iostream>
#include <stack>
using namespace std;

// Original recursive function
int F(int n) {
    { // Block 0 - initial setup and base cases
        if (n <= 0) return 0;
        if (n == 1) return 1;
    }

    int x;
    { // Block 1 - first recursive call (n-3)
        x = F(n - 3);
    }

    int y;
    { // Block 2 - second recursive call (n/2)
        y = F(n / 2);
    }

    int z;
    { // Block 3 - calculation
        z = x * y;
    }

    { // Block 4 - final result
        return n + z;
    }
}

struct ActivationRecord {
    int n;
    int x, y, z; // Local variables
    int block_num; // Current block being executed
    int return_value;

    ActivationRecord(int n) : n(n), block_num(0), x(0), y(0), z(0) {}
};

int G(int n) {
    stack<ActivationRecord> call_stack;
    call_stack.push(ActivationRecord(n));
    int final_result = 0;

    while (!call_stack.empty()) {
        ActivationRecord& ar = call_stack.top();

        switch (ar.block_num) {
            case 0: { // Block 0 - base cases check
                if (ar.n <= 0) {
                    ar.return_value = 0;

                    final_result = ar.return_value;
                    call_stack.pop();
                }
                else if (ar.n == 1) {
                    ar.return_value = 1;
                    final_result = ar.return_value;
                    call_stack.pop();
                }
                else {
                    ar.block_num = 1; // Move to next block
                }
                break;
            }

            case 1: { // Block 1 - first recursive call (n-3)
                call_stack.push(ActivationRecord(ar.n - 3));
                ar.block_num = 2; // After this returns, go to block 2
                break;
            }

            case 2: { // Block 2 - store x and make second call
                ar.x = final_result; // Result from previous call
                call_stack.push(ActivationRecord(ar.n / 2));
                ar.block_num = 3; // After this returns, go to block 3
                break;
            }

            case 3: { // Block 3 - store y and calculate z
                ar.y = final_result; // Result from previous call
                ar.z = ar.x * ar.y;
                ar.block_num = 4; // Move to final block
                break;
            }

            case 4: { // Block 4 - final calculation
                ar.return_value = ar.n + ar.z;
                final_result = ar.return_value;
                call_stack.pop();
                break;
            }
        }
    }

    return final_result;
}

int main() {
    cout << "Testing recursive F() vs iterative G():" << endl;
    for (int i = 0; i <= 10; i++) {
        cout << "F(" << i << ") = " << F(i) << "  |  G(" << i << ") = " << G(i) << endl;
    }
    return 0;
}