Recursive Finbonacci Optimization

Question

The code below is written to calculate the first 70 Fibonacci Numbers. I have two questions:

1) Why does the program get increasingly slower for each successive value of i? Is it because calling the function with high numbers causes heavy memory footprint.

2) What technique or coding scheme could I use to speed up the programs calculations at run time?

#include <iostream>

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

void main() {
  for (int i = 1; i<70; i++)
    cout << " fib(" << i << ") = " << fib(i) << endl;
}

Answer 1

Here is a simple recursive version which runs in linear time O(N). The trick is to return two values instead of one.

void Fibo(int N, int& F0, int& F1)
{
  if (N == 1) {
    F1= F0= 1;
  }
  else {
    Fibo(N - 1, F0, F1);
    F1= F1 + F0;
    F0= F1 - F0;
  }
}

Answer 2

I want to stress quantitatively a very annoying property of the recursive algorithm.

When you call fib(1), or fib(2), the function returns immediately, so that the number of calls performed is exactly 1 in both cases. We write c(1) = c(2) = 1, where c(n) is the number of calls performed to compute fib(n).

When you call fib(n) with n > 2, you call indirectly fib(n-1) and fib(n-2), for a total number of calls which is 1 + c(n-1) + c(n-2).

So c(n) is defined by the recurrence

c(n) = c(n-1) + c(n-2) + 1,
c(1) = c(2) = 1

The solution is called the Leonardo numbers (https://oeis.org/A001595).

Given the form of the recurrence, you easily see that these numbers exceed the Fibonacci numbers so that its takes more recursive function calls to compute the Nth Fibonacci number than the value of the number itself. And as the Fibonacci numbers grow exponentially, so does the number of calls.

So it's not just "more recursive calls", it is "massively more recursive calls". This makes the method horribly inefficient and impractical for large n.

---

Fortunately, there is a simple way to compute the numbers iteratively by just applying the recurrence (given in other answers).

Also of interest is the direct formula

Fn = φ^n/√5

to be rounded to the nearest integer, where φ is the Golden Ratio.

Answer 3

To speed up the program you need to use the technique of memoisation which is a very fancy way of saying "Do not recalculate just store the answer and use it again when needed".

You are using recursion to calculate the answer and at each step you make calls to function which you have already calculated before thereby increasing the complexity. The complexity of the above program is exponential, however you can reduce it to linear time.

Your code with some minor edits and memoisation :

#include<iostream>
#define NOT_DEFINED -1

using namespace std;

long long memo[1000];

long long fib(int n){
    if(memo[n] != NOT_DEFINED) return memo[n];
    if(n==1 || n==2) return 1;
return memo[n] = fib(n-1)+fib(n-2);
}

int main(){
    for(int i = 0;i < 1000;i++) memo[i] = NOT_DEFINED;
    for(int i=1; i<70; i++)
    cout<<" fib("<<i<<") = "<<fib(i)<<endl;
return 0;
}

Link to solution on ideone : http://ideone.com/jW1VKD

Answer 4

1) Why does the program get increasingly slower for each successive value of i?

It's simply that more recursive calls of the function take up more time to execute.

Is it because calling the function with high numbers causes heavy memory footprint.

No, there's no excessive memory footprint (by means of expensive dynamic memory allocation operations). All memory needed is kept on the stack, which is already pre-allocated for the process.

You might easily run out of available stack memory for slightly bigger numbers though.

2)What technique or coding scheme could I use to speed up the programs calculations at run time?

Recursion is probably not the best approach to that problem. There's a more detailed answer already available here:

Is there a better way (performance) calculate fibonacci than this one?

Answer 5

The main problem with the recursive solution is that it has O(2^N) complexity. E.g. to calculate fib(10) it has to calculate fib(9)+fib(8). To calculate fib(9) it has to calculate f(8) [a second time!] + f(7). To calculate f(8) [for the first sum] it has to ...

The optimal solution is using a simple loop, which has O(N) complexity

unsigned int f(unsigned int n)
{
    unsigned int retVal = 1;

    if (n > 2)
    {
        unsigned int a, b = 1, c = 1;

        for (unsigned int index = 2; index < n; index++)
            a = b, b = c, c = a + b;

        retVal = c;
    }

    return retVal;
}

The [huge] difference is due to not recalculating elements.

You could make a run time optimization by trading off memory - allocate a static vector, and every time the function is called either store previously un-calculated values, or use those already stored values.

That would make both memory and run time calculation O(N) for the largest N used during the program's run time.

Answer 6

In addition to the other answers. It is getting slower and slower because the program needs to "remember" the calculation results.

If you have to use recursion than I would suggest you to look into tail recursion. It reuses the previous stack frame. see Tail recursion in C++

Here is a small example:

#include <iostream>

int tail_fib(int n, int a, int b) {
  if (n == 0) return a;
  if (n == 1) return b;
  return tail_fib(n - 1, b, a + b);
}

void main() {
  for (int i = 1; i < 45; i++)
    cout << " fib(" << i << ") = " << tail_fib(i, 0, 1) << endl;        
}

Answer 7

Recursive Fibonacci calculation has an exponential complexity, so it becames slow very fast. You can read analysis here

To calculate Fibonacci faster don't even think of using recursion! Use just plain cycle, like this:

#include <iostream>
#include <cassert>
#include <stdint.h>

uint64_t fib(uint64_t n)
{
    assert(n>0);
    uint64_t fprev = 1;
    uint64_t fprev2 = 0;
    while (--n>0)
    {
        uint64_t t = fprev2;
        fprev2 = fprev;
        fprev += t;

    }
    return fprev;
};

int main(int, char**)
{
    for(uint64_t i=1; i<70; i++)
    std::cout<<" fib("<<i<<") = "<<fib(i)<<std::endl;
    return 0;
}

If you need calculate it even faster, you could precalculate them at program start and save to table for further use.

Also, Fibonacci sequence grows very fast (also like exponential function) so beware integer overflow.