I am trying to implement a count variable in the function below using dynamic programming specifically memoization. The method calculates the value in a Fibonacci sequence at a given index. I cannot figure out why the count (in this case the number of times this program executes) is not returned.
def fibonacci_memoized(): cached = {} count = [0] def fib(n): count[0] += 1 if n in cached: return cached[n] elif n < 2: cached[n] = n return n elif n >= 2: cached[n] = fib(n-1) + fib(n-2) return cached[n] return fib, count[0] fib_calculation, c = fibonacci_memoized() print("Memoized recursive Fibonacci sequence solution:", fib_calculation(given_index), "Execution:", c)
Output:
Memoized recursive Fibonacci sequence solution: 13 Execution: 0
Additionally, is this a good way to implement a method using dynamic programming in python, can this code be made better?
Advertisement
Answer
The issue is that you are returning count[0]
, which is an integer. This doesn’t get modified, the reference to count[0]
does. So return count
instead:
def fibonacci_memoized(): cached = {} count = [0] def fib(n): count[0] += 1 if n in cached: return cached[n] elif n < 2: cached[n] = n return n elif n >= 2: cached[n] = fib(n-1) + fib(n-2) return cached[n] # change this line return fib, count # as a test, let's loop fib_calculation, c = fibonacci_memoized() for i in range(5): print( "Memoized recursive Fibonacci sequence solution:", fib_calculation(i), "Execution:", c[0] ) Memoized recursive Fibonacci sequence solution: 0 Execution: 1 Memoized recursive Fibonacci sequence solution: 1 Execution: 2 Memoized recursive Fibonacci sequence solution: 1 Execution: 5 Memoized recursive Fibonacci sequence solution: 2 Execution: 8 Memoized recursive Fibonacci sequence solution: 3 Execution: 11
And to show the memoization works, we can run the loop a second time:
for i in range(5): print( "Memoized recursive Fibonacci sequence solution:", fib_calculation(i), "Execution:", c[0] ) Memoized recursive Fibonacci sequence solution: 0 Execution: 12 Memoized recursive Fibonacci sequence solution: 1 Execution: 13 Memoized recursive Fibonacci sequence solution: 1 Execution: 14 Memoized recursive Fibonacci sequence solution: 2 Execution: 15 Memoized recursive Fibonacci sequence solution: 3 Execution: 16