The IT Service Excellence Tool Kit has best practices to keep your clients happy and business booming. Inside, you’ll find everything you need to increase client satisfaction and retention, become more competitive, and increase your overall success.

Hi,

I am working on below challenge

http://codingbat.com/prob/p120015

Psedo code:

1. if first two numbers return same

2. else call same fibonacci method by passing n-1 and n-2 and sum it up

I am passing all tests

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

I am working on below challenge

http://codingbat.com/prob/p120015

Psedo code:

1. if first two numbers return same

2. else call same fibonacci method by passing n-1 and n-2 and sum it up

```
public int fibonacci(int n) {
if ((n == 0) || (n == 1)) // base cases
return n;
else
// recursion step
return fibonacci(n - 1) + fibonacci(n - 2);
}
```

I am passing all tests

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

Experts Exchange Solution brought to you by

Enjoy your complimentary solution view.

Get this solution by purchasing an Individual license!
Start your 7-day free trial.

I wear a lot of hats...

"The solutions and answers provided on Experts Exchange have been extremely helpful to me over the last few years. I wear a lot of hats - Developer, Database Administrator, Help Desk, etc., so I know a lot of things but not a lot about one thing. Experts Exchange gives me answers from people who do know a lot about one thing, in a easy to use platform." -Todd S.

Experts Exchange Solution brought to you by

Your issues matter to us.

Facing a tech roadblock? Get the help and guidance you need from experienced professionals who care. Ask your question anytime, anywhere, with no hassle.

Start your 7-day free trialWhat is important in this case is that

http://www.maths.surrey.ac.uk/hosted-sites/R.Knott/Fibonacci/fibformproof.html

The way I learned the closed form solution was to take the z-transform of the equation. Here is a link that describes how to do this.

http://mathforum.org/library/drmath/view/51540.html

```
The difference equation for the Fibonacci series is:
u(n+2) = u(n+1) + u(n) with u(0) = 0, u(1) = 1
So:
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) = 0
Putting u(0) = 0 and u(1) = 1 this becomes:
u(z)[z^2 - z - 1] = z
z
u(z) = -------------
z^2 - z - 1
The 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)/2
and so:
z z
u(z) = 1/sqrt(5)[---------------- - ------------------ ]
z-1/2-sqrt(5)/2) z-1/2+sqrt(5)/2
Then from table of inverse transforms:
z
------- = a^n
z - a
where 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]
```

```
u(n) = [(1/2+sqrt(5)/2)^n - (1/2-sqrt(5)/2)^n]/sqrt(5)
```

http://www.wolframalpha.com/input/?i=plot+%5B(1%2F2%2Bsqrt(5)%2F2)%5En+-+(1%2F2-sqrt(5)%2F2)%5En%5D%2Fsqrt(5),+where+n+%3D+1+to+8When 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

http://www.tutorialspoint.com/java/number_round.htm

```
public int fibonacci(int n) {
if ( n == 0 || n == 1) // base cases
return n;
else
// recursion step
return fibonacci(n - 1) + fibonacci(n - 2);
}
```

got rid of extra brackets. when i have to put and when i can get rid of brackets?

Doug

Java

From novice to tech pro — start learning today.

Experts Exchange Solution brought to you by

Enjoy your complimentary solution view.

Get this solution by purchasing an Individual license!
Start your 7-day free trial.