Recursion in C only works when printing unrelated things

Question

I've just started learning C, and I decided to work on some of the Euler Problems for practice. The program that isn't working is meant to solve Problem2, which asks to compute the sum of all even Fibonacci numbers below 4,000,000.

What's really weird about this program is that it actually works, but only if I print something during recursion: whenever I try commenting out the printf("bazooka"); line in the recursive function, I get results that seem completely random, and vary between large positive numbers and large negative numbers (eg -882154758 and 770491113) upon successive executions of the same program. On the other hand, if I print something, no matter what, in the recursive function, I get the correct output.

I find this behavior extremely weird and interesting, and I would really like to know what's going on: what really puzzles me is that the outputted number changes even when the program is not altered at all. Also, I don't understand why printing during recursion should have any effect on the integer computations being performed.

This is my main function:

int first = 1; int second = 2; int total = 0;
total = Fibo(first,second, total);
printf("\nthis is my result for Euler 2: ");
printf("%d",total);

And this is my recursive function:

  int Fibo(int first, int second, int total) {
  printf("bazooka");
  if (second < 4000000) {
    int add;
    second = first+second;
    first = second-first;
    if (first%2 == 0) {
      add = first;
    }
      total = add+Fibo(first,second,total);
  }
  return total;
}

Can anybody help me figure this out? I really appreciate your help.

Answer 1

add is not initialized if first is odd. Make sure to initialize the variable in both cases and the bug will go away.

Now, for explaining the observed behavior: using an uninitialized variable can show as a random "value" or it can cause the program to malfunction in other random ways. (The technical term in C-like languages is undefined behavior.) In your case it is likely that the value was a garbage left over from the previous usage of the memory location used for the stack frame of the function, or the previous value of the register. A call to printf can appear to fix things because its implementation happens to use and clear the relevant portion of the memory. Needless to say, this is not something you can depend on.

Note that this kind of bug will be diagnosed by the compiler with the appropriate warning settings, such as -Wall for GCC or Clang.

Answer 2

Well, I cannot relate 100% about that behavior, but for sure when you get numbers like the negative number, is because you are exceeding the max value of the int value:

INT_MIN = -2147483648 
INT_MAX = +2147483647

Change this type to long, or long long if getting the same result.

Here you can check the data type boundaries.