But it is aided by tail-call optimization. Suppose you have a function as follows:

   int foo(int x) {
     if (test(x)) return C;
     return evaluate(x) + foo(adjust(x));
   }

I can turn that function into:

   int foo(int x) {
     int accum = C;
     for ( ; !test(x); x = adjust(x)) {
       accum += evaluate(x);
     }
     return accum;
   }

In the case of fibonacci, that equates to:

   int fib(int x) {
     int accum = 1;
     for (; x > 1; x -= 2) {
       accum += fib(x - 1);
     }
     return accum;
   }

We still turned the recursive call (or one of them, at least), into a while loop.

And this idiom is recognized by both gcc and llvm. In fact. llvm has a test that specifically makes sure fib is transformed as thus: https://github.com/llvm-mirror/llvm/blob/30fa583f8430bfc7935...