fibonacci

I use this (C++) function to calculate member n of the fibonacci series:

Code:

---

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

---

This is my VB translation (for those who don't know C++)

Code:

---

public function fib (n as long) as long
  if(n = 0 or n = 1) then
    fib = 1
  end if
  fib = fib (n - 1) + fib (n-2)
end function

---

I hope I got that right.

Now, I want to know how often this recursive function is called for any number n. Can anyone tell me how to calculate this please?

Thx in advance

Hello,

There's an error in your VB translation of the C fragment. You should exit the function in case n = 0 or n = 1. If you don't, then also for n = 0 or n = 1 the fib function is called recursively, which will result in an infinite number of calls.

At first sight I would say that the fib function is called recursively 2^(n-1) times for every n. The actual value will be lower, since one of the calls is fib(n-2), but it will be more than the half of those times. So, the number of calls lies roughly between 2^(n-2) and 2^(n-1).
I'll put Excel to work for a more precise answer :)

also check Binnet's formula to find the nth fib number - it is faster for large n.

search on google or post if you can't find it.

thanks. It is Binet's formula btw.

But I really want to know the number of calls to my function since I managed to make a Athlon 600 crazy with it...

You could increment a public variable inside the Fib function...?

yes, I could, but then I had to run the program with the function, and since this takes >5 minutes sometimes I don't want to...

I made up an application to test this recursion.

The following code worked

Code:

---

Public Function Fibonacci(Number As Long) As Long

FibonacciTally = FibonacciTally + 1

If Number = 0 Then
        Fibonacci = 1
    ElseIf Number = 1 Then
        Fibonacci = 1
    Else
        Fibonacci = Fibonacci(Number - 1) + Fibonacci(Number - 2)
  End If
 
End Function

---

My 1000Mhz AMD Athlon did computations for N = 30 in what seemed like 1/10 second or less. When I tried 35, the program hung and I terminated the application. Perhaps it might have gotten an answer if I waited longer, but I think it ran into stack overflow, not enough memory, arithmetic overflow, or some other problem. Perhaps I should have used Doubles instead of Longs.

FibonacciTally seemed to always be twice the Fibonacci number minus one.

I got the following results.

BTW, the numbering seems a bit strange.

Fibonacci( 0 ) = 1 --- Tally = 1
Fibonacci( 1 ) = 1 --- Tally = 1
Fibonacci( 2 ) = 2 --- Tally = 3
Fibonacci( 3 ) = 3 --- Tally = 5
Fibonacci( 4 ) = 5 --- Tally = 9
Fibonacci( 5 ) = 8 --- Tally = 15
Fibonacci( 6 ) = 13 -- Tally = 25
Fibonacci( 7 ) = 21 -- Tally = 41

I think it was a stack overflow, so you should NOT use doubles, as they take 8 bytes instead of 4...
But thanks anyways, I'll do that, although it's not exactly what I wanted.

Quote:

---

think it was a stack overflow, so you should NOT use doubles, as they take 8 bytes instead of 4...

---

Stack overflow : the reason why I avoid programming recursive functions.

Same here, you should always try an iterative solution, unless it violates the protection of an interface

I agree - you've got extremely terse, tight code and an alogrithm that crashes memory. Unless it's for school project, code like that should never go into production.

Why not ITERATE FORWARD, like Kedaman suggested?
It won't crash, except possibly if you overflow an unsigned _int64 or whatever. You should consider using unsigned integers, as well.

While waiting for my girl friend earlier today, I had time to mull over this Thread. To me it seems to be an unusual application of recursion.

Almost every recursive algorithm I have previously encountered seemed a bit or very difficult to grok. This was (to me anyway) extremely easy to understand. One look at the code, and I knew the algorithm would result in the correct value.

Next, it is the first recursive algorithm I have seen for which alternative methods would not require an array (or deep stack) to hold the variables maintained by the recursive logic.

Finally, from a practical point of view, it is a worst case use of recursion. The recursive algorithm requires a stack containing potentially millions of variables. A non recursive implementation only requires remembering the current and the previous term plus a counter.

For many applications, recursion is not such a bad idea. The best example I can think of is the Quick Sort algorithm. If implemented properly, you would run out of time way before you would overflow memory or have stack overflow. The recursion overhead for Quick Sort is small compared to the overall requirements of the application. The recursion overhead is not likely to be much (if any) more time consuming than the overhead for maintaining the array required for a non recursive implementation.

You are getting wrong the first terms of the series. The correct one is:

0, 1, 1, 2, 3, 5, 8, 13 ...

Hence, F(0)=0, F(1)=1
and F(n)=F(n-1)+F(n-2)

I'd also want to know how to fight recursive function stack overflow.

Joe Back

For heaven's sake, would you care to look at the DATE of a thread before replying? This thread is 5 years old! Since then, I've developed from a clueless little kid into an encyclopedia of weird information about C++.

The only way to fight stack overflow in recursion is to avoid recursion.

Sorry Cornedbee. In fact, I didn't notice the date. However, I'm happy you've become a C++ guru. I might need your advice when I switch from vb to C soon after. I expect you have already mastered and saved dozens of algorithms.


________
The most important thing is not what you know, but whom you know!
(from Alice in Wonderland)

Cheers...