Recursive Fibonacci Sequence

Question

So I wrote a recursive program that asks the user now many Fibonacci numbers they would like to execute. The problem I'm having is that after the 45th number, it gives me a number with a "-" and its a number that doesn't fit into the sequence. How can I change that to give me the proper number? Here is the recursive part of the code that executes the calculation:

void fibonacci (int a, int b, int n, int count)
{
    if(n < count) 
    {
        cout<<a+b<<endl;
        fibonacci(b, a+b, n+1, count);
    }
}

here's the output of the sequence:

How many numbers do you want the Fibonacci sequence to process: 50
The starting numbers for the sequence are: 0, 1
1
2
3
5
8
13
21
34
55
89
144
233
377
610
987
1597
2584
4181
6765
10946
17711
28657
46368
75025
121393
196418
317811
514229
832040
1346269
2178309
3524578
5702887
9227465
14930352
24157817
39088169
63245986
102334155
165580141
267914296
433494437
701408733
1134903170
1836311903
-1323752223
512559680
-811192543
-298632863
-1109825406

What changes do I need to make in order for it to change the -#'s to the real numbers?

score 9 · Answer 1 · edited May 23 '17 at 11:55

9

You're running into problems because the datatype int you're using is 32 bits and can only hold values up to 2^31-1 = 2147483647 when signed (default, 31 bits used, 1 bit is occupied to indicate signedness, this also explains the negative numbers), 2^32-1 = 4294967295 when unsigned. You can use a 64 bit datatype here (long long in most cases), but will also run in problems with this one later (around the 94th fibonacci number, I think).

The "real" solution to this problem is to write your own methods for numerical calculations and use an own representation of the numbers, f.e. an array of chars. You can also look for one of the various possibilites to use a "bignum" library. You should find more information about this in some SO questions, for example this one.

edited May 23 '17 at 11:55

Community

1
1

answered Mar 31 '11 at 17:07

schnaader

49,103
10
104
136

4

Also, it's preferable to use `unsigned` types for things that can't be negativ. – Xeo Mar 31 '11 at 17:08
Btw, consider adding the exact cause of the negative representation to your answer, that makes it more complete. – Xeo Mar 31 '11 at 17:15
@Xeo Not according to most experts. Unsigned is generally understood to mean that bit manipulations or modula arithmetic are required. – James Kanze Mar 31 '11 at 17:18
You can also use double precision floating point(which is type double). This type can support a huge number(250 0s or greater I think). Plus for large integer, use 2.0E10, not 2E10. 2.0E10 will make it exactly 2 with 10 zeros. – rauprog Aug 11 '18 at 02:37

score 1 · Answer 2 · answered Mar 31 '11 at 17:11

1

declaring your variable as unsigned int will allow you to do a bit more interactions, but you'll run into problems anyway. Extending the size of your variable, using a long long int will still delay your problem. You can't solve this because, sooner or later, you will exceed the maximum number you can represent, whatever data-type you'll choose

answered Mar 31 '11 at 17:11

BlackBear

22,411
10
48
86

Or you'll run out of memory. Some implementations of BigInt will allow "infinite" precision, but in the end, "infinite" is never larger than the amount of available memory. – James Kanze Mar 31 '11 at 17:19

score 0 · Answer 3 · answered Aug 11 '18 at 07:31

Use double type because int type will quickly overflow for modestly large fibonacci numbers to compute. Large numbers should use exponential notation found in double floating point.

Since you are using the previous numbers shifted up one for each next loop iteration, it makes sense for a recursive call to use fibonacci(a, a+b, n+1, count) instead of fibonacci(b,a+b,n+1, count). I wrote my own recursive function that is less recursive which will illustrate why to use the different recursive call to make the logic clearer.

The recursive function I wrote shows how quickly non -floating point numbers overflow in fibonacci numbers.

// ConsoleApplication1.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <iostream>
#include <conio.h>
using std::cout;
using std::endl;

int fibonacci(double n, int count) {
    char ch;
    static double lastnminus1, lastnminus2;
    if (n == 1) {
     lastnminus1 = 1;
     lastnminus2 = 0;
    }
    cout << lastnminus1 + lastnminus2 << endl;
    double temp = lastnminus1;
    lastnminus1 = lastnminus1 + lastnminus2;
    lastnminus2 = temp;
    if (static_cast<int>(n) % 24 == 0) { 
        cout << "press a key" << endl;
        ch = getch();
    }
    if ( n < count)
        fibonacci(n+1,count);

    return 0;
}

int main()
{
    fibonacci(1,200);
    return 0;
}

score 0 · Answer 4 · answered Mar 31 '11 at 17:10

0

Ints only hold 32 bits of data, for a maximum value of 2,147,483,647. Your return values are "overflowing". Use the ulong data type, which holds 64 bits and has a max value of 18,446,744,073,709,551,615.

answered Mar 31 '11 at 17:10

Joe Abrams

1,124
11
16

Recursive Fibonacci Sequence

4 Answers4