ECCE$4257$

Lab$1$

$2-$ Write a function fibonacci$\_$recursive$($n$)$ that calculates the nth Fibonacci number using recursion. Then, write another function, fibonacci$\_$iterative$($n$),$ that calculates the nth Fibonacci number using an iterative loop.

a$-$ Verify the correctness of your implementations by calculating the first $10$ Fibonacci numbers with both functions and comparing their outputs.

b$-$ Measure the execution time of both your recursive and iterative functions for increasing values of $n=10$ and increase $n$ by $10$ until you reach $n=40$

c$-$ Summarize the key differences between the recursive and iterative approaches to computing Fibonacci numbers in terms of their efficiency.

Use the following starter

import time

for $n$ in range $(10,41,10)$ :

start$\_$time $=$ time.time $()$

fibonacci recursive$($n$)$

print$(f^{\text{'}}$ Recursive for $n=\{n\}$ : $\{$time$.$time$()-$start$\_$time:. $\{$:$5f\}$ seconds"$)$

start time $=$ time.time $($

fibonacci iterative$($n$)$

print$(f^{\text{'}\text{'}}$ Iterative for $n=\{n\}$ : $\{$time$.$time$()-$ start$\_$time: $\{$:$5f\}$ seconds"$)$