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)


!@%STYLE%@!
{"css":"{\"css\": \"font-weight: bold;\"}","target":"[[{\"line\":0,\"ch\":0},{\"line\":0,\"ch\":3}],[{\"line\":1,\"ch\":4},{\"line\":1,\"ch\":10}]]"}
!@%STYLE%@!
Figure 1.1. The height of each stickman is the previous two stickmen’s heights added together.

1.2. Trivial compression

1.3. Unbreakable encryption

1.4. Calculating pi

1.5. The Towers of Hanoi

1.6. Real-world applications

1.7. Exercises

sitemap