Prasanna Raman

Ranch Hand

Posts: 410

posted 3 years ago

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?

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?

posted 3 years ago

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

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

Is it fast? Is it small? Is it simple?

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.

Prasanna Raman

Ranch Hand

Posts: 410

Ulf Dittmer

Rancher

Posts: 42972

73

posted 3 years ago

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

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

posted 3 years ago

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.

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

Campbell Ritchie

Marshal

Posts: 56520

172

posted 3 years ago

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

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

172

Prasanna Raman

Ranch Hand

Posts: 410

posted 3 years ago

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?

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?

posted 3 years ago

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:

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

posted 3 years ago

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

posted 3 years ago

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:

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

Prasanna Raman

Ranch Hand

Posts: 410

posted 3 years ago

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

posted 3 years ago

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

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

172

posted 3 years ago

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.

Did you see how Paul cut 87% off of his electric heat bill with 82 watts of micro heaters? |