Classic Computer Science Problems in Python

David Kopec, Tomz Eastmond, Ivan Martinovic

• Publisher: Manning Publications
• Year: 2019
• ISBN:
  9781617295980
• Topic: Informatica
• Subtopic: Programmazione in Python

Classic Computer Science Problems in Python deepens your knowledge of problem solving techniques from the realm of computer science by challenging you with time-tested scenarios, exercises, and algorithms. As you work through examples in search, clustering, graphs, and more, you'll remember important things you've forgotten and discover classic solutions to your "new" problems!

Chapter 1. Small problems

To get started, we will explore some simple problems that can be solved with no more than a few relatively short functions. Although these problems are small, they will still allow us to explore some interesting problem-solving techniques. Think of them as a good warm-up.

1.1. The Fibonacci sequence

The Fibonacci sequence is a sequence of numbers such that any number, except for the first and second, is the sum of the previous two:

0, 1, 1, 2, 3, 5, 8, 13, 21...

The value of the first Fibonacci number in the sequence is 0. The value of the fourth Fibonacci number is 2. It follows that to get the value of any Fibonacci number, n, in the sequence, one can use the formula

fib(n) = fib(n - 1) + fib(n - 2)

1.1.1. A first recursive attempt

The preceding formula for computing a number in the Fibonacci sequence (illustrated in figure 1.1) is a form of pseudocode that can be trivially translated into a recursive Python function. (A recursive function is a function that calls itself.) This mechanical translation will serve as our first attempt at writing a function to return a given value of the Fibonacci sequence.

Listing 1.1. fib1.py

def fib1(n: int) -> int: return fib1(n - 1) + fib1(n - 2)

Figure 1.1. The height of each stickman is the previous two stickmen’s heights added together.

Let’s try to run this function by calling it with a value.

Listing 1.2. fib1.py continued

if __name__ == "__main__": print(fib1(5))

Uh-oh! If we try to run fib1.py, we generate an error:

RecursionError: maximum recursion depth exceeded

The issue is that fib1() will run forever without returning a final result. Every call to fib1() results in another two calls of fib1() with no end in sight. We call such a circumstance infinite recursion (see figure 1.2), and it is analogous to an infinite loop.

Figure 1.2. The recursive function fib(n) calls itself with the arguments n-2 and n-1.

1.1.2. Utilizing base cases

Notice that until you run fib1(), there is no indication from your Python environment that there is anything wrong with it. It is the duty of the programmer to avoid infinite recursion, not the compiler or the interpreter. The reason for the infinite recursion is that we never specified a base case. In a recursive function, a base case serves as a stopping point.

In the case of the Fibonacci function, we have natural base cases in the form of the special first two sequence values, 0 and 1. Neither 0 nor 1 is the sum of the previous two numbers in the sequence. Instead, they are the special first two values. Let’s try specifying them as base cases.

Listing 1.3. fib2.py

def fib2(n: int) -> int: if n < 2: # base case return n return fib2(n - 2) + fib2(n - 1) # recursive case

Note

The fib2() version of the Fibonacci function returns 0 as the zeroth number (fib2(0)), rather than the first number, as in our original proposition. In a programming context, this kind of makes sense because we are used to sequences starting with a zeroth element.

fib2() can be called successfully and will return correct results. Try calling it with some small values.

Listing 1.4. fib2.py continued

if __name__ == "__main__": print(fib2(5)) print(fib2(10))

Do not try calling fib2(50). It will never finish executing! Why? Every call to fib2() results in two more calls to fib2() by way of the recursive calls fib2(n - 1) and fib2(n - 2) (see figure 1.3). In other words, the call tree grows exponentially. For example, a call of fib2(4) results in this entire set of calls:

fib2(4) -> fib2(3), fib2(2) fib2(3) -> fib2(2), fib2(1) fib2(2) -> fib2(1), fib2(0) fib2(2) -> fib2(1), fib2(0) fib2(1) -> 1 fib2(1) -> 1 fib2(1) -> 1 fib2(0) -> 0 fib2(0) -> 0

Figure 1.3. Every non-base-case call of fib2() results in two more calls of fib2().

If you count them (and as you will see if you add some print calls), there are 9 calls to fib2() just to compute the 4th element! It gets worse. There are 15 calls required to compute element 5, 177 calls to compute element 10, and 21,891 calls to compute element 20. We can do better.

1.1.3. Memoization to the rescue

Memoization is a technique in which you store the results of computational tasks when they are completed so that when you need them again, you can look them up instead of needing to compute them a second (or millionth) time (see figure 1.4).^[1]

¹

Donald Michie, a famous British computer scientist, coined the term memoization. Donald Michie, Memo functions: a language feature with “rote-learning” properties (Edinburgh University, Department of Machine Intelligence and Perception, 1967).

Figure 1.4. The human memoization machine

Let’s create a new version of the Fibonacci function that utilizes a Python dictionary for memoization purposes.

Listing 1.5. fib3.py

from typing import Dict memo: Dict[int, int] = {0: 0, 1: 1} # our base cases def fib3(n: int) -> int: if n not in memo: memo[n] = fib3(n - 1) + fib3(n - 2) # memoization return memo[n]

You can now safely call fib3(50).

Listing 1.6. fib3.py continued

if __name__ == "__main__": print(fib3(5)) print(fib3(50))

A call to fib3(20) will result in just 39 calls of fib3() as opposed to the 21,891 of fib2() resulting from the call fib2(20). memo is prefilled with the earlier base cases of 0 and 1, saving fib3() from the complexity of another if statement.

1.1.4. Automatic memoization

fib3() can be further simplified. Python has a built-in decorator for memoizing any function automagically. In fib4(), the decorator @functools.lru_cache() is used with the same exact code as we used in fib2(). Each time fib4() is executed with a novel argument, the decorator causes the return value to be cached. Upon future calls of fib4() with the same argument, the previous return value of fib4() for that argument is retrieved from the cache and returned.

Listing 1.7. fib4.py

from functools import lru_cache @lru_cache(maxsize=None) def fib4(n: int) -> int: # same definition as fib2() if n < 2: # base case return n return fib4(n - 2) + fib4(n - 1) # recursive case if __name__ == "__main__": print(fib4(5)) print(fib4(50))

Note that we are able to calculate fib4(50) instantly, even though the body of the Fibonacci function is the same as that in fib2(). @lru_cache’s maxsize property indicates how many of the most recent calls of the function it is decorating should be cached. Setting it to None indicates that there is no limit.

1.1.5. Keep it simple, Fibonacci

There is an even more performant option. We can solve Fibonacci with an old-fashioned iterative approach.

Listing 1.8. fib5.py

def fib5(n: int) -> int: if n == 0: return n # special case last: int = 0 # initially set to fib(0) next: int ...