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?

That's because you are returning count[0] instead of count — bui
– bui, Commented Sep 1, 2022 at 4:21
You can read this interesting discussion on optimization of the computation of the series — mozway
– mozway, Commented Sep 1, 2022 at 4:47

C.Nivs · Accepted Answer · 2022-09-01 04:58:41Z

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

Collectives™ on Stack Overflow

Returning value in a nested function when using memoization

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related