Anything wrong with this C++ code

Question

Can someone please let me know if the following code has something wrong with it ... In a question I was asked if anything is wrong with the following fibonacci number function.

int fib(int n)
{
  if (n <= 1) return n;
  return fib (n-1) + fib(n-2);
}

where n is 0 ... 100

So my answer was nothing as I cannot see anything obvious. The syntax seems fine and logically this is calculating a fibonacci number. Am I correct in making this assumption ?

Answer 1

It depend on what kind of problems you are asking about. I see two problems here:

• Recursion. There is no reason for it. Just use iteration.
• Range overflow. int type cant hold all Fibonacci numbers in range [0, 100]

This is an example of fib implementation using iteration in Python(just because it can hold fib(100) out of box):

In [16]: def fib(n):
   ....:     curr, next = 0, 1
   ....:     for x in range(n):
   ....:         curr, next = next, curr
   ....:         next += curr
   ....:     return curr
   ....: 

In [17]: fib(100)
Out[17]: 354224848179261915075L

Answer 2

Sorry if the answer is too late, but you should also study the complexity of this function to understand better why it doesn't work fine.

Since for every appeal of the function you call fib(n-1) and fib(n-2) , the number of operations performed by fib(n) will be around 2^n. Check the following program which counts how many times fib() is called:

#include <iostream>
using namespace std;

int cnt = 0;

int fib(int n) {
    cnt++;
    if (n <= 1) return n;
    return fib(n - 1) + fib(n - 2);
}

int main() {
    cout << fib(15) << '\n';
    cout << cnt << '\n';
}

So, if you want to call fib(100), it will perform about 10^18 operations, and assuming that your computer is fast enought to make 10^9 operations in 1 second, it will take like 33 years to finish this.

But this will cause a stack overflow error earlier.

It is true that fib(100) will have more than 19 digits, which is (aprox.) the max value that long long can hold, but this is not the main reason why your function is "sticky".

A good (and maybe the best) alternative here would be to do as @soon said above, using an iterative function / algorithm that have linear complexity (your function is exponential, read more here).

Here's a code of fibonacci function implemented using big numbers in C++ (there's more C actually, but, anyways):

#include <iostream>
using namespace std;

const int maxsize = 10000; // number of digits
int n;

// note that the digits are keep reversed in the vector
// the bigsum function is as you would use add in math
// a = a + b
void bigsum(int a[], int b[]) { // in a[0] I hold the number of digits of 'a'
    int i, t = 0;
    for (i = 1; i <= a[0] || i <= b[0] || t; ++i) { // while you still have digits to add
        t = t + a[i] + b[i]; 
        a[i] = t % 10;
        t /= 10;
    }
    a[0] = i - 1; // the new a[0]
}

int zero[maxsize];

// a = b
void copy(int a[], int b[]) {
    for (int i = 0; i <= b[0]; ++i) {
        a[i] = b[i];
    }
}

void fib(int n) {
    if (n < 0) {
        cout << "NA";
    } else if (n == 0) {
        cout << 0;
    } else if (n == 1 || n == 2) {
        cout << 1;
    } else if (n == 3) {
        cout << 2;
    } else {
        int first[maxsize], second[maxsize], third[maxsize];
        copy(first, zero); copy(second, zero); copy(third, zero);
        first[0] = first[1] = second[0] = second[1] = 1; // initializing the numbers with 1
        third[0] = 1; third[1] = 2; // initializing with 2

        for (int i = 4; i <= n; ++i) {
            copy(first, second);
            copy(second, third); // if you don't understand why these 3, try to do it on a paper
            bigsum(third, first);
        }

        for (int i = third[0]; i >= 1; --i) { // because the digits are reversed
            cout << third[i];
        }
    }
    cout << '\n';
}

int main() {
    cin >> n;
    fib(n);
}

Now the fib function works for higher numbers (10000 digits, just change the maxsize value if you want higher) and the total number of operations is n * NUMBER_OF_DIGITS, which is around n^2 (way smaller than 2^n).

Another very nice solution would be using a 2x2 matrix, which allows you to calculate the remainder fib(n) % SOME_NUMBER in aprox. log2(n) operations (you can use "exponentiation by squaring", see this). Read more about the matrix solution here.

In conclusion, your program isn't good because it runs in exponential complexity and also it uses too much stack memory (even if it returns the correct value).

Hope you understand now the issues of your function. Sorry again if this post shouldn't be here.

All the best!