• Post Reply Bookmark Topic Watch Topic
  • New Topic

Fibonacci Number - Recursive  RSS feed

 
Prasanna Raman
Ranch Hand
Posts: 410
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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?

 
Knute Snortum
Sheriff
Posts: 4270
127
Chrome Eclipse IDE Java Postgres Database VI Editor
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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?
  •  
    Prasanna Raman
    Ranch Hand
    Posts: 410
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    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?
     
    Ulf Dittmer
    Rancher
    Posts: 42972
    73
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    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.)
     
    Tim Cooke
    Marshal
    Posts: 4038
    239
    Clojure IntelliJ IDE Java
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    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.
     
    Campbell Ritchie
    Marshal
    Posts: 56520
    172
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    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: 56520
    172
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    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: 410
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    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?
     
    Henry Wong
    author
    Sheriff
    Posts: 23295
    125
    C++ Chrome Eclipse IDE Firefox Browser Java jQuery Linux VI Editor Windows
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    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
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    Thank you, Henry. Is there a way to understand the run time without having to look at the proofs?
     
    Henry Wong
    author
    Sheriff
    Posts: 23295
    125
    C++ Chrome Eclipse IDE Firefox Browser Java jQuery Linux VI Editor Windows
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    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
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    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
    Sheriff
    Posts: 23295
    125
    C++ Chrome Eclipse IDE Firefox Browser Java jQuery Linux VI Editor Windows
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    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
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    Henry, doesn't my recursive version achieve O(n) run time?
     
    Henry Wong
    author
    Sheriff
    Posts: 23295
    125
    C++ Chrome Eclipse IDE Firefox Browser Java jQuery Linux VI Editor Windows
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    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: 410
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    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
    Sheriff
    Posts: 23295
    125
    C++ Chrome Eclipse IDE Firefox Browser Java jQuery Linux VI Editor Windows
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    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
    Sheriff
    Posts: 23295
    125
    C++ Chrome Eclipse IDE Firefox Browser Java jQuery Linux VI Editor Windows
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    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
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    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.
    • Post Reply Bookmark Topic Watch Topic
    • New Topic
    Boost this thread!