Recursive fibonacci

Question

I am trying to generate Fibonacci series and provided the code for the same below. When I run this code for smaller values, it outputs correct results. However, when I try and calculate series for a number say '50', it out puts correct results upto the 47th number and result for 48,49 and 50th term are incorrect. I tried using unsigned long int as well but it did not correct the results. Can some please suggest what am I doing wrong here. Thanks.

#include<stdio.h>
unsigned long long int fibr(unsigned long long int);

int main(){
    unsigned long long  int n;
    printf("Enter a number\n");
    scanf("%llu",&n);
    //res=fibr(n);
      while(n>=0){
          printf("%llu\n",fibr(n));
          n--;
           }
     }
unsigned long long int fibr(unsigned long long int n){
     if((n==0)||(n==1))
         return n;
     else return fibr(n-1)+fibr(n-2);
     }

'After the suggestions , I incorporated unsigned long long int. Have modified the code above but now it gives a seg fault. Any hints please. I am not allowed to use any other library except the standards one available. '

You may be able to bump up the size of the integer type you're using a few times, but if you need to compute even larger numbers, you might have to start looking into some kind of arbitrary-precision library. — icktoofay, Sep 17 '11 at 07:09

score 2 · Answer 1 · answered Sep 17 '11 at 07:07

2

Did you try using unsigned long long?

answered Sep 17 '11 at 07:07

Petar Minchev

46,889
11
103
119

@Faizan - This is because the complexity of recursive Fibonacci is `2^n`. You are computing the same values again and again. Either use memoization(saving results) or turn it to iterative version. – Petar Minchev Sep 17 '11 at 07:34
@Faizan - Also remove the `unsigned` from `unsigned long long int n;` (the first line after main method) – Petar Minchev Sep 17 '11 at 07:36

score 1 · Accepted Answer · answered Sep 17 '11 at 07:33

1

Here's the answer to your second question:

I think you had this problem from the beginning:

while(n>=0){

is an infinite loop since n is an unsigned integer. n will go negative due to the decrement. But since it's unsigned, it will wrap around and cause a stack-overflow in your recursion.

Also, your algorithm is probably slowest way to do this. It runs in exponential time. So it will take a very long time to run it when n is big.

A better way is just this:

int n = 48;
return (unsigned long long)(pow(1.6180339887498948,n) * 0.44721359549995794 + 0.5);

This method will run in constant time. :)

answered Sep 17 '11 at 07:33

Mysticial

464,885
45
335
332

Thanks Mystical for pointing this out. This did the job. Also it is slow but a requirement for assignment as now this needs to be divided into threads and timing needs to be calculated. I am sure would have not been able to figure out the n>=0 for unsigned it.. thanks again – f-z-N Sep 17 '11 at 08:19
Also, don't use my answer unless you can figure how/why it works. I'll leave the proof as an exercise. :) – Mysticial Sep 17 '11 at 08:23

score 0 · Answer 3 · edited May 23 '17 at 12:03

0

C data types are limited in size. So if you use int, long or long long, at some point, your result will overflow, due to the fast-growing nature of fibonacci-numbers. To store such big numbers, you'll need some BigInteger implementation. Have a look at “BigInt” in C? for this.

edited May 23 '17 at 12:03

Community

1
1

answered Sep 17 '11 at 07:10

rumpel

7,870
2
38
39

score 0 · Answer 4 · answered Sep 17 '11 at 07:10

0

You get integer overflow. For unsigned int the largest possible value is 4294967295, but 48th Fibonacci number is 4807526976.

answered Sep 17 '11 at 07:10

Nikolay Polivanov

657
4
11

score 0 · Answer 5 · answered Sep 17 '11 at 08:11

0

Converting fibr() to memoize its results reduces the running time for fibr(90) to a few milliseconds on my machine. Switching from recursion to iteration should have similar results.

answered Sep 17 '11 at 08:11

Caleb

124,013
19
183
272

Recursive fibonacci

5 Answers5