Note: Click on "Kernel" > "Restart Kernel and Run All" in JupyterLab after finishing the exercises to ensure that your solution runs top to bottom without any errors. If you cannot run this file on your machine, you may want to open it in the cloud 
.
Chapter 9: Mappings & Sets (Coding Exercises)¶
The exercises below assume that you have read the second part 
of Chapter 9.
The ...'s in the code cells indicate where you need to fill in code snippets. The number of ...'s within a code cell give you a rough idea of how many lines of code are needed to solve the task. You should not need to create any additional code cells for your final solution. However, you may want to use temporary code cells to try out some ideas.
Memoization without Side Effects¶
It is considered bad practice to make a function and thereby its correctness dependent on a program's global state: For example, in the "Easy at second Glance: Fibonacci Numbers" section in Chapter 9 , we use a global memo to store the Fibonacci numbers that have already been calculated.
That memo dictionary could be "manipulated." More often than not, such things happen by accident: Imagine we wrote two independent recursive functions that both rely on memoization to solve different problems, and, unintentionally, we made both work with the same global memo. As a result, we would observe "random" bugs depending on the order in which we executed these functions. Such bugs are hard to track down in practice.
A common remedy is to avoid global state and pass intermediate results "down" the recursion tree in a "hidden" argument. By convention, we prefix parameter names with a single leading underscore _, such as with _memo below, to indicate that the caller of our fibonacci() function must not use it. Also, we make _memo a keyword-only argument to force ourselves to always explicitly name it in a function call. Because it is an implementation detail, the _memo parameter is not mentioned in the docstring.
Your task is to complete this version of fibonacci() so that the function works without any side effects in the global scope.
"Easy at third Glance" Example: Fibonacci Numbers 
def fibonacci(i, *, debug=False, _memo=None):
"""Calculate the ith Fibonacci number.
Args:
i (int): index of the Fibonacci number to calculate
debug (bool): show non-cached calls; defaults to False
Returns:
ith_fibonacci (int)
"""
# answer to Q1
if ...:
... = {
0: 0,
1: 1,
}
# answer to Q2
if ...:
return ...
if debug: # added for didactical purposes
print(f"fibonacci({i}) is calculated")
# answer to Q3
recurse = (
fibonacci(...)
+ fibonacci(...)
)
# answer to Q4
... = ...
return ...
Q1: When fibonacci() is initially called, _memo is set to None. So, there is no dict object yet. Implement the two base cases in the first if statement!
Hints: All you need to do is create a new dict object with the results for i=0 and i=1. This object is then passed on in the recursive function calls. Use the is operator in the if statement.
Q2: When fibonacci() is called for non-base cases (i.e., i > 1), it first checks if the result is already in the _memo. Implement that step in the second if statement!
Hint: Use the early exit pattern.
Q3: If fibonacci() is called for an i argument whose result is not yet in the _memo, it must calculate it with the usual recursive function calls. Fill in the arguments to the two recursive fibonacci() calls!
Hint: You must pass on the hidden _memo.
Q4: Lastly, after the two recursive calls have returned, fibonacci() must store the recurse result for the given i in the _memo before returning it. Implement that logic!
Q5: What happens to the hidden _memo after the initial call to fibonacci() returned? How many hidden _memo objects exist in memory during the entire computation?
< your answer >
Because fibonacci() is now independent of the global state, the same eleven recursive function calls are made each time! So, this fibonacci() is a pure function, meaning it has no side effects.
Q6: Execute the following code cell a couple of times to observe that!
fibonacci(12, debug=True) # = 13th Fibonacci number -> 11 recursive calls necessary
The runtime of fibonacci() is now stable: There is no message that "an intermediate result is being cached" as in Chapter 9 .
Q7: Execute the following code cells a couple of times to observe that!
%%timeit -n 1
fibonacci(99)
%%timeit -n 1
fibonacci(999)