fork download
copy 
  1. #include <stdio.h>
  2.  
  3. #include <vector>
  4.  
  5. int fib1(int n) {
  6.   if (n < 2) {
  7.     return n;
  8.   } else {
  9.     return fib1(n - 1) + fib1(n - 2);
  10.   }
  11. }
  12.  
  13. int fib2(int n) {
  14.   std::vector<int> data_stack;
  15.   std::vector<int> call_stack = {0, n};
  16.   int x, t;
  17. L3:
  18.   if (call_stack.back() < 2) {
  19.     data_stack.push_back(call_stack.back());
  20.     call_stack.pop_back();
  21.     switch (call_stack.back()) {
  22.       case 0: goto L0;
  23.       case 1: goto L1;
  24.       case 2: goto L2;
  25.     }
  26.   } else {
  27.     x = call_stack.back();
  28.     call_stack.push_back(1);
  29.     call_stack.push_back(x - 1);
  30.     goto L3;
  31. L1: call_stack.pop_back();
  32.     x = call_stack.back();
  33.     call_stack.push_back(2);
  34.     call_stack.push_back(x - 2);
  35.     goto L3;
  36. L2: call_stack.pop_back();
  37.     int left = data_stack.back();
  38.     data_stack.pop_back();
  39.     int right = data_stack.back();
  40.     data_stack.pop_back();
  41.     data_stack.push_back(left + right);
  42.     call_stack.pop_back();
  43.     switch (call_stack.back()) {
  44.       case 0: goto L0;
  45.       case 1: goto L1;
  46.       case 2: goto L2;
  47.     }
  48.   }
  49. L0:
  50.   return data_stack.back();
  51. }
  52.  
  53. int main() {
  54.   printf("%d %d\n", fib1(10), fib2(10));
  55.   return 0;
  56. }
Success #stdin #stdout 0s 3460KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
55 55
https://ideone.com/0QXd8O
language:
C++14 (gcc 8.3)
created:
8 years 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!