Write a recursive definition of the Fibonacci numbers, a sequence of integers, each of which is the sum of the previous two numbers. The first two numbers in the sequence are 0 and 1. Explain why you would not normally use recursion to solve this problem.
What will be an ideal response?
Fib(0) = 0
Fib(1) = 1
Fib(j) = Fib(j-1) + Fib(j-2) for j > 1
You would not normally use recursion to solve this problem because the iterative solution is straightforward and the recursive version is inefficient. Calculating a Fibonacci number less than Fib(j-1) would be calculated at least twice in order to calculate Fib(j). The recalculation of each such number would lead to the further recalculation of other Fibonacci numbers with the accompanying inefficiency.
You might also like to view...
Java uses pass by value for passing parameters on a method call. What does this mean if the parameter is a primitive data type? What does this mean if the parameter is a reference to an object?
What will be an ideal response?
A button can change appearance in all of the following frames EXCEPT ____.
A. Up B. Down C. Hit D. Over
Data validation improves the accuracy of the person entering data into a worksheet
Indicate whether the statement is true or false
Which of the following is not an advantage of using a physical model?
A) Transaction data stores are identified. B) It is easier to create compared with the logical model. C) The sequence of processes is identified. D) Controls are included.