24.2.2. Fibonacci Numbers

Try these first

1. 1.

   Define Fibonacci numbers in your own words.

   Hint

   Think about the starting numbers.

2. 2.

   What is Fibonacci(3)?

   Hint

   Calculate using previous Fibonacci numbers.

3. 3.

   What are the first two Fibonacci numbers?

   • 0
   • 1
   • 1
   • 1
   • 0
   • 0

   Hint

   Remember the starting values.

4. 4.

   True or False: Fibonacci(5) equals Fibonacci(4) plus Fibonacci(3).

   • True
   • False

   Hint

   Think about the definition.

5. 5.

   Using memoization, implement a function to calculate Fibonacci numbers and compare its performance against a naive recursive implementation.

   Hint

   Time each approach and compare.

6. 6.

   Design a dynamic programming solution for calculating Fibonacci numbers and explain why it is efficient.

   Hint

   Explain the fill-up process in your solution.