Recall & Review
beginner
What is the base case in a recursive Fibonacci function?
The base case returns the first two Fibonacci numbers directly, usually when n is 0 or 1, to stop the recursion.
Click to reveal answer
beginner
Explain how recursion works in calculating Fibonacci numbers.
Recursion calculates Fibonacci by calling itself with smaller values (n-1 and n-2) and adding their results until it reaches the base case.
Click to reveal answer
intermediate
What is the time complexity of the naive recursive Fibonacci algorithm?
The time complexity is exponential, specifically O(2^n), because it recalculates the same values many times.
Click to reveal answer
beginner
Show the recursive formula used in Fibonacci calculation.
fib(n) = fib(n-1) + fib(n-2) with base cases fib(0) = 0 and fib(1) = 1.
Click to reveal answer
intermediate
Why is recursion not efficient for large Fibonacci numbers without optimization?
Because it repeats calculations for the same inputs many times, leading to a lot of unnecessary work and slow performance.
Click to reveal answer
What does the base case in Fibonacci recursion return for fib(0)?
✗ Incorrect
The base case fib(0) returns 0 to stop further recursive calls.
Which of the following best describes the recursive call in Fibonacci?
✗ Incorrect
The Fibonacci function calls itself twice with n-1 and n-2 to calculate the current number.
What is the main drawback of the naive recursive Fibonacci method?
✗ Incorrect
The naive recursive method has exponential time complexity due to repeated calculations.
What is the output of fib(3) using recursion?
✗ Incorrect
fib(3) = fib(2) + fib(1) = 1 + 1 = 2.
Which technique can improve recursive Fibonacci efficiency?
✗ Incorrect
Memoization stores results of previous calls to avoid repeated calculations.
Describe how the Fibonacci sequence is calculated using recursion, including base cases and recursive calls.
Think about how the function calls itself with smaller numbers until it reaches the simplest cases.
You got /4 concepts.
Explain why the naive recursive Fibonacci algorithm is inefficient and how you might improve it.
Consider what happens when the function calls itself many times with the same inputs.
You got /4 concepts.