is it possible to obtain recursion value at runtime?

Question

I have a Fibonacci recursion function:

int efib (int num) {     
    if (num == 0){    
        return 0;
    }else if (num == 1){ 
        return 1;
    }else if (num == -1){ 
        return -1;
    }else if (num > 0){  
        return efib(num - 1) +  efib (num - 2);
    }else{    
        return efib (num + 1) + efib(num + 2);
    }
}

I'm trying to find the exact element num where the int value overflows, is it possible to obtain the current recursion value to compare it to the maximum value an int data type can hold?

I know that the max value an int can hold that is included in the Fibonacci sequence is 1836311903.

Integer overflow causes undefined behavior, there's no portable way to detect it or continue after it. — Barmar, Oct 25 '18 at 01:36
You could do your arithmetic using `long` instead of `int`, and detect when the value is higher than `(long)INT_MAX`. — Barmar, Oct 25 '18 at 01:36

chux - Reinstate Monica · Answer 1 · 2018-10-25T01:49:35.073

I'm trying to find the exact element (num) where the int value overflows

To prevent overflow, pass the 2 operands to an OF test function before adding.

It use a "compare it to the most value an int data type can hold".

#include <limits.h>
int is_undefined_add1(int a, int b) {
  return (a < 0) ? (b < INT_MIN - a) : (b > INT_MAX - a);
}

   ....
   // return efib(num - 1) +  efib (num - 2);
   int a = efib(num - 1);
   int b = efib(num - 2);
   if (is_undefined_add1(a, b)) {
     fprintf(stderr, "fib[%d] was about to overflow\n", num);
     exit(EXIT_FAILURE);
   }
   return a + b;

If a wider type (long, long long or intmax_t) is available, simple add via that type and check the sum against the int range. @Barmar

#if LLONG_MAX/2 >= INT_MAX && LLONG_MIN/2 <= INT_MIN
int is_undefined_add1(int a, int b) {
  long long sum = a;
  sum += b;
  return sum < INT_MIN || sum > INT_MAX;
}
#else
  // as above
#endif

is it possible to obtain recursion value at runtime?

1 Answers1