Fibonacci Numbers in Java - Quiz
Total: 5 questions
1. What is the simplest way to compute the n-th Fibonacci number in Java?
What is the simplest way to compute the n-th Fibonacci number in Java?
The simplest and fastest way is a for loop: keep the two most recent numbers and add them on each iteration, sliding the window forward. It runs in O(n) time and O(1) memory — three variables are enough, no array needed. Recursion is used for clarity, but without memoization it is far too slow.
2. Why is the plain recursive Fibonacci algorithm so slow?
Why is the plain recursive Fibonacci algorithm so slow?
Because the same values are recomputed again and again: the call tree grows exponentially, so the complexity is O(2^n). For example, while computing recursive(5), F(2) is calculated three times and F(1) five times. Around n = 45–50 the program lags noticeably, and at n = 250 it effectively freezes.
3. How far can a long hold Fibonacci numbers, and what should you do next?
How far can a long hold Fibonacci numbers, and what should you do next?
F(92) = 7540113804746346429 is the last term of the sequence that still fits in a long. From F(93) onward the value overflows and becomes incorrect (often negative) with no exception thrown. For larger n use BigInteger, which supports integers of arbitrary length.
4. What is memoization and how does it help the recursive Fibonacci algorithm?
What is memoization and how does it help the recursive Fibonacci algorithm?
Memoization is caching values you have already computed (for example in an array or a HashMap) so they are never recalculated. The exponential slowness is not a property of recursion itself — it comes from repeated computations. With memoization the recursive algorithm also becomes linear, O(n), at the cost of O(n) extra memory.
5. Which is better for computing Fibonacci numbers — a loop or recursion — and why?
Which is better for computing Fibonacci numbers — a loop or recursion — and why?
In production code almost always a for loop: it gives O(n) time and O(1) memory and answers instantly. Plain recursion reads like the formula but runs in O(2^n) and already thinks for several seconds at n = 45. The compromise is recursion with memoization: it keeps the readability and runs in O(n).