Python - When are the "non-base case" keys/values stored in the cache dictionary?

Question

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

print(getNthFib(10))
#outputs 34

When exactly do n=3,4,5,6,7,8,9 and their corresponding values get stored in the cache dictionary?

Does the line "cache[n] = getNthFib(n-1, cache) + getNthFib(n-2, cache)" tell the computer to calculate getNthFib(3), getNthFib(4), getNthFib(5), etc? If so, how come?

I'm struggling to understand the function of the cache ARGUMENT.

Answer 1

Solus That's a good question!
I couldn't see how the values of the cache dictionary were being provided either.
I hope you get an answer

Answer 2

When n becomes equal to 3, the base case will be called because 2 (n-1) and 1 (n-2) are keys of the dictionary, and :
cache[3] = cache[2] + cache[1] = 1 + 0 = 2
cache[4] = cache[3] + cache[2] = 1 + 1 = 3 and so on.
So basically the program will begin by decreasing the value of n from 10 to 3 and after that the dict will be updated and n will increase back to 10 and returns the last value. So from n = 10 to n= 3 cache = {1:0, 2:1} and after that it will be updated.
I think there is a reason why it is called cache since the dictionary is a hash map, so fetching a value from the dict has a time complexity = O(1).

Answer 3

It's called memoization (google it!).

The values of previously calculated numbers are stored in the cache to avoid recomputation.

I think this program does not memoize correctly as the cache parameter will be reinstantiated everytime. I am not sure though. I am not so talented in python.