Fibonacci Function with memoization in C++

I was trying to make a Fibonacci Function with memoization in C++. I opted for the following approach.

#include <iostream>
using namespace std;


int fibonacci(int index = 0) // Recursive // SwitchCase
{
    switch (index)
    {
    case 0:
        return 0;
    case 1:
        return 1;
    default:
        return fibonacci(index - 2) + fibonacci(index - 1);
    }
}

int fibo(int i) // Recursive & Memoisation
{
    static int const maxIndex = 2000;
    static int seq[maxIndex] = {0, 1};
    static int count = 2;
    if(i < count){return seq[i];}
    int temp = fibo(i-2) + fibo(i-1);
    count = count + 1;
    seq[i] = temp;
    return temp;
}

int main()
{
    int n = 50;
    for (int i=0; i<=n; i++)
    {cout << i << ":\t:" << fibo(i) << endl;} // Memoization
    cout << "\n\n" << endl;
    for (int i=0; i<=n; i++)
    {cout << i << ":\t:" << fibonacci(i) << endl;} // Non Memoization
    return 0;
}

I noticed something weird from index 47. The output is as following:

0:      :0  
1:      :1  
2:      :1  
3:      :2  
4:      :3  
5:      :5  
6:      :8  
7:      :13 
8:      :21 
9:      :34 
10:     :55 
11:     :89 
12:     :144
13:     :233
14:     :377
15:     :610
16:     :987
17:     :1597
18:     :2584
19:     :4181
20:     :6765
21:     :10946
22:     :17711
23:     :28657
24:     :46368
25:     :75025
26:     :121393
27:     :196418
28:     :317811
29:     :514229
30:     :832040
31:     :1346269
32:     :2178309
33:     :3524578
34:     :5702887
35:     :9227465
36:     :14930352
37:     :24157817
38:     :39088169
39:     :63245986
40:     :102334155
41:     :165580141
42:     :267914296
43:     :433494437
44:     :701408733
45:     :1134903170
46:     :1836311903
47:     :-1323752223 // <--
48:     :512559680   // <--
49:     :-811192543  // <--
50:     :-298632863  // <--


0:      :0
1:      :1
2:      :1
3:      :2
4:      :3
5:      :5
6:      :8
7:      :13
8:      :21
9:      :34
10:     :55
11:     :89
12:     :144
13:     :233
14:     :377
15:     :610
16:     :987
17:     :1597
18:     :2584
19:     :4181
20:     :6765
21:     :10946
22:     :17711
23:     :28657
24:     :46368
25:     :75025
26:     :121393
27:     :196418
28:     :317811
29:     :514229
30:     :832040
31:     :1346269
32:     :2178309
33:     :3524578
34:     :5702887
35:     :9227465
36:     :14930352
37:     :24157817
38:     :39088169
39:     :63245986
40:     :102334155
41:     :165580141
42:     :267914296
43:     :433494437
44:     :701408733
45:     :1134903170
46:     :1836311903
47:     :-1323752223 // <--
48:     :512559680   // <--
49:     :-811192543  // <--
50:     :-298632863  // <--

P.S. I did the non memoization approach just to check if there is something wrong with the array part.

I don't understand why the output contains negative integers. I tried using double instead of int too but the output still had negative numbers.

Can anyone please explain why this happens? Thanks in advance

Solution

So basically int has a limit values and the range is from -2147483647 up to 2147483647.

If you want to write longer numbers you should consider using:

unsigned int: With max value 4294967295 only positive
long long: With max value 9223372036854775807
unsigned long long: With max value 18446744073709551615 only positive

There is one more solution:

You can divide very long number at few ints and then output them in one line.