public int fibonacci(int n) {
if ((n == 0) || (n == 1)) // base cases
return n;
else
// recursion step
return fibonacci(n - 1) + fibonacci(n - 2);
}
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
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+8public int fibonacci(int n) {
if ( n == 0 || n == 1) // base cases
return n;
else
// recursion step
return fibonacci(n - 1) + fibonacci(n - 2);
}
If you are experiencing a similar issue, please ask a related question
Title | # Comments | Views | Activity |
---|---|---|---|
JUnit 4 @Before and @BeforeClass differences | 3 | 48 | |
Why method in Java which is called from Runnable run() doesn't need to be 'static'? | 1 | 22 | |
servlet URL Rewriting | 1 | 27 | |
Is doing tutor.com teaching in my situation advisable? | 2 | 54 |
Join the community of 500,000 technology professionals and ask your questions.
Connect with top rated Experts
16 Experts available now in Live!