fork download
copy 
  1. #include <iostream>
  2. #include <stack>
  3. using namespace std;
  4.  
  5. int fib(int n) {
  6.     if (n == 0) return 0;
  7.     if (n == 1) return 1;
  8.     return fib(n - 1) + fib(n - 2);
  9. }
  10.  
  11. struct Call {
  12.     int n;
  13.     int cur_loc;
  14.     int ret_val;  // To store the return value of this call
  15. };
  16.  
  17. int G(int n) {
  18.     Call initial_call;
  19.     initial_call.n = n;
  20.     initial_call.cur_loc = 0;
  21.     initial_call.ret_val = 0;
  22.  
  23.     stack<Call> st;
  24.     st.push(initial_call);
  25.  
  26.     int last_ret_val = 0;
  27.  
  28.     while (!st.empty()) {
  29.         Call& call = st.top();
  30.  
  31.         if (call.cur_loc == 0) {
  32.             if (call.n <= 1) {
  33.                 last_ret_val = call.n;
  34.                 st.pop();
  35.             }
  36.             else {
  37.                 // Schedule fib(n-1) first
  38.                 call.cur_loc = 1;
  39.                 Call new_call;
  40.                 new_call.n = call.n - 1;
  41.                 new_call.cur_loc = 0;
  42.                 new_call.ret_val = 0;
  43.                 st.push(new_call);
  44.             }
  45.         }
  46.         else if (call.cur_loc == 1) {
  47.             // fib(n-1) has completed, store its result
  48.             call.ret_val = last_ret_val;
  49.  
  50.             // Schedule fib(n-2)
  51.             call.cur_loc = 2;
  52.             Call new_call;
  53.             new_call.n = call.n - 2;
  54.             new_call.cur_loc = 0;
  55.             new_call.ret_val = 0;
  56.             st.push(new_call);
  57.         }
  58.         else if (call.cur_loc == 2) {
  59.             // fib(n-2) has completed, add it to previous result
  60.             call.ret_val += last_ret_val;
  61.             last_ret_val = call.ret_val;
  62.             st.pop();
  63.         }
  64.     }
  65.     return last_ret_val;
  66. }
  67.  
  68. int main() {
  69.     for (int i = 0; i < 7; i++) {
  70.         cout << G(i) << " ";
  71.     }
  72.     cout << endl;
  73.     return 0;
  74. }
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0 1 1 2 3 5 8
https://ideone.com/OQZekQ
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!