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?

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".

So I would worry less about "acceptable" and more about:

All things are lawful, but not all things are profitable.

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.)

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.

Tim Driven Development

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, 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?

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 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 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 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

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

What you posted is indeed linear complexity, but the exponential complexity version does not run inPrasanna 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).

**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. |