|
|
F0 = F1 = 1 and Fn = Fn-1 + Fn-2 for n>1.In the discussion on arrays we have recursively built-up a table of the first fifty Fibonacci numbers. But this is not the only form of recursion that Java offers. You can also define recursively methods.
The applet below contains a recursive implementation of computing
Fibonacci numbers. The work is done in the recursive method called
fibonacci.
It has complexity O(2n); the array
implementation had linear complexity.
fibonacci Method
long fibonacci (int n) {
if (n<2) {
return 1;
}
else {
return fibonacci(n-1) + fibonacci(n-2);
}
}
The complete source code
of the applet is also available.