Win a copy of Head First Agile this week in the Agile forum!
  • Post Reply Bookmark Topic Watch Topic
  • New Topic

People say Fibonacci Series using recursion, is in-efficient why?  RSS feed

 
Ranajoy Saha
Ranch Hand
Posts: 105
2
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hi, eveyone

First I would like you'all to check these two codes fro producing the Nth Fibonacci Term.

My code



The output for this code is 5.

This is the code that I see everywhere, whenever I search for Fibonacci Series using recursion.



In the book Thinking Recursively By Eric S. Roberts, it is said that the complexity for this algorithm is O((phi/Golden Ratio)^N), there fore it is an exponential algorithm. Where as, if we write the code for fibonacci series using iteration, then the complexity of the code become O(N), where N depends on the number of terms. But, then I converted that iteration code to recursion and that always depends on the number of terms, so my fibonacci Series method has a linear complexity or is it that my code has violated some properties of recursion? So, my question is, why do people use "return fibonacciSeries(term - 1) + fibonacciSeries(term - 2);" instead of using "return fibonacciSeries(lb, lb+ub, terms-1);".
 
Campbell Ritchie
Marshal
Posts: 55793
164
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Why are you calling the method fibonacciSeries when it doesn't create a series, but a single number? Call it fibonacci. Also what do ub and lb mean? They are confusing abbreviations.

Try the naïve method to calculate fibonacci(5).
A few definitions: there are an infinite number of different Fibonacci series, which are a mapping ℕ₁ ↦ ℤ, so there is no such thing as Fib₀. Define Fib₁ 1 and Fib₂ 1, and you have the common Fibonacci series. Let's try to calculate some Fibonacci numbers:-That first attempt will only get the first two terms, so for input of 1 or 2 that method runs once and for larger inputs it returns the wrong result. Next attempt, without the method to weed out values ≤ 0:-You must ensure that only values ≥ 3 allow the right part of the ?: operator to be used. That is correct because 1 or 2 will go left and 3+ will go right. So far so good. Let's try fib(3). That calls fib(1) and fib(2), so you actually call fib() thrice.
Let's try fib(4); that makes 1 and calls to fib(3)(=3) and fib(2)(=1) make 5.
Now try fib(5) which calls fib(4)(=5) and fib(3)(=3) and that is 8

I think I have made a mistake there somewhere, but you can see that each recursive call has an increasing number of calls below it. Haven't got the time now to work out what my mistake is. Sorry.

Now, number of calls for fib(2) ÷ calls for fib(1) = 1 ÷ 1 = 1;
For fib(3) ÷ for fib(2) = 3 ÷ 1 = 3
For 4 ÷ for 3 = 5 ÷ 3 = 1.6666666…
For 5 ÷ for 4 = 8 ÷ 5 = 1.6.
etc etc.

I think you can get as far as fib(34) before you get arithmetic overflow with an int.

Another version with a counter:-Now you will see that the counts of calls are themselves elements of the same Fibonacci series, and you will see that the ratios between successive counts converge on φ
 
Henry Wong
author
Sheriff
Posts: 23284
125
C++ Chrome Eclipse IDE Firefox Browser Java jQuery Linux VI Editor Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Ranajoy Saha wrote:
In the book Thinking Recursively By Eric S. Roberts, it is said that the complexity for this algorithm is O((phi/Golden Ratio)^N), there fore it is an exponential algorithm. Where as, if we write the code for fibonacci series using iteration, then the complexity of the code become O(N), where N depends on the number of terms. But, then I converted that iteration code to recursion and that always depends on the number of terms, so my fibonacci Series method has a linear complexity or is it that my code has violated some properties of recursion? So, my question is, why do people use "return fibonacciSeries(term - 1) + fibonacciSeries(term - 2);" instead of using "return fibonacciSeries(lb, lb+ub, terms-1);".


I think you kinda hit on the issue. Recursion is inefficient for Fibonacci, based on fact, that it is using the classic fibonacci recursion solution... and since, any iterative solution can be converted to recursion in an efficient manner, the argument can easily be made moot.

As for why the solution is that way, I can only guess that the solution is for learning purposes. And that solution does show it in an elegant way. A fibonacci number is the sum of the two previous numbers, and that solution shows that as an example.

Henry
 
Campbell Ritchie
Marshal
Posts: 55793
164
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Agree with Henry; that inefficient recursive method for calculating Fibonacci numbers is shown for teaching purposes. There is another standard recursive solution which takes three parameters to the method, which I think you have found, and that runs in linear time. There is another solution which uses matrix multiplication and runs in logarithmic time. You will find it in Anne Kaldewaij's book about algorithms, about page 98 or 99.
 
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!