Recursive Fibonacci using dynamic programming Implement a recursive program to find the nth fibonacci term with/without dynamic programming and output the results in a table given here for n, 1.....10 n fib(n) num of calls to fib(n) (without dp) num of calls to fib(n) (with dp)
(was told I got the incorrect output results how would i get the correct output?)
def fibonacci_recursive(n, calls):
if n <= 0:
return 0, calls
elif n == 1:
return 1, calls
calls += 1
fib1, calls = fibonacci_recursive(n - 1, calls)
fib2, calls = fibonacci_recursive(n - 2, calls)
return fib1 + fib2, calls
def fibonacci_dynamic_programming(n):
fib = [0, 1]
calls = [0, 0]
for i in range(2, n + 1):
calls.append(calls[i - 1] + calls[i - 2] + 1)
fib.append(fib[i - 1] + fib[i - 2])
return fib[n], calls[n]
print("n Fibonacci (w/o DP) Calls (w/o DP) Fibonacci (with DP) Calls (with DP)")
print("-- ------------------- --------------- ------------------ --------------")
for n in range(2, 11):
fib_without_dp, calls_without_dp = fibonacci_recursive(n, 0)
fib_with_dp, calls_with_dp = fibonacci_dynamic_programming(n)
print(f"{n:2} {fib_without_dp:21} {calls_without_dp:17} {fib_with_dp:19} {calls_with_dp:15}", end='')
if n == 2:
print()
else:
print()
Trending now
This is a popular solution!
Step by step
Solved in 2 steps with 1 images
