Compute to find Fib- 43

[DS9596]

How do I write a program to compute run-time of a recursive and non-recursive functions to find the 43rd Fibonacci number?

[ddanbe]

What have you done, besides posting your homework assignment?Show your code to us and pinpoint the errors you have.We will be more than happy to help.

[David W]

Can you start the non-recusive function ... show what you can do ... so we can see what you are missing ... hopefully ... not everything :)

[Schol-R-LEA]

I will also warn you that while the conventional tree-recursive algorithm is much simpler than the iterative algorithm, it is extremely inefficient, being of order O(Fib(n)) in time and O(n) in space. This is because (for example) for fib(5), you have to compute fib(4) and fib(3), which in turn have to compute fib(3) + fib(2), which in turn have to compute fib(2) + fib(1) and fib(1) + fib(0), and then compute fib(2) and fib(1), and so on. The total number of calls to fib() is equal to the fibonacci number of n.

It would take quite a while to compute fib(43) that way, even in C++ - unless you use a trick.

The trick is called memoization, and basically means keeping a record of the computed values so that when you come to a value you have already calculated before, you can just look it up in a table rather than re-computed again. I won't go into the details of it, just that it is easiest to use a vector<int> to do it so that you don't have to worry about the size of the table. You don't need to worry about it, but it is something to at least be aware of.

There is an even faster way to compute fibonacci numbers using matrices, but I'll just tantalize you with that fact for now and leave it to you to learn it on your own (hint: Wikipedia covers it quite nicely).

[ddanbe]

@Schol-R-LEA
I even have another way, it is a snippet here in C# but is easily translated in C++. :)

[rubberman]

Fib(43) is a VERY big number, and will overflow even double precision numbers. Not sure about 64bit integers, but definitely 32bit ones.

As for the recursive vs. non-recursive algorithms, show your work!

FWIW, I was using recursive fib algorithms back in the mid-1980's to balance S&P indexed funds for the Mellon Bank.

[Schol-R-LEA]

rubberman: I thought so too, but then I checked using Python (which has bigints), and it turns out that's not the case. Fibonacci numbers do grow quite rapidly, but not quite that rapidly; fib(43) is around 400 million, which will fit a 32-bit signed value.

memo = dict()
memo[0] = 0
memo[1] = 1

def fib(n):
    global memo

    if n in memo.keys():
        return memo[n]
    else:
        memo[n] = fib(n - 1) + fib(n - 2)
        return memo[n]


fib(43)
print(memo)

I think we were both thinking of factorials, which do grow that quickly - fact(43) is around 6 x 10^52.

def fact(n):
    if n <= 1:
        return 1
    else:
        return n * fact(n - 1)

print(fact(43))

(And yes, I know I've given the game away, but the OP would need to be able to re-write the Python code into C++, and if they could do that they wouldn't be posting such a basic question in the first place.)

[ddanbe]

Int64 can handle all fibs up to fib 93.

[DS9596]

Not right, but something like this?

long Fib(int n)
{ int f1=1, f2=2, fn;
  for (i=43; i<=n; ++i)
     {  fn=f1+f2;
        f2=fn;
        f1=f2;
     }
     return fn;
}

[Schol-R-LEA]

Well, it's a start I guess, but in this case, the 43 should be what you are passing to the function as n, not hard-coded into the function; it should look like this in your call:

value = fib(43);

The initial value of i should probably be 0, since you are counting up to the value of n.

long Fib(int n)
{
    long f1=1, f2=1, fn;

    for (i=0; i<=n; ++i)
    {
        fn=f1+f2;
        f2=fn;
        f1=f2;
    }

    return fn;
}

(I won't offer advice on whether the algorithm is correct overall, just this one piece of the puzzle.)

[DS9596]

Instead of that would something like this work?
I found some stuff from the book that it might be like this not sure:

#include <iostream>
using namespace std;

int fib(int);

int main()
{
    for(int i=0; i<43; ++i)
       cout << fib(i) << " "; 
       cout << endl;

    system("pause");
    return 0;
}

int fib(int n)
{   if (n<=0)
        return 0;
    else if (n==1)
        return 1;
    else 
        return fib(nul)+fib(n-2);  //recursive case
}

[DS9596]

#include <iostream>
using namespace std;

int fib(int);

int main()
{
    for(int i=0; i<43; ++i)
       cout << fib(i) << " "; 
       cout << endl;

    system("pause");
    return 0;
}

int fib(int n)
{   if (n<=0)
        return 0;   // base case
    else if (n==1)
        return 1;   //base case
    else 
        return fib(n-1)+fib(n-2);  //recursive case
}

[Schol-R-LEA]

That should be correct for the recursive version, yes, though you'll want some patience when it runs: you are producing the whole series of fib(0) to fib(43), one at a time, which means that you'll be recomputing the series, uhm... pardon me if I'm not quite awake enough right now to work it all out but it will be a lot of recomputing. If all you need is fib(43), this particular code is overkill, but if you mean to print the whole series in that range, you are good to go.

Oops, I just noticed something: you need to test in the loop to be i <= 43 in order to get 43 inclusive.

You may want to fiddle about with memoizing the results, though, just to see about how much of a speedup you'll get from it. A std::vector<int> variable should be useful for this purpose.

BTW, are you using Bloodshed Dev-C++ as your IDE by any chance? I noticed the system("pause"); line which is why I ask, that particular problem is specific to the old version of Dev-C++ and some early versions of Visual Studio. If you are, you should be aware that this version of Dev-C++ hasn't been updated in ten years, and has been superceded by the Orwell Dev-C++ fork, which is in current development, has an up-to-date version of GCC bundled with it, and AFAICT doesn't have that specific problem. Alternately, you can try Code::Blocks which is a similar IDE to Dev-C++ and also avoids that problem.