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.
JavaScript
x
21
21
1
def fibonacci_memoized():
2
cached = {}
3
count = [0]
4
5
def fib(n):
6
count[0] += 1
7
if n in cached:
8
return cached[n]
9
elif n < 2:
10
cached[n] = n
11
return n
12
elif n >= 2:
13
cached[n] = fib(n-1) + fib(n-2)
14
return cached[n]
15
16
return fib, count[0]
17
18
19
fib_calculation, c = fibonacci_memoized()
20
print("Memoized recursive Fibonacci sequence solution:", fib_calculation(given_index), "Execution:", c)
21
Output:
JavaScript
1
2
1
Memoized recursive Fibonacci sequence solution: 13 Execution: 0
2
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:
JavaScript
1
35
35
1
def fibonacci_memoized():
2
cached = {}
3
count = [0]
4
5
def fib(n):
6
count[0] += 1
7
if n in cached:
8
return cached[n]
9
elif n < 2:
10
cached[n] = n
11
return n
12
elif n >= 2:
13
cached[n] = fib(n-1) + fib(n-2)
14
return cached[n]
15
16
# change this line
17
return fib, count
18
19
20
# as a test, let's loop
21
fib_calculation, c = fibonacci_memoized()
22
for i in range(5):
23
print(
24
"Memoized recursive Fibonacci sequence solution:",
25
fib_calculation(i),
26
"Execution:",
27
c[0]
28
)
29
30
Memoized recursive Fibonacci sequence solution: 0 Execution: 1
31
Memoized recursive Fibonacci sequence solution: 1 Execution: 2
32
Memoized recursive Fibonacci sequence solution: 1 Execution: 5
33
Memoized recursive Fibonacci sequence solution: 2 Execution: 8
34
Memoized recursive Fibonacci sequence solution: 3 Execution: 11
35
And to show the memoization works, we can run the loop a second time:
JavaScript
1
14
14
1
for i in range(5):
2
print(
3
"Memoized recursive Fibonacci sequence solution:",
4
fib_calculation(i),
5
"Execution:",
6
c[0]
7
)
8
9
Memoized recursive Fibonacci sequence solution: 0 Execution: 12
10
Memoized recursive Fibonacci sequence solution: 1 Execution: 13
11
Memoized recursive Fibonacci sequence solution: 1 Execution: 14
12
Memoized recursive Fibonacci sequence solution: 2 Execution: 15
13
Memoized recursive Fibonacci sequence solution: 3 Execution: 16
14