3. Function Design and Problem Solving

# Reading 3: Function Design and Problem Solving #

Up to this point, you have spent a great deal of time learning the syntax of Python and practicing function implementation. In this reading, you will learn how to improve the way you design functions in Python and approach programming problems. Specifically, we will describe how you can be more confident about your code’s correctness through unit tests, how you can write cleaner code by reusing existing code, and how to solve certain types of problems more easily using recursion.

## Unit Testing #

In general, testing your code is good practice for software development. Even if you do so informally, just running your code to make sure that it works, you will likely find and fix most of the bugs in your code. In this section, we will help you get started with unit tests to better use testing in your software development workflow.

### A unit test checks that code behaves a certain way #

A unit test is a test to check that a small, specific piece of code (a “unit”) behaves in a specific way.

Suppose that you have a function `average_value(num_list)` - as its name suggests, this function is supposed to calculate the average of a list of numbers. One unit test for this function would be to check that `average_value([1, 2, 3])` is `2.0`. Another would be to check that `average_value([1, 1, 1])` is `1.0`. In the worksheets or assignments in the course so far, you have had Jupyter cells that you could run to compare the output of a function to some expected value - these are unit tests too.

As you may have noticed, passing a unit test doesn’t necessarily mean that your code is working correctly - it just means that it’s working correctly for that specific test case. But code that fails a unit test means that some part of the code is definitely not working correctly.

### Use a collection of diverse unit tests for your code #

Since a single unit test only checks behavior in a single test case, it’s important to use a collection of tests to maximize your confidence that your code is working correctly. If a code passes multiple tests, you can be reasonably sure that your code did not just happen to work as a fluke.

As an example, consider the `average_value` function we mentioned above. You could write the function (incorrectly) like this:

``````def average_value(num_list):
# This code is incorrect, so don't use it in practice.
total_sum = 0
for num in num_list:
total_sum += num
``````

This code incorrectly divides the total sum of the list numbers by 3 instead of by the length of `num_list`. If you use this implementation and run `average_value([1, 2, 3])` or `average_value([1, 1, 1])`, though, you will get the expected answers of `2.0` and `1.0`, respectively. The code behaves correctly, but for the wrong reason.

Thus you should also make sure sure that you use a diverse set of tests. If you include a check that `average_value()` is `1.0`, for example, you’d find that this function fails that test, and know that something is wrong with the code.

### Use pytest and `assert` statements to test your code #

The way you have been testing code so far (running Jupyter cells with tests in them) makes it difficult to test many aspects of your code’s correctness. Running many Jupyter cells every time you change your function is tedious. If you try to put many tests into one cell, then an error in an early test case will prevent your subsequent tests from running at all.

The pytest framework is a simple but powerful way to easily write and run many unit tests. Initially, you’ll only be writing and running a few unit tests for your code, but the skills you build with pytest can be used well into the future, as it is a commonly used framework in practice.

To test a function, you need to write a testing function. In it, you should include an `assert` statement that checks that the output of a function meets some expected criteria. As shown below, an `assert` statement is followed by some expression that evaluates to `True` or `False`:

``````def test_ones_average():
assert average_value([1, 1, 1]) == 1.0
``````

This function runs `average_value([1, 1, 1])`, checks that the output is `1.0`, and results in an error if the outputs do not match.

If you put this function into the same file where `average_value` is implemented, then you can run the code using `pytest`. If the file is called `average.py`, the command and output look like this:

``````\$ pytest average.py
================================== test session starts ===================================
platform linux -- Python 3.8.5, pytest-6.0.2, py-1.9.0, pluggy-0.13.1
rootdir: /home/steve
collected 1 item

average.py .                                                                       [100%]

=================================== 1 passed in 0.00s ====================================
``````

In most cases, pytest determines which functions to run as tests by looking for functions whose names start with `test_`. Thus, you should write your test functions with names like `test_ones_average`, rather than something like just `ones_average`.

### Run multiple unit tests from a single file #

If the file contains multiple tests, pytest will run them all and report which ones failed. Suppose you add the following test to `average.py`:

``````def test_single_average():
assert average_value() == 1.0
``````

Then you will see the following message in the pytest output:

``````======================================== FAILURES ========================================
__________________________________ test_single_average ___________________________________

def test_single_average():
>       assert average_value() == 1.0
E       assert 0.3333333333333333 == 1.0
E        +  where 0.3333333333333333 = average_value()

average.py:13: AssertionError
================================ short test summary info =================================
FAILED average.py::test_single_average - assert 0.3333333333333333 == 1.0
``````

The message shows which test(s) failed, as well as what the function actually returned.

### Put unit tests in a separate file and use good style #

In the example above, we placed the code to test and the testing functions in a single file. It’s good practice to keep the testing functions in a separate file. This keeps the code readable, particularly if you have many functions and test cases.

Your testing file should be named almost identically to the original file, but with `test_` at the beginning, so `average.py` would have tests for its functions in `test_average.py`. To access the function in `average.py`, you will need to use an `import` statement from `test_average.py`. You have already seen `import` statements in worksheets and assignments for this course, but we explain the syntax in more detail in the next section.

You should also use good style in your test functions, and ensure that your docstrings explain what feature of the code you’re testing. For example, the `test_single_average` function above should have a docstring explaining that it tests that taking the average of a list with just one number simply returns that number (or its float equivalent).

You can use the process of designing unit tests to help you make your expectations of the function more precise. For example, what should `average_value([])` return? Trying the above with our implementation above returns `0.0`, but we might have wanted the function to result in an error instead. Of course, what the function actually returns in this case may be irrelevant if the function assumes that the list will never be empty.

It may seem unintuitive at the moment to think about cases like this, but with practice, you can develop a good sense of what kinds of cases. One helpful way to start developing your testing intuition is to think through the possible cases of the function’s behavior.

For example, if a function has an `if`/`else` statement, you should consider writing at least one test for each case - in other words, one test you know will hit the `if` block of the code and one test you know will hit the `else` block. Similarly, if you have a `for` or `while` loop, you should consider writing at least one test that goes through the loop and one test that does not.

No matter how long you have been writing code, you will always write buggy code at least occasionally. But bugs in your code can be beneficial to your development as a software designer - as you encounter more bugs, you will develop a better and better intuition for the types of mistakes that result in bugs, how to test for them, and eventually, how to avoid them in the first place.

## Using Existing Code #

As you develop more complex code, you may find yourself implementing similar functionality repeatedly. For example, in the `average_value` function above, you saw that we added a list of numbers together by defining a variable to hold the running total of numbers (`total_sum`) and used a `for` loop to add each number in the list to this total.

Implementing the same functions over and over can be helpful for building good habits, but is generally not an efficient way to develop software. In this section, we talk about ways in which you can reuse existing functions to write cleaner and more efficient code.

### Use built-in functions for convenience and efficiency #

Python has a number of built-in functions that are, for the most part, always available in the interpreter and in programs. (You can technically overwrite these functions by assigning to them, but you shouldn’t.) You have already seen a few of these functions already: the often used `print`, `range`, and `len`, as well as type conversion functions such as `int`, `str`, and `list`.

Using these functions is recommended for two reasons. First, they are more convenient: it would be a pain to have to write a `for` or `while` loop every time you wanted to find the length of a list or string. Second, they are typically implemented in a more efficient way than most Python programmers would be able to do, so they will usually run faster and require less memory.

Below, we list a few built-in functions that you might find useful.

#### View a function’s docstring with `help`#

The `help` function allows you to view the docstring of any function. For example, if you run `help(len)` in the Python interpreter or Jupyter notebook, you will see the following:

``````Help on built-in function len in module builtins:

len(obj, /)
Return the number of items in a container.
``````

If you run `help` from the Python interpreter, you can exit the help view by pressing `q`.

#### Check that a variable has a certain type with `isinstance`#

The `isinstance` function takes a variable and a type. It returns `True` if the variable is of that type and `False` otherwise.

``````>>> isinstance("abc", str)
True
>>> one_two_three = [1, 2, 3]
>>> isinstance(one_two_three, int)
False
``````

#### Add all the numbers in a sequence with `sum`#

The `sum` function takes a sequence, such as a list or tuple and adds all of the items in it. This allows us to write the `average_value` function from earlier like this:

``````def average_value(num_list):
return sum(num_list) / len(num_list)
``````

Note that `sum` only works for numerical types - it does not work for strings.

#### Concatenate a list of strings with `join`#

The `join` function will concatenate a list of strings. Its syntax is a bit odd:

``````>>> " ".join(["Use", "the", "Force"])
'Use the Force'
``````

As you can see, the string you use before the `.join` part of the function call is used in between items in the list. If you want to quickly concatenate a list of strings without any separation between them, you can use the empty string:

``````>>> "".join(["R", "2", "-", "D", "2"])
'R2-D2'
``````

#### Loop through indices and items with `enumerate`#

The `enumerate` function allows you to loop through a sequences indices and items at the same time. The `for` loop used to do this looks a bit different from what you are used to:

``````number_words = ["zero", "one", "two"]
for index, word in enumerate(number_words):
print(f"{index} is called {word}")
# This code prints the following:
# 0 is called zero
# 1 is called one
# 2 is called two
``````

#### Loop through a dictionary’s keys and values with `items`#

The `items` function is the `enumerate` equivalent for dictionaries:

``````number_words = {"zero": 0, "one": 1, "two": 2}
for word, number in number_words.items():
print(f"{word} is written {number}")
# This code prints the following:
# zero is written 0
# one is written 1
# two is written 2
``````

#### Find the maximum and minimum values of a sequence with `max` and `min`#

You can find the maximum or minimum values of a sequence by using the `max` or `min` functions. For example, here is a demonstration of finding the maximum value in a list:

``````>>> max([6, 5, 8, 9, 0, 3, 7, 2, 4, 1])
9
``````

If you use this with a list of sequences, though, you might get some unexpected results:

``````>>> max([[1, 2, 3], [1, 4]])
[1, 4]
``````

When comparing sequences, Python starts with the first item in the sequence, and breaks ties by subsequent items. So in the example above, Python sees that both lists begin with `1` and compares the items at index 1 in both lists. Since `4` is higher than `2`, `max` returns `[1, 4]`. If the two sequences are mostly equal, except one is longer than the other, like `[1, 2]` and `[1, 2, 3]`, `max` will return the longer one.

#### Sort a sequence with `sorted` or `sort`#

The `sorted` function sorts a sequence from smallest to largest:

``````>>> sorted([6, 5, 8, 9, 0, 3, 7, 2, 4, 1])
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
``````

You can view the sorting how-to for more examples.

If you are working with a list, you can use `.sort()` to sort a list in-place, which modifies the original list:

``````>>> one_digit = [6, 5, 8, 9, 0, 3, 7, 2, 4, 1]
>>> one_digit.sort()
>>> one_digit
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
``````

Note that this version only works with lists.

### Use imports to get code from other files #

You have already seen in worksheets and assignments that you can use code from `.py` files in Jupyter notebooks without having to copy and paste the code into a notebook cell. You did this using the syntax `from X import Y`, where `X` was the name of a file and `Y` was the name of a function or variable to import.

In general, you can use the `import` keyword to make code in other files accessible to the current file, whether you are working in a Jupyter notebook or in a Python file. There are two ways to use the `import` keyword:

• `from X import Y`
• `import X`

where `X` is the filename and `Y` is the function or variable defined in `X`. In a Python file, these lines should be placed at the top of the file.

For now, you should assume that file `X` must be in the same directory as the file you are importing into, with one exception that you will see later in this reading. (There are ways to access files in a different directory, but that’s a topic for a later reading.)

You have already seen import statements of the form `from X import Y`, which let you use `Y` as if it were defined in the current file. You can import multiple things `X` this way, using something like `from X import Y, Z`.

#### The `from X import Y` syntax can cause variables to be overwritten #

You should be careful when you use `from X import Y` that you do not also have a variable called `Y` in your code. If this happens, the one that was defined later will overwrite the previous one. In Jupyter notebooks, it can be especially easy to do this, since `import` statements do not all appear at the top of a notebook, and the order in which you run cells matters.

You may also see `from X import *` on Q&A sites. As in Bash, the asterisk (`*`) is a wildcard that matches anything, and thus this statement will import everything from `X`. You should not use this form because it is much harder to keep track of what is being imported (and what you might overwrite in your code).

#### `import` statements are safe from overwriting but more verbose to use #

A safer way to import code is to use the form `import X`. This will make all the variables in `X` available to you, but you access those variables slightly differently. Rather than using the variables `Y` and `Z`, for example, you would use `X.Y` and `X.Z`. This method is more tedious to write but avoids the overwriting issues mentioned above.

#### Unit tests are a good example for how to use imports #

Suppose you wanted to move your unit tests for `average_value` into a new file, as is good practice. To make sure that you could then access the `average_value` function (in the file `average.py`) from your test file `test_average.py`, you would write the file like this:

``````from average import average_value

def test_ones_average():
assert average_value([1, 1, 1]) == 1.0

def test_single_average():
assert average_value() == 1.0
``````

Or, if you used a plain `import` statement:

``````import average

def test_ones_average():
assert average.average_value([1, 1, 1]) == 1.0

def test_single_average():
assert average.average_value() == 1.0
``````

### Use helpful features from the Python standard library #

Beyond built-in functions, Python provides a standard library with commonly used functions for convenience. These features are split into different modules, each of which you can import using the syntax above. You can view the entire library here.

The `math` module provides some common math functions , such as `ceil` and `floor` (which round up and down to the nearest integer, respectively), `sqrt` (which takes the square root of a number), and the standard trigonometry functions. It also provides some useful constants: `inf` represents infinity, and `pi` is the well-known constant that begins with 3.14.

The `random` module provides functions to generate random numbers, including ints (`randint`) and floats (`random` or `uniform`). It also provides functions to pick a random element of a sequence (`choice`) or to put the elements of a sequence in a random order (`shuffle`).

The `string` module provides functionality to build specifically formatted strings (though much of this functionality can be done with f-strings). It also provides helpful strings that represent different sets of characters, such as all uppercase letters (`ascii_uppercase`), numbers, (`digits`), and punctuation (`punctuation`).

The `collections` module provides a variety of container data structures designed for holding items. While most of them have fairly specialized use cases, one is rather helpful in many situations: `defaultdict`. This essentially allows you to create a dictionary that assumes a default value for any key not in it. This saves you the trouble of checking whether something is in the dictionary before using it:

``````from collections import defaultdict

letter_count = defaultdict(int)
sentence = "King Philip Came Over For Great Spaghetti"
for character in sentence:
# Any key not in letter_count is mapped to 0 when you try to access it.
letter_count[character] += 1
``````

As you progress through this course, we will discuss a few other modules that will be useful on future assignments and projects.

## Recursion #

Recursion is a problem-solving approach and programming technique that has its roots in the mathematical foundations of computer science. Despite not being used that often in much of software development, recursion is a technique that many potential employers will expect you to have some familiarity with.

In the problem-solving context, recursion involves repeatedly breaking a problem or task down into smaller versions of itself until it can be easily solved, then using those smaller solutions to build up a solution to the original problem. In the programming context, this is implemented as a function that calls itself.

In this section, we will present recursion as both a way of solving problems and a way of writing functions. We will provide few worked-out examples to illustrate recursion. Since recursion is only a well-suited approach for certain types of problems, we will also describe the situations in which using recursion is likely to be helpful.

To explain how to approach a problem using recursion, we will use an example problem through the next few sections.

The problem is to find the minimum value in a list of numbers. We have already seen this done using a `for` loop, and we saw earlier in this chapter that we can simply use the `min` function for this. Now we will take a look at how to solve this problem using recursion, which we hope will be a good comparison with the other approaches.

### Identify a trivially small and easy version of the problem #

The problem we are trying to solve here is to find the minimum of a list of numbers. The first step in using recursion is to find a set of cases where this problem can be solved more or less trivially. This is called the base case in recursion, and will be used to build up a solution to the problem that can be used for all lists.

In our example problem, the trivial case is when our list has only one number in it. In this case, whatever that number is must be the minimum value by default. Usually, base cases for a problem tend to look something like this: an empty sequence or string, a sequence with only one item in it, an integer argument that is 0 or 1, etc. We would not use an empty list as the base case for this example problem, since taking the minimum of an empty list doesn’t make much sense.

Problems can occasionally have multiple base cases. For example, if your function takes an integer `n`, it may have a base case that returns `True` when `n` is 1 and `False` when `n` is 0.

### Break the problem into smaller versions towards the base case #

Once you have identified the base case of a problem, you should think about how to break the problem down into smaller versions, called the recursive cases or recursive calls. As you do this, you should keep two principles in mind:

1. You should break the problem into a small unit of work and a smaller version of the same problem.
2. Breaking down the problem repeatedly in this way should eventually get to the base case.

What constitutes a “small unit of work” is somewhat up to your discretion, but typically involves some post-processing of the results of the recursive calls. We will describe this work more in the next section.

In our example problem, we can consider smaller and smaller versions of the problem by splitting the list into its first item and the rest of the list. Here is a concrete example:

``````[2, 0, 1, 3]  # The original list.
2, [0, 1, 3]  # Split the first item from the original list and consider the
# list [0, 1, 3].
0, [1, 3]  # Repeat the process.
1,   # Now we have a base case: .
```    # If the first and last characters aren't the same, it can't be a palindrome.

We can see that the length of the list goes down by 1 in each step. Beause of this we know that we will eventually reach a list of length 1, which is a base case.

### Use solutions to the recursive cases to build a solution for the original problem

Once you hit a base case, you can solve the problem trivially. Now, you should determine how to do the "small unit of work" we mentioned earlier to build up larger solutions.

In our example, we hit a base case, which was to find the minimum of the list ``. Clearly, the minimum of this list is 3. In the step before we reached this case, we split the list `[1, 3]` into the first item of the list (`1`) from the rest of the list. So what do we now do with `1`?

Because we are trying to find the overall minimum of the list, we should compare it to the solution we got for the minimum of `` and reutrn whichever is smaller. In this case, we are comparing `1` and `3`, of which `1` is smaller. Thus, the minimum of the list `[1, 3]` is `1`.

If we repeate this process, we can build up the minimum of more and more of the original list until we have the full list. Thus in this case, the "small unit of work" is to compare the current "head" of the list (that was split off in this step) to the minimum of the rest of the list (that was just calculated) and return the smaller one. Here is a concrete example of this process:

```python
1,   # 1 is smaller than 3, so the minimum of [1, 3] is 1.
0, [1, 3]  # 0 is smaller than 1, so the minimum of [0, 1, 3] is 0.
2, [0, 1, 3]  # 0 is smaller than 2, so the minimum of [2, 0, 1, 3] is 0.
# [2, 0, 1, 3] was the original list, so we are done and the minimum is 0.
``````

### Implement the approach in code #

Notice that the process we use in each step of the recursive approach is identical: split the head of the list from the rest, find the minimum of the rest, and take the smaller of the two. If the list only has one item in it, simply return that item.

Because the smaller versions of the problem have the same approach to solving them as the entire problem, we can use the same function code in each step. The way to do this in Python is to have a function call itself, like this:

``````def list_min(numbers):
# This is the base case. Simply return the number.
if len(numbers) == 1:
return numbers
else:
# Split the head of the list.
first = numbers
# Find the minimum of the rest of the list.
min_rest = list_min(numbers[1:])  # list_min calls itself here.

# Return the smaller of the two.
if first < min_rest:
return first
else:
return min_rest
``````

It can be a bit difficult to fully understand this logic without seeing the function in action. We highly recommend you view a step-by-step visualization of this function to get a better sense of how this approach works in practice.

### Recursion is only useful for some problems #

The function we used previously was used as an example to show the thought process behind recursion, but in practice the function is much better written with a `for` loop:

``````def list_min(numbers):
minimum = None
for num in numbers:
if minimum is None or num < minimum:
minimum = num
return num
``````

(You could also just use the `min` function we introduced earlier, which would be an even better approach.)

While this problem was helpful in seeing the conceptual logic behind recursion, the actual code turned out to be a bit messy in practice. We chose this problem to illustrate that while recursion can be applied to many problems, it is not always an ideal way to approach problems.

As a problem-solving approach, recursion is usually compared against iteration (which uses a `for` or `while` loop to solve a problem). Any problem that can be solved with recursion can also be solved with iteration, and vice versa. But you will often find that one approach is much more intuitive than the other.

So when is recursion a better approach than iteration? In practice, we’ve found two helpful signs that recursion may be a well-suited approach:

1. You don’t know beforehand how many iterations or steps you have to go through. If you know how many steps you have to take, then you should just write a `for` loop, with something like `for thing in sequence:` or `for i in range(len(sequence)):`.
2. You need to keep track of or combine information from previous steps. If you don’t know how many iterations you need to do but it is relatively easy to keep track of the previous steps, you may consider using a `while` loop instead.

To illustrate some cases in which recursion is better suited, we will present two problems - one from a more conceptual perspective with no real code, and one from a more programming-oriented perspective.

### Recursion is suited to listing files within a folder hierarchy #

Suppose you want to list all of the regular files that are within a folder or any of its subfolders. For example, consider the following directory structure:

``````deep-sea-divers
└── photic
└── twilight
└── bathyal
├── abyssal
│   ├── detritus.txt
│   └── treasure.zip
├── angler.sh
├── pollutant.zip
├── trash.txt
└── wreckage.py
``````

The goal is to list the six files you can see in this structure.

This problem is well-suited to a recursive solution for the following reasons:

1. It isn’t obvious at the start of the problem how many iterations to make. You can see from this structure that there are files that are five folders deep, but if you didn’t know what was in `deep-sea-divers` to begin with, the only way to find out would be to actually open all of the folders.
2. Some folders have a mix of subfolders and files, and some folders can have multiple subfolders. Taking an iterative approach would be difficult, since you would then need to keep track of where you are in the directory structure, as well as the files and subfolders at each level.

Conceptually, though, a recursive approach is rather straightforward:

1. Look in the current folder and list all of the regular files in it.
2. If there are any subfolders in the current folder, apply the same approach to each of those subfolders.

Eventually, you will reach a folder that has no subfolders, as you cannot have an infinite cascade of folders nested in each other. This is the base case, as you simply can list the files in this folder.

### Recursion can be used to buy snacks #

Consider a fictional club on campus: the Olin Fried Asparagus Club, or OFAC for short. This club sells packages of fried asparagus stalks in sets of 6, 10, or 15. If you want 12 stalks, you can buy two packages of 6, but this is not possible for every number: if you want 13 stalks, for example, there is no way to buy a combination of packages that gets you exactly 13 stalks. (You could buy a package of 15 and give two away, though.)

You want to determine for any number of asparagus stalks if it is possible to buy a combination of packages to equal exactly that number. This problem is well-suited to recursion, based on our two criteria above:

1. You don’t know how many iterations you need to make, because it depends on what combinations of packages you buy. For example, if you want 30 stalks, you could buy five packages of 6, three packages of 10, or two packages of 15.
2. Keeping track of all of the possible package combinations is difficult. If for example, you want to buy 42 stalks, you can start by buying a package of 6, 10, or 15. Then, you have three sub-problems: trying to buy 36, 32, or 27 stalks (42 - 6, 10, or 15, respectively). For each of those, you would need to keep track of the possible combinations, and this would get rather tedious.

Fortunately, recursion again turns out to be a helpful approach.

There are a number of base cases to consider here:

• If you need to buy 0 stalks, then this is easily possible - just buy nothing.
• If you need to buy 5 or fewer stalks (but not 0), this is impossible - the minimum you can buy in a single package is 6.

Otherwise, you can subtract 6, 10, or 15 from the number you want to buy, and see if any of those combinations will work.

Following this approach, your code would look like this:

``````def asparagus(n):
if n == 0:
return True
# Note the case below also includes negative numbers, which can happen in
# some recursive calls (such as if n is 7 and you subtract 10).
elif n < 6:
return False
else:
return nuggets(n - 6) or nuggets(n - 10) or nuggets(n - 15)
``````

Because each recursive call subtracts some number from the originally desired number of stalks, you are guaranteed to eventually hit one of the base cases (either the desired number is 0 or otherwise less than 6).