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