fork download
copy 
  1. #include <iostream>
  2. #include <stack>
  3. using namespace std;
  4.  
  5. struct Call {
  6.     int b;          // Current exponent
  7.     int cur_res;    // Current accumulated result
  8.     int cur_loc;    // Current location in the "function"
  9. };
  10.  
  11. int G(int n, int b) {
  12.     stack<Call> st;
  13.     st.push({ b, 1, 0 });  // Initial call: exponent = b, cur_res = 1, cur_loc = 0
  14.  
  15.     int last_ret_val = 1;
  16.  
  17.     while (!st.empty()) {
  18.         Call& call = st.top();
  19.  
  20.         if (call.cur_loc == 0) {
  21.             if (call.b == 0) {
  22.                 // Base case: return cur_res (which is the final result)
  23.                 last_ret_val = call.cur_res;
  24.                 st.pop();
  25.             }
  26.             else {
  27.                 // Schedule next call: multiply by n and decrement exponent
  28.                 call.cur_loc = 1;
  29.                 st.push({ call.b - 1, call.cur_res * n, 0 });
  30.             }
  31.         }
  32.         else if (call.cur_loc == 1) {
  33.             // The recursive call has completed, and last_ret_val holds the result
  34.             // No further action needed; just pop the call
  35.             st.pop();
  36.         }
  37.     }
  38.  
  39.     return last_ret_val;
  40. }
  41.  
  42. int main() {
  43.     cout << G(2, 3) << endl;  // Output: 8 (2^3 = 8)
  44.     return 0;
  45. }
Success #stdin #stdout 0.01s 5324KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
8
https://ideone.com/NDkKY9
language:
C++ (gcc 8.3)
created:
3 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!