0

I am working with a recursive function like:

from functools import lru_cache
init = {0:1,1:1}

@lru_cache(maxsize=10000)
def fib(n):
  global init
  if n in init.keys():
    return init[n]
  else:
    return fib(n-1)+fib(n-2)

and I defined init as a global variable in order to save all the mid steps for any future computation, but if I run:

print(fib(20))
print(init)

It prints:

10946
{0: 1, 1: 1}

Why even when I defined init as a global variable it still prints the same dictionary? I bet that it is because of the return statement but I might be worng.

Federico Vega
  • 355
  • 2
  • 8

1 Answers1

0

You're not updating the value of init in your function, so it never changes from the original value. You need to update it when you compute the current fibonacci number:

from functools import lru_cache
init = {0:1,1:1}

@lru_cache(maxsize=10000)
def fib(n):
  global init
  if n in init.keys():
    return init[n]
  else:
    fibn = fib(n-1)+fib(n-2)
    init[n] = fibn
    return fibn

print(fib(20))
print(init)

Output:

10946
{0: 1, 1: 1, 2: 2, 3: 3, 4: 5, 5: 8, 6: 13, 7: 21, 8: 34, 9: 55, 10: 89, 11: 144, 12: 233, 13: 377, 14: 610, 15: 987, 16: 1597, 17: 2584, 18: 4181, 19: 6765, 20: 10946}
Nick
  • 138,499
  • 22
  • 57
  • 95
  • You are righ!t but I still dont get the idea of the global statement. If I erase that line, it still print your result, why? – Federico Vega Jun 13 '20 at 01:22
  • It's because you can access variables from the global scope inside a function, and dictionaries are mutable, so although without `global` you can't change the dictionary that `init` *references* inside the function, you can still change its *contents.* There's a good discussion [here](https://stackoverflow.com/questions/13881395/in-python-what-is-a-global-statement) – Nick Jun 13 '20 at 02:07