Extension 6.4: Fibonacci Recursively and Iteratively (3 points)¶
The Fibonacci Sequence is an interesting pattern of numbers that occurs in a lot of unusual places. The first number in the sequence is 0, the second number is 1, the third is also 1, the fourth is 2, the fifth is 3, the sixth is 5, ….
Each new number in this sequence is just the sum of the previous two numbers. This can be expressed via a recursive equation, like:
Since this formula is recursive, it can easily be represented in recursive computer code.
In this extension, you will compare the running time of that recursive formulation with an iterative formulation of the same function.
You should see a
fibonacci package in the
src folder. You will modify
Fibonacci.java. They are both already in the respository.
Note: You should assume that StdDraw’s x and y scales are configured to allow the index of the array to map to the x-coordinate and the value at that index to be the y-coordinate.
Graphas a Java Application.
You will complete two methods in the
iterative(n). You will complete
Fibonacciso that it returns the n th fibonacci number using recursion. (You can base it on the recursive equation provided above.)
FibonacciTestSuiteuntil you have passed all of the recursive portion.
- Complete the
Fibonacciso that it computes the same function, but iteratively.
As a hint, you will need two variables that represent the (n-1) :sup:th and (n-2) th values of the sequence. Adding those together produces the n :sup:`th`term. The variables’ values are then shifted prior to the next iteration.
- Complete the
FibonacciTestSuiteuntil you have passed all of the tests.
To run the suite of unit tests, right (control) click on
FibonacciTestSuite and choose
Run as... then
FibonacciDebugApp to get timing information on your algorithms.
Press the Graph Timing button to see your
graphLine(ys) method draw the timing data.