programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other all forums
this forum made possible by our volunteer staff, including ...
Marshals:
Sheriffs:
Saloon Keepers:
Bartenders:

# Fibonacci Number - Recursive

Ranch Hand
Posts: 422
Hello,

I wrote this tail recursive function that mirrors the iterative version, except that the loop in the iterative version is replaced by an if statement here and then a recursive call. Is this truly recursive? I have seen the fibo(n-1) + fibo(n - 2) version, but is this also an acceptable recursive solution? Why is it never solved this way?

Sheriff
Posts: 4748
133
Yes, it's recursive (well, fiboHelper() is). Yes, it's acceptable (whatever that means). No one's (well, very few) ever done it this way because you are a unique individual.

Now this doesn't mean I might not comment on it. It seems a bit overly complex. But does this complexity make it faster? Have you tried timing the standard fib(n) + fib(n-1) implementation against yours? Does it take less memory? If it's not faster, then is it clearer? Easier to maintain? Normally, the simpler implementation is better because of these last two reasons, and because of something programmers like to call "elegance".

• Is it fast?
• Is it small?
• Is it simple?
•
Prasanna Raman
Ranch Hand
Posts: 422
Thank you, Knute. I haven't timed it, but if I understood it correctly, this is tail recursive, correct? Hence it would take up less memory and run faster?

Rancher
Posts: 42975
76
Since fiboHelper calls itself at each step, yes - it is recursive.

You probably never see this because Fibonacci numbers are used to demonstrate tree recursion, which this version does not. If one wanted to have an efficient algorithm for calculating Fibonacci numbers one wouldn't use recursion at all, since they're easy to calculate iteratively. (Just like factorials are easy to calculate iteratively, but are nonetheless frequently used to demonstrate recursion.)

Marshal
Posts: 4355
280

Prasanna Raman wrote:this is tail recursive, correct? Hence it would take up less memory and run faster?

Whether it is tail recursive or not is kind of irrelevant in this case as Java does not optimise for tail recursion. So even if it were technically tail recursive it would not occupy a constant stack frame as you would expect.

Therefore it will never be as efficient as solving it iteratively as Ulf suggests.

Marshal
Posts: 58436
178
That algorithm will run in linear time, so it will be much more efficient than the tree recursion version. It does look more complicated but that is normal for that version of Fibonacci number programs.
What you do is add a static count field, and add count++; to the fiboHelper method. Then compare it to the common tree recursion version and count how many calls that has. Try fib(30) with both methods, then fib(31). Divide the count for fib(31) with the tree recursion by the count for fib(30).

Campbell Ritchie
Marshal
Posts: 58436
178
If you find Anne Kaldewaaij's book (I think page 98) there is a version of Fibonacci numbers which runs in logarithmic complexity.

Prasanna Raman
Ranch Hand
Posts: 422
Thank you, Campbell, Ulf and Tim.

Campbell, the ratio is 1.6. I checked the running time somewhere and it says 2^n. Why is it so? For 15, it gives me 1219, and for 30 it's 1664079 which are nowhere near 2^n. How should I understand this if there's a way without having to look at the proofs.

Also, can I write this version if someone asks me to write a recursive Fibonacci series in an interview? Is this version as good as the iterative version except that this will take up stack space which the iterative version won't?

author
Marshal
Posts: 23439
138

Prasanna Raman wrote:
Campbell, the ratio is 1.6. I checked the running time somewhere and it says 2^n. Why is it so? For 15, it gives me 1219, and for 30 it's 1664079 which are nowhere near 2^n. How should I understand this if there's a way without having to look at the proofs.

Also, can I write this version if someone asks me to write a recursive Fibonacci series in an interview? Is this version as good as the iterative version except that this will take up stack space which the iterative version won't?

http://en.wikipedia.org/wiki/Big_O_notation

The complexity (order) of an algorithm assumes that N is approaching infinity... so you will need much much much much bigger numbers than 15 and 30...

Also, you can't determine it with two data points. Two data points creates a straight line -- and 2^N is not a straight line.

Henry

Prasanna Raman
Ranch Hand
Posts: 422
Thank you, Henry. Is there a way to understand the run time without having to look at the proofs?

Henry Wong
author
Marshal
Posts: 23439
138

Prasanna Raman wrote:Thank you, Henry. Is there a way to understand the run time without having to look at the proofs?

Considering that ... (1) N has to approach infinity, so the run times should be really really large. (2) You need a lot of data points (way more than two) in order to determine the graph, so that you can determine the formula. And (3) 2^N is a ridiculously growing formula.

I think that it is safe to say that it will be very difficult to run a program to try to figure out the formula. It will likely be quicker to learn the theory (and even get a PhD in mathematics) before you can get a computer to draw out the formula.

Henry

Prasanna Raman
Ranch Hand
Posts: 422
No, I am not trying to deduce the running time by running the program. I am just asking if there's a way to understand it by looking at the code, like we do with some programs.

Henry Wong
author
Marshal
Posts: 23439
138

Prasanna Raman wrote:
Also, can I write this version if someone asks me to write a recursive Fibonacci series in an interview? Is this version as good as the iterative version except that this will take up stack space which the iterative version won't?

Not even close. You can probably take a minute to do it iteratively, and achieve an order of N. And as Campbell already mentioned, there is an algorithm that can achieve an order of Log N... An order of 2^N is pretty bad, and such an algorithm should be avoided, if possible.

Henry

Prasanna Raman
Ranch Hand
Posts: 422
Henry, doesn't my recursive version achieve O(n) run time?

Henry Wong
author
Marshal
Posts: 23439
138

Prasanna Raman wrote:Henry, doesn't my recursive version achieve O(n) run time?

No... As you already mentioned, and as mentioned many times during this topic, it should be O(2^N).

Henry

Prasanna Raman
Ranch Hand
Posts: 422
I agree it's 2^n for the fibo(n-1) + fibo(n-2) version, but for the version I've written in my original post, I thought it was O(n).

Henry Wong
author
Marshal
Posts: 23439
138

Prasanna Raman wrote:No, I am not trying to deduce the running time by running the program. I am just asking if there's a way to understand it by looking at the code, like we do with some programs.

It comes with practice. You can do it with some programs because they are the easier algorithms. With enough practice, stuff that looks hard now, will become easy.

Henry

Henry Wong
author
Marshal
Posts: 23439
138

Prasanna Raman wrote:I agree it's 2^n for the fibo(n-1) + fibo(n-2) version, but for the version I've written in my original post, I thought it was O(n).

Sorry. Jumped into this topic in the middle, and didn't go back to the original post.

Yes, with tail recursion, it is just like a loop -- so, it is as you said. Never mind my previous post regarding this.

Henry

Campbell Ritchie
Marshal
Posts: 58436
178

Prasanna Raman wrote:I agree it's 2^n for the fibo(n-1) + fibo(n-2) version, but for the version I've written in my original post, I thought it was O(n).

What you posted is indeed linear complexity, but the exponential complexity version does not run in O(2ⁿ) time. I have suggested to you how you can work out the argumrnt to the xⁿ bit.

 Don't get me started about those stupid light bulbs.