GCC optimization of iterative functions

Question

I have the following code for Fibonacci both for recursive and iterative versions:

#include <stdio.h>

typedef long long INT;

long long recursive (long long i) {
    if (i == 0) return 0;
    if (i == 1) return 1;
    return recursive (i-1) + recursive (i-2);
}


long long iterative (long long i) {
    INT counter = i-1;
    INT fib1 = 0;
    INT fib2 = 0;

    // first iteration
    fib1 = 0;
    fib2 = 1;

    while (counter > 0) {
        INT temp1 = fib1;
        INT temp2 = fib2;
        fib1 = fib2;
        fib2 = temp1 + temp2;

        counter--;
    }

}

int main (int argc, char **argv) {

    printf("Result: %lli\n", iterative(10));

    return 0;
}

I tried compiling it with GCC -O2 optimization to see if recursion would perform better than iteration, but I noticed an interesting occurrence: when compiled with -O2, the iterative function outputs 0 while if it's compiled without the flag, it outputs the proper number.

gcc -O2 fibonacci.c -o fib && ./fib: Result: 0

gcc fibonacci.c -o fib && ./fib: Result: 55

... and that gives you undefined behavior. Turn on those warnings! `-Wall -Wextra -Werror -pedantic -std=c99` (or another standard version) — Mat, Apr 25 '15 at 16:11
Yup, that was it. So why did it work when I compiled without optimization? — Aroll605, Apr 25 '15 at 16:25
That's what undefined behaviour does. Anything can happen. Including a function giving the result that you expect, when the function doesn't actually return anything. — gnasher729, Apr 25 '15 at 20:43
And you are not doing a fair comparison of recursion and iteration. The recursive fibonacci implementation makes n recursive calls recursive (1) when the result is n. — gnasher729, Apr 25 '15 at 20:45

score 0 · Answer 1 · edited May 23 '17 at 12:28

0

Recursion will be slower than iterative or tail recursion version (which usually gets optimized to an iterative version). Examples of both are in this thread:

Fibonacci Computation Time

edited May 23 '17 at 12:28

Community

1
1

answered Apr 25 '15 at 16:47

rcgldr

27,407
3
36
61

score 0 · Answer 2 · answered Apr 25 '15 at 19:59

0

Your iterative loop is also suboptimal, it uses more assignments than needed. This would be enough:

int sum = fib1 + fib2;
fib1 = fib2;
fib2 = sum;

And of course you could assign fib1/fib2 the initial values at the start instead of first initializing to 0 and then assigning.

answered Apr 25 '15 at 19:59

Bjorn Munch

496
2
6

Those are relevant style comments, but obviously the compiler knows that it makes no difference. – Marc Glisse Apr 25 '15 at 20:09

score 0 · Answer 3 · answered Apr 25 '15 at 21:51

You are not return-ing anything from long long iterative (long long i). You should place a return statement at the end of every non-void function, otherwise, you get UB (undefined behaviour).

However, the function may still "return" something. It will "return" whatever ends up in the processor register used to return values from functions, which may be what you were meaning to return, and may be not.

GCC optimization of iterative functions

3 Answers3