0

I wrote a simple recursive program to get the Nth Fibonacci number with a cache to speed it up.

def fibonacci(n, cache={0:0, 1:1}):
    if n-1 not in cache:
        cache[n-1] = fibonacci(n-1)
    return cache[n-1] + cache[n-2]

The problem with that code is that I forgot to pass the cache variable into the recursive call, so I wouldn't expect it to work, since I can't access cache[n-2] once n > 3 -- however, it does work just the same as the the following correct example:

def fibonacci(n, cache={0:0, 1:1}):
    if n-1 not in cache:
        cache[n-1] = fibonacci(n-1, cache)
    return cache[n-1] + cache[n-2]

Can someone explain to me why it seems like cache is being passed into the recursive call in the first snippet?

Newbrict
  • 285
  • 1
  • 13
  • 1
    Maybe it's related to https://stackoverflow.com/questions/366422/what-is-the-pythonic-way-to-avoid-default-parameters-that-are-empty-lists. In particular, the default parameter (here the mutable dict `{0:0, 1:1}`) is created when the function is created. So subsequent calls without `cache` will access this very object. – j1-lee Mar 06 '22 at 04:38
  • Try checking the memory address of `cache` for each recursive call – Abhinav Mathur Mar 06 '22 at 04:39

1 Answers1

0

This is happening because you are providing a default value for one of your function arguments (cache=default_argument). When you call fibonacci and provide a value for cache, then the value you pass in will be used. If you do not provide a value, then the default value is used.

Furthermore, the default argument is evaluated once, when the function is created. Therefore, the same cache object is being reused between invocations, and that is why it appears as if it is "global".

vasia
  • 1,093
  • 7
  • 18