Returning value in a nested function when using memoization

Question

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?

Answer 1

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