#python #programming #question #fibonacci #intermediate #algorithm

Write a Python program that implements three different methods to generate the Fibonacci sequence up to the nth term:

1. Use an iterative approach with a loop.
2. Use recursion with memoization.
3. Use dynamic programming with a list.

For each method, calculate the 20th Fibonacci number and measure the execution time. Print the results for each method along with their respective times.

import time

def fibonacci_iterative(n):
    if n <= 1:
        return n
    a, b = 0, 1
    for i in range(2, n + 1):
        a, b = b, a + b
    return b

def fibonacci_recursive_memo(n, memo={}):
    if n in memo:
        return memo[n]
    if n <= 1:
        return n
    memo[n] = fibonacci_recursive_memo(n - 1, memo) + fibonacci_recursive_memo(n - 2, memo)
    return memo[n]

def fibonacci_dp(n):
    if n <= 1:
        return n
    dp = [0] * (n + 1)
    dp[1] = 1
    for i in range(2, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]
    return dp[n]

# Test all three methods for the 20th Fibonacci number
n = 20

# Method 1: Iterative
start_time = time.time()
result_iter = fibonacci_iterative(n)
iter_time = time.time() - start_time

# Method 2: Recursive with memoization
start_time = time.time()
result_rec = fibonacci_recursive_memo(n)
rec_time = time.time() - start_time

# Method 3: Dynamic Programming
start_time = time.time()
result_dp = fibonacci_dp(n)
dp_time = time.time() - start_time

print(f"20th Fibonacci number using iterative method: {result_iter} (Time: {iter_time:.6f} seconds)")
print(f"20th Fibonacci number using recursive method: {result_rec} (Time: {rec_time:.6f} seconds)")
print(f"20th Fibonacci number using DP method: {result_dp} (Time: {dp_time:.6f} seconds)")

By: @DataScienceQ 🚀