Overview
This lecture covers implementing the Fibonacci function in Python using iterative, recursive, and optimized recursive (with memoization) approaches.
Iterative Fibonacci Implementation
- Define a function that takes an integer n as input and returns the nth Fibonacci number.
- Set initial variables a=0 and b=1 to represent the first two Fibonacci numbers.
- If n equals 1, return 0; if n equals 2 or 3, return 1.
- For n > 3, iterate using a loop: set c = a + b, update a to b, and b to c in each iteration.
- Return the final value after the loop ends.
- Use a for loop to call the function and generate the first 10 Fibonacci numbers.
Recursive Fibonacci Implementation
- Define a recursive function where Fibonacci(n) = Fibonacci(n-1) + Fibonacci(n-2).
- The function calls itself with arguments n-1 and n-2 until it reaches base cases.
- Return the result after summing values from the recursive calls.
Optimizing with Memoization
- Enhance the recursive function by adding a default dictionary parameter to store previously computed results.
- Before calculation, check if the value for the current n exists in the dictionary; if so, return it immediately.
- For n > 3, calculate the value recursively, store it in the dictionary, and return it.
- This reduces redundant calculations and improves efficiency for large n.
Key Terms & Definitions
- Fibonacci Sequence — A series where each number is the sum of the two preceding ones.
- Recursive Function — A function that calls itself to solve smaller parts of the problem.
- Memoization — An optimization technique that stores previously computed results to avoid redundant calculations.
Action Items / Next Steps
- Practice implementing all three versions of the Fibonacci function.
- Test the memoized version on large input values to observe performance improvements.