Expected Run
fibonacci(0) → 0 0 OK
fibonacci(1) → 1 1 OK
fibonacci(2) → 1 1 OK
fibonacci(3) → 2 2 OK
fibonacci(4) → 3 3 OK
fibonacci(5) → 5 5 OK
fibonacci(6) → 8 8 OK
fibonacci(7) → 13 13 OK
other tests
OK

How to improve/modify my design, code and any other alternate approaches. please advise

This again: These tests and tasks are pretty poor. Fibonacci is definied here over N0. Thus a test covering the input -1 should exist. And you should test the input first.

1

DevOps for the modern enterprise offers many benefits — increased agility, productivity, and more, but digital transformation isn’t easy, especially if you’re not addressing the right issues. Register for the webinar to dive into the “new normal” for enterprise modern ops.

I agree with ste5an. On the other hand, this is for learning the basics of programming, and the totally correct solution (with checking of everything, with unit test, and so on) is not necessary to understand the principle (of Fibonacci, and of the recursive solution).

What is important in this case is that you should not remember this recursive solution as the right approach. The reason is that it is extremely ineficient. The non-recursive solution is not more difficult here, and it is much more efficient.

The difference equation for the Fibonacci series is: u(n+2) = u(n+1) + u(n) with u(0) = 0, u(1) = 1So: u(n+2) - u(n+1) - u(n) = 0 Taking the z-transforms: z^2[u(z) - u(0) - u(1)/z] - z[u(z) - u(0)] - u(z) = 0 u(z)[z^2 - z - 1] - z^2*u(0) - z*u(1) + z*u(0) = 0Putting u(0) = 0 and u(1) = 1 this becomes: u(z)[z^2 - z - 1] = z z u(z) = ------------- z^2 - z - 1The denominator factorizes to: [z-1/2 -sqrt(5)/2)][z-1/2 +sqrt(5)/2]The trick here is to express u(z)/z in partial fractions: 1 1 u(z)/z = 1/sqrt(5)[ ---------------- - ---------------- ] z-1/2 - sqrt(5)/2 z-1/2 +sqrt(5)/2and so: z z u(z) = 1/sqrt(5)[---------------- - ------------------ ] z-1/2-sqrt(5)/2) z-1/2+sqrt(5)/2Then from table of inverse transforms: z ------- = a^n z - awhere a is constant. Then: z z u(z) = 1/sqrt(5) [-------------------- - --------------------] z - (1/2+sqrt(5)/2) z - (1/2-sqrt(5)/2)Now from the table of inverse transforms: u(n) = 1/sqrt(5)[(1/2+sqrt(5)/2)^n - (1/2-sqrt(5)/2)^n]

When n is a positive integer, then u(n) is also a positive integer. Pretty amazing!
In practice, when computing, you probably won't get a positive integer, but a real number that is very close. To get the positive integer, you need to use a round function. http://www.tutorialspoint.com/java/number_round.htm

As n gets larger, the speed at which you compute fibonacci(n) really rocks over the other approaches, whether recursive or just looping. However, if you want a table of the first N values of fibonacci(n), then just adding the previous two integers and storing it into an array of length N will be faster than using fibonacci(n) for all values of n = 1..N, where n is an integer.

They make absolutely NO difference (in this case) to the execution of the code, if it is easy for you to read with them there, leave them there. That's all that it comes down to, how easy it is to read for YOU.

Yes +1 for what mccarl said - I actually think it's a little better with the extra brackets. You should always prefer clarity and to me the extra with the extra braces is clearer.

Doug

0

Featured Post

The average business loses $13.5M per year to ineffective training (per 1,000 employees). Keep ahead of the competition and combine in-person quality with online cost and flexibility by training with Linux Academy.

Basic understanding on "OO- Object Orientation" is needed for designing a logical solution to solve a problem. Basic OOAD is a prerequisite for a coder to ensure that they follow the basic design of OO. This would help developers to understand the b…

This tutorial explains how to use the VisualVM tool for the Java platform application. This video goes into detail on the Threads, Sampler, and Profiler tabs.