CODEWITHSUNDEEP
c
Foreastbtch
Foreastbtch

Reputation: 45

Fibonacci recursive

I'm trying to generate the x Fibonacci number. I made a float function and I can't find why it's not working. However, with an int function, it's working.

#include <stdio.h>

float fib(float x) {
  if (!x)
    return 0;
  else if (x == 1)
    return 1;
  else
    return fib(x - 2) + fib(x - 1);
}

int main() {
  float x, y;
  printf("x= ");
  scanf("%7.2f", &x);
  y = fib(x);
  printf("%7.2f", y);
  return 0;
}

error message:

Unhandled exception at 0x002C50D9 in Fibonacci.exe: 0xC00000FD: Stack overflow (parameters: 0x00000001, 0x00122F44).

Upvotes: 2

Views: 138

Answers (2)

chqrlie
chqrlie

Reputation: 144740

This recursive float version should use approximately the same stack space as the int version: proportional to the argument version.

There are multiple problems here:

  • the scanf conversion format "%7.2f" is incorrect: the .2 is meaningless and causes the conversion to fail. The 7 means at most 7 bytes should be read and converted as a float, probably not what you meant. You do not test the return value of scanf() so you don't realise that x stays uninitialized, so the code has undefined behavior anyway, but x is quite unlikely to be an integer. Use %f and check that scanf() returns 1.

  • if you give an argument that is too large, the function will recurse too deep and produce a stack overflow.

  • if the argument is not an integer or negative, the termination tests will not stop the recursion: if (!x) return 0; if (x == 1) return 1;. If the initial argument is not an integer, subtracting 1 or 2 will keep producing numbers that are not integers and the tests will fail to stop the recursion as x passes into the negatives.

In both cases, the recursion continues and soon the stack space is exhausted anywhere between 100000 calls and a few million. Your CPU can perform hundreds of millions of calls per second so the stack overflow occurs almost immediately.

For other arguments, given the exponential nature of this recursion you are more likely to lose patience over execution time than to experience a stack overflow.

Here is a modified version:

#include <math.h>
#include <stdio.h>

float fib(float x) {
    if (x > 200)
        return INFINITY;
    if (x <= 2)
        return 1;
    return fib(x - 2) + fib(x - 1);
}

int main() {
    float x, y;
    printf("x= ");
    if (scanf("%f", &x) == 1) {
        y = fib(x);
        printf("%7.2f\n", y);
    } else {
        printf("invalid input\n");
    }
    return 0;
}

Upvotes: 3

Maf
Maf

Reputation: 725

You are using a wrong scanf format. 

int main() {
  float x, y;
  printf("x= ");
  scanf("%f", &x); //Your mistake was here!
  y = fib(x);
  printf("%7.2f", y);
  return 0;
}

Upvotes: 1

Related Questions