Chapter 2 : Functional Programming

2.1 Humans, Chimpanzees, and Spell Checkers

For many years, scientists were uncertain whether humans were more closely related to chimpanzees or gorillas. New technologies and clever computational methods have allowed us to resolve this issue in recent years: humans are evidently more closely related to chimps than to gorillas. Humans and chimps diverged from their common ancestor approximately 4–6 million years ago, while gorillas diverged about 2 million years before that. How did we come to that conclusion? One of the primary methods involves computational analysis of DNA, the genetic code—or genome—that is essentially the “program” for all living creatures.

As you may recall from your biology class, DNA is a sequence of molecules fondly known as “A”, “T”, “C”, and “G”. Each living organism has a long sequence of these “letters” that make up its genome. Computer scientists refer to a sequence of symbols as a string.

Imagine that we look at a DNA string from the human genome and a string from the corresponding location of the chimp genome. For example, in the human we might see the string “ATTCG” and in the chimp we might see “ACTCG.” The human and chimp DNA differ in only one position (the second one). In contrast, imagine that the gorilla’s DNA string at the corresponding part of its genome is “AGGCG.” Notice that the gorilla differs from the human in two positions (the second and third) and also differs from the chimp in two positions (again, the second and third). So the gorilla exhibits more differences from the human and the chimp than those two species differ from one another. This kind of analysis (on a larger scale and with more complex ways of comparing differences) allows scientists to make inferences about when species diverged. In a nutshell, the key computational idea here is determining the level of similarity between two strings.

But how exactly do we measure the similarity between two strings? We’re glad you asked! Biologists know that there are three fundamental ways in which DNA changes over time. First, a single letter in the genome can change to another letter. This is called substitution. Second, a letter in the genome can be deleted, and third, a new letter can be inserted. A reasonable definition of “similarity” is to find the smallest number of substitutions, insertions, and deletions required to get from our first string to our second string. For example, to get from the DNA string “ATC” to the string “TG”, we can delete the “A” in “ATC” to get “TC”. Then we can change the “C” to a “G” to get “TG.” This took two operations—and that’s the best that we can do in this case. We say that the edit distance between these two strings is 2.

../_images/Alien3.PNG

It seems that biology beat computer science to programming!

Interestingly, this problem also arises in spell checking. Many word processing programs have built-in spell checkers that will try to offer you a number of alternatives to a word that you’ve misspelled. For example, when we typed “spim” in one spell checker it offered us a list of alternatives that included “shim”, “skim”, “slim”, “spam”, “spin”, “spit”, “swim”, among others. You can probably see why those words were suggested: They are all legitimate English words that differ from “spim” by only a little bit. In general, a spell checker might check every word in its dictionary against the word that we typed in, measure the difference between those two words, and then show us a short list of the most similar words. Here again, we need a way to compute the similarity between two strings.

For example, consider the pair of strings “spam” and “poems”. One way to get from “spam” to “poems” is through the following sequence of operations: Delete “s” from “spam” resulting in “pam” (a deletion), replace the “a” with an “o” resulting in “pom” (a substitution), insert an “e” after the “o” resulting in “poem” (an insertion), and insert an “s” at the end of “poem” resulting in “poems” (another insertion). This took a total of four operations. Indeed, that’s the smallest number of operations required to get from “spam” to “poems.” In other words, the edit distance between “spam” and “poems” is 4. By the way, you’ll notice that we defined the edit distance to be the smallest number of operations needed to get from the first string to the second. A few moments of thought will convince you that this is exactly the same as the number of operations required to get from the second string to the first. In other words, edit distance is symmetric—it doesn’t depend on which of the two strings we start with.

Our ultimate goal in this chapter is to write a program to compute the edit distance. We’ll begin with the foundations of programming in the Python programming language and then explore a beautiful technique called “recursion.” Recursion will allow us to write short and very powerful computer programs to compute the edit distance between two strings—and many other useful things.

2.2 Getting Started in Python

Python is a programming language that, according to its designers, aims to combine “remarkable power with very clear syntax.” Indeed, in very short order you’ll be able to write programs that solve interesting and useful problems. While we hope that this and later chapters will be pleasant reading, there’s no better way to learn the material than by trying it yourself. Therefore, we recommend that you pause frequently and try some of the things that we’re doing here on a computer. Moreover, this book is relatively short and to-the-point. To truly digest this material, it will be important for you to do the exercises on the book’s Web site or assignments given to you by your instructor. Let’s get started! When you start up Python, it presents you with a “prompt” that looks like this:

>>>

That’s your invitation to type things in. For now, let’s just type in arithmetic—essentially using Python as a calculator. (We’ll do fancier things soon.) For example, below we’ve typed 3+5.

>>> 3 + 5
8

Next, we can do more complex things, like this:

>>> (3 + 5) * 2 - 1
15

Notice that parentheses were used here to control the order of operations. Normally, multiplication and division have higher precedence than addition or subtraction, meaning that Python does multiplications and divisions first and addition and subtractions afterwards. So without parentheses we would have gotten:

>>> 3 + 5 * 2 - 1
12

You can always use parentheses to specify your desired order of operations. Here are a few more examples of arithmetic in Python:

>>> 6 / 2
3
>>> 2 ** 5
32
>>> 10 ** 3
1000
>>> 52 % 10
2

You may have inferred what /, \**, and % do. In particular, 52 % 10 is the remainder when 52 is divided by 10—it’s pronounced “52 mod 10”. Arithmetic symbols like +, -, /, *, **, and % are called operators.

We pause our regularly scheduled program to make a quick observation about division. In Python 2, division can be a bit surprising. Here’s an example:

>>> 11 / 2
5

In Python 2, when the numerator and denominator are both integers, Python assumes that you want the result to be an integer as well. Although 11 divided by 2 is 5.5, Python gives just the integer part of the solution which is 5. If you want Python 2 to give you the digits after the decimal point, you need to use a decimal point somewhere. For example, you could do any of these:

>>> 11.0 / 2
5.5
>>> 11 / 2.0
5.5
>>> 11.0 / 2.0
5.5

Python 3, on the other hand, always gives you the digits after the decimal point. If you want to do integer division in Python 3 (dividing two integers and getting an integer back), you’ll need to use the special integer division // as in:

>>> 11 // 2
5

2.2.1 Naming Things

Python lets you give names to values — the results of calculations. Here’s an example:

>>> pi = 3.1415926
>>> pi * (10 ** 2)
314.15926

In the first line, we defined pi to be 3.1415926. In the second line, we used that value to compute the area of a circle with radius 10. Computer scientists call a name like “pi” a variable because we can assign it any value that we like. In fact, we could, if we wanted to, give “pi” a new value later. We could even give it some crazy value like 42 (although that’s probably not a great idea if we’re going to use it compute the area of a circle). The point here is that a “variable” in the computer science sense is different from a variable in the mathematical sense. No sane mathematician would say that the number π is a variable!

../_images/Alien3.PNG

Calling \(\pi\) a “variable” would be irrational.

Notice that the “=” sign is used to assign a value to a variable. On the left of the equal sign is the name of the variable. On the right of the equal sign is an expression that Python evaluates and then assigns that value to the variable. For example, we could have done this:

>>> pi = 3.1415926
>>> area = pi * (10 ** 2)
>>> area
314.15926

In this case, we define a variable called pi in the first line. In the second line, the expression pi * (10 ** 2) is evaluated (its value is 314.15926) and that value is assigned to another variable called area. Finally, when we type area at the prompt, Python displays the value. Notice, also, that the parentheses weren’t actually necessary in this example. However, we used them just to help remind us which operations will be done first. It’s often a good idea to do things like this to make your code more readable to other humans. Note that the equals sign represents an action, namely changing the variable on the left (in this case, pi or area) so that it has a new value. That value can be changed later. It is important to distinguish this notation from the use of the equals sign in mathematics, where it means that the left and right side are forever the same. That’s not the case in CS!

2.2.2 What’s in a Name?

Python is not too picky about the names of variables. For example naming a variable Joe or Joe42 is fine. However, naming a variable Joe+Sally is not permitted. You can probably imagine why: if Python sees Joe+Sally it will think that you are trying to add the values of two variables Joe and Sally. Similarly, there are built-in Python special words that can’t be used as variable names. If you try to use them, Python will give you an error message. Rather than listing here the words that cannot be used as Python variable names, just keep in mind that if you get a Python error when trying to assign a variable, it’s probably because you’ve stumbled upon the relatively small number of names that are not permitted. Finally, try to use descriptive variable names to help the reader understand your program. For example, if a variable is going to store the area of a circle, calling that variable area (or even areaOfCircle) is a much better choice than calling it something like z or x42b or harriet.

2.3 More Data: From Numbers to Strings

One of our central themes for this book is data. In the previous section we worked with one kind of data: numbers. That was all good, but numbers are not the only useful kind of data. In the rest of this chapter we’ll introduce a few other types of data that are central to solving problems in Python. Indeed, at the start of the chapter we noted that we’re going to want to compare strings. In Python, a string is any sequence of symbols within quotation marks. Python allows you to use either double quotes or single quotes around a string. However, Python displays strings in single quotes, regardless of whether you used single or double quotes. Here are some examples:

>>> name1 = "Ben"
>>> name2 = 'Jerry'
>>> name1
'Ben'
>>> name2
'Jerry'

Again, name1 and name2 are just variables that we’ve defined. There’s nothing particularly special about those variable names. While there are many things that we can do with strings, we want to show you just a few of the most important things here. In the examples that follow, we assume that we’ve defined the strings name1 and name2 as shown above.

2.3.1 A Short Note on Length

First, we can find the length of a string by using Python’s len function:

>>> len(name1)
3
>>> len('I love spam!')
12

In the first example, name1 is the string ’Ben’ and the length of that string is 3. In the second example, the string contains two spaces (a space is a regular symbol so it gets counted in the length) so the total length is 12.

2.3.2 Indexing

Another thing that we can do with strings is find the symbol at any given position or index. In most computer languages, including Python, the first symbol in a string has index 0. So,

>>> name1[0]
'B'
>>> name1[1]
'e'
>>> name1[2]
'n'
>>> name1[3]
IndexError: string index out of range

Notice that although name1 , which is ’Ben’, has length 3, the symbols are at indices 0, 1, and 2 according to the funny way that Python counts. There is no symbol at index 3, which is why we got an error message. (Computer scientists start counting from 0 rather than from 1.)

2.3.3 Slicing

Python lets you find parts of a string using its special slicing notation. Let’s look at some examples first:

>>> bestFood = 'spam burrito'
>>> bestFood[0:3]
'spa'
>>> bestFood[0:4]
'spam'
../_images/Alien3.PNG

I don’t really want a slice of your spam burrito.

What’s going on here? First, we’ve defined a variable bestFood and given it the string ‘spam burrito’ as its value. The notation bestFood[0:3] is telling Python to give us the part—or “slice”—of that string beginning at index 0 and going up to, but not including, index 3. So, we get the part of the string with symbols at indices 0, 1, and 2, which are the three letters s, p, a — resulting in the string spa. It may seem strange that the last index is not used, so we don’t actually get the symbol at index 3 when we ask for the slice bestFood[0:3]. It turns out that there are some good reasons why the designers of Python chose to do this, and we’ll see examples of that later. By the way, we don’t have to start at index 0. For example:

>>> bestFood[2:6]
'am b'

This is giving us the slice of the string 'spam burrito' from index 2 up to, but not including, index 6. We can also do things like this:

>>> bestFood[1:]
'pam burrito'

When we leave out the number after the colon, Python assumes we mean “go until the end.” So, this is just saying “give me the slice that begins at index 1 and goes to the end.” Similarly,

>>> bestFood[:4]
'spam'

Because there was nothing before the colon, it assumes that we meant 0. So this is the same as bestFood[0:4].

2.3.4 String Arithmetic

Strings can be “added” together. Adding two strings results in a new string that is simply the first one followed by the second. This is called string concatenation. For example,

>>> 'yum' + 'my'
'yummy'

Once we can add, we can also multiply!

>>> 'yum' * 3
'yumyumyum'

In other words, 'yum' * 3 really means 'yum' + 'yum' + 'yum', which is 'yumyumyum': the concatenation of 'yum' three times.

2.4 Lists

So far we’ve looked at two different types of data: numbers and strings. Sometimes it’s convenient to “package” a bunch of numbers or strings together. Python has another type of data called a list that allows us to do this. Here’s an example:

>>> oddNumbers = [1 , 3 , 5 , 7 , 9 , 11]
>>> friends = [ 'rachel' , 'monica' , 'phoebe' , 'joey' , 'ross']

In the first case, oddNumbers is a variable and we’ve assigned that variable to be a list of six odd numbers. In the second case, friends is a variable and we’ve given it a list of five strings. If you type oddNumbers or friends, Python will show you what those values are currently storing. Notice that a list starts with an open bracket [, ends with a close bracket ], and each item inside the list is separated from the next by a comma. Check this out:

>>> stuff = [2 , 'hello' , 2.718]

Notice that stuff is a variable that is assigned to be a list, and that list contains two numbers and a string. Python has no objection to different kinds of things being inside the same list! In fact, stuff could even have other lists in it, as in this example:

>>> stuff = [2 , 'hello' , 2.718 , [1 , 2 , 3]]

This ability to have multiple types of data living together in the same list is called polymorphism (meaning “many types”), which is a common feature in functional programming languages.

2.4.1 Some Good News!

Here’s some good news: Almost everything that works on strings also works on lists. For example, we can ask for the length of a list just as we ask for the length of a string:

>>> len(stuff)
4

Notice that the list stuff really only has four things in it: The number 2, the string 'hello', the number 2.718, and the list [1, 2, 3]. Indexing and slicing also work on lists just as on strings:

>>> stuff [0]
2
>>> stuff [1]
’hello’
>>> stuff [2:4]
[2.718, [1, 2, 3]]

Just like strings, lists can be added and multiplied as well. Adding two lists together creates a new list that contains all of the elements in the first list followed by all of the elements in the second. This is called list concatenation and is similar to string concatenation.

>>> mylist = [1, 2, 3]
>>> mylist + [4, 5, 6]
[1, 2, 3, 4, 5, 6]
>>> mylist * 3
[1, 2, 3, 1, 2, 3, 1, 2, 3]

Finally, it’s worth noting that doing something like:

>>> mylist + [4 , 5 , 6]

doesn’t actually change mylist. Instead, it gives you a NEW list which is the result of concatenating mylist and the list [4, 5, 6]. You can verify this by typing mylist at the Python prompt and seeing that it wasn’t changed:

>>> mylist + [4 , 5 , 6]
[1, 2, 3, 4, 5, 6]
>>> mylist
[1, 2, 3]

2.5 Functioning in Python

We’ve covered the basics of Python including how to represent and work with several types of data including numbers, strings and lists! Next, we’re going to write actual programs. Throughout this and the remaining sections, we will keep in mind the problem that is motivating us in the first place—calculating edit distance—by looking at examples that help us build toward a solution to that problem. However, we wouldn’t want you to get bored by looking at just one single problem, so we’ll also throw in some other interesting ones along the way.

Let’s begin with an analogy to something that you know and love: mathematical functions. In math, a function can be thought of as a “box” that takes some data as input, or argument, and returns some data as output, which we call its result, return value, or simply value. For example, the function \(f (x) = 2x\) has an argument called \(x\), and for any value that we “stick into” \(x\) we get back a value that is twice as large. Python lets us define functions too, and as in math, these functions take some data as arguments, process that data in some way, and then return some data as a result. Here’s a Python function that we’ve named f, which takes an argument we are calling \(x\) and returns a result that is two times \(x\).

In other words:

def f ( x ):
    return 2 * x
../_images/Alien3.PNG

Actually, we’ll learn later that unlike in math, Python functions do not have to take arguments or return results. But for now we’ll focus on functions that do.

In Python, the syntax for functions uses the special word def, which means: “I’m def ining a function.” Then comes the name that we’ve chosen for the function; in our case we chose to call it f. Then come the arguments to the function in parentheses (just like the definition of a function in math!), followed by a colon (“:”). Then, we start a new line, indented a few spaces, and begin the function. In this case, our function computes 2*x and then returns it. The word return tells Python to give us back that value as the function’s result. Don’t forget to indent the line (or lines) after the first line. Python absolutely demands this. We’ll talk a bit more about indentation shortly. We can now run the function in the Python interpreter like this:

>>> f (10)
20
>>> f ( -1)
-2

When we type f(10) we say that this is a function call because we are metaphorically placing a telephone call to f with argument 10 and asking it to give us an answer. When we call f, Python takes the value inside the parentheses and assigns it to the name x. Then it executes the statement or statements inside the function in order until there are no more statements to execute in the function. In this case, there is only a single statement inside the function, which doubles the value of x and returns the result to where the function was called.

../_images/Alien3.PNG

The Python IDLE environment is named after Eric Idle, one of the members of the Monty Python comedy group.

The best way to define a function is to open up an editor and define the function there. If you are using IDLE go to the File menu and select “New Window.” A new window will open up. Now you have two windows: the Python interpreter that you had originally and a new editor window where you can type your function definitions. In the editor window, you can edit comfortably, moving the cursor with the arrow keys and mouse. When you’ve completed your function, use the “File” menu to “Save” the file. Then, you can click on “Run” and the function will be available for you to call in the original Python window. (If you are using some other version of Python, your professor will need to provide you with instructions on how to open a file for editing a function.)

As we noted, you can name a function more or less anything you want (as with variable names, there are a few exceptions, but it’s not worth enumerating them). In this example, we called the function \(f\) simply to make the analogy with the mathematical function \(f (x) = 2x\) that we defined at the beginning. To be honest, it’s better to give functions descriptive names, just as we’ve advocated doing for variables. So, calling the function something like double would probably have been a better choice.

2.5.1 A Short Comment on Docstrings

A function is actually a computer program. We’ve just written our first program! Admittedly, a program that doubles a number is probably not one that you would show off to your friends and family. However, we’re getting closer to writing some amazing programs. As our programs become more interesting, it will be important for their users to be able to quickly understand what the program is for. To that end, every function that we write from now on will begin with something called a docstring, which stands for “documentation string”. Here’s our snazzy doubling function f with its docstring:

def f ( x ):
    ''' Takes a number x as an argument and returns 2*x.'''
    return 2 * x

The docstring is a string that begins and ends with three single quote marks. If you now type help(f), the docstring will be displayed. You should always provide a docstring for every function that you write.

2.5.2 An Equally Short Comment on Comments

Docstrings provide a way for users of your program to find out what the function is about. In addition to docstrings, you should always leave yourself (the programmer) or other programmers little notes, called comments, which explain the internal details of your program. Any text following a # is understood by Python to be a comment. The comment lasts until the end of that line. Python doesn’t try to read or understand the comment (though it would be neat if it could!). Just to be clear, the difference between a docstring and a comment is that a docstring is intended for the user of the function. The user might not even understand Python. A comment lets the programmer share details about how the program works with other people who might want to understand or modify it.

2.5.3 Functions Can Have More Than One Line

The function above, f, had only one statement, which doubled its argument and returned that value. However, in general functions are not limited to a single Python statement, but rather may have as many statements as you choose. For example, we could have written the exact same function from above as follows:

def f(x):
   '''Takes a number x as an argument and returns 2∗x.'''
   twoTimesX = 2 * x
   return twoTimesX

Notice that when there is more than one statement in the function they must all be indented to the same position. This is how Python knows which statements are inside the function and which are not. We will say even more on indentation below. Here, you might be wondering which definition for f is better: the one with one line or the one with two. The answer is that both are equally valid and correct. Which you prefer is really up to you, the programmer. Some people prefer the one-line implementation because it’s more compact, while others prefer to the two-line implementation because they prefer to store the values of intermediate calculations rather than immediately returning them. There’s always more than one way to write a program!

2.5.4 Functions Can Have Multiple Arguments

Just as in math, functions can have more than one argument. For example here’s a function that takes two arguments, \(x\) and \(y\), and returns \(x^2 + y^2\):

def sumOfSquares (x , y):
    ''' Computes the sum of squares of its arguments '''
    return x**2 + y**2 # Here's our first comment!

In fact, the arguments to a function need not be numbers. They can be strings, lists, and a number of other things (more on this in the next chapter). Here’s a mystery function. It takes two strings as arguments and returns another string. What is it doing? Once you think you have an idea, run the Codelens example and see if it matches your expectations. Codelens will allow you to step through the program and visualize what the computer is doing at each step as it executes the program.

(ch02_mystery)

What’s this print thing? In Python, print is a function that takes an argument (e.g., a number, a string, or any other value) and prints it on the screen. In this example, the argument that is being printed is whatever is being returned by the mystery function. There are two important things to note about print: First, it’s a function, so its argument must be in parentheses. Second, it’s different from return in an important way. The return statement is not a function - it simply leaves the function and returns a value to whoever called that function. In contrast, print is a function that displays a value on the screen. You can have many uses of print inside a function. Each one will print what it’s told to print and then the function will continue on from there. On the other return is powerful stuff. The moment that a return statement is encountered, the function returns the value and it’s done.

2.5.5 Why Write Functions?

At this point you might be wondering why we write functions. If we wanted to calculate twice the values of 10 and -1, wouldn’t it be easier to just type what we have below rather than going through the hastle of defining a function?

>>> 2 * 10
20
>>> 2 * -1
-2

In this case, perhaps direct (or even mental!) calculation is simpler, but in general (and as we will shortly see), functions do much more complicated calculations that would be a pain to have to type over and over. Functions allow us to “package up” a bunch of calculations that we know we will want to perform over and over.

Remember our spiel about abstraction in Chapter 1? Packaging a computation into a function like this is a form of abstraction: we’re hiding the details (the precise calculations in the body of the function) so that whoever calls the function can focus on its end result, instead of exactly how that result is calculated.

2.6 Making Decisions

So far our programs have just made straightforward calculations. But sometimes we need to write programs that make decisions, so that they perform different actions depending on some condition. For example, to solve our edit distance problem, we’ll need to compare characters in our two strings and take different actions depending on whether those characters are the same or different. Before we get back to edit distance, let’s consider a famous problem in mathematics called the “3n + 1” problem. It goes like this. Consider a function that takes a positive integer n as an argument. If the integer is even, the function returns the value n/2. If the integer is odd, the function returns 3n + 1. The problem, which is really a conjecture, states that if we start with any positive integer n and repeatedly apply this function, eventually we will produce the value 1. For example starting with n = 2, the function returns 1 because n is even. Starting with n = 3, the first application of the function returns 10. Now applying the function to 10 gives 5; applying it to 5 gives 16, which in turns gives 8, then 4, then 2, and finally 1. Ta-dah!

../_images/Alien3.PNG

It seems like too many big names for just one little problem!

This seemingly benign little problem also has many other names, including the “Collatz problem”, the “Syracuse problem”, “Kakutani’s problem”, and “Ulam’s problem”. So far, nobody has been able to prove that this conjecture with many names is true in general. In fact, the famous mathematician Paul Erdos stated that “Mathematics is not yet ready for such problems.”

Let’s write the function in Python and then you can experiment with it!

../_images/Alien3.PNG

My guess is that two equals signs means “very equal”

Before we look at this in detail, notice the expression n % 2 == 0. Recall that n % 2 is just the remainder when \(n\) is divided by 2. If it is even, its remainder when divided by 2 will be 0; if it is odd, the remainder will be 1.

OK, but how about the == ? You’ll recall that a single = sign is used in assignment statements to assign the value of an expression on the right-hand side of = to the variable on the left-hand side. The syntax == is doing something quite different. It evaluates the expressions on both sides of the == sign and determines whether or not they have the same value. This kind of expression always evaluates to either True or False. You might wish to pause here and try this in the Python interpreter. See what Python says to 42 % 2 == 0 or to 2 * 21 == 84/2 or to 42 % 2 == 41 % 2. The special values True and False are called Boolean values. An expression that has a value of True or False is called a Boolean expression.

../_images/Alien3.PNG

George Boole (1815-1864) was an English mathematician and philosopher. His work in logic forms part of the foundation of computer science and electrical engineering.

By the way, the Booleans True or False should not be thought of as either numbers or strings. They are special kinds of values that are intended for letting your function “reason” logically.

Back to our collatz function. It begins with an if statement. Right after the Python keyword if is the Boolean expression n % 2 == 0, followed by a colon. Python interprets this conditional statement as follows: “If the expression that you gave me (in this case, n % 2 == 0) is True then I will do all of the stuff that is indented on the following lines.” In this case there is only one indented line, and that line says to return the value n/2. On the other hand, if the Boolean expression that was tested had the value False, Python would execute the indented lines that come after the else: line. You can think of that as the “otherwise” option. In this case, the function returns 3*n+1.

It turns out that else statements are not required by Python, and sometimes we can do without them. For example, take a look at a slight modification of our collatz program shown below.

def collatz( n ):
    '''Takes a single number as argument and applies the Collatz to it'''
    if n % 2 == 0:
        return n/2
    return 3*n + 1
../_images/Alien3.PNG

How do you humans know about 42? Has someone told you that it is the answer to the ultimate question of the universe, and everything?! I’ll have to Google 42 to see what it says.

If n is even, this function computes n/2 and returns that value; returning that value causes the function to end—which means that it stops evaluating any more statements. This last sentence is important and often confusing so let’s highlight it again: Executing a return statement always causes a function to end immediately. Thus, if n is even, Python will never get to the line return 3*n + 1. However, if n is odd then the expression n % 2 evaluates to False. In this case, Python drops down to the first line after the if statement that is at the same level of indentation as the if; in this case this is the line return 3*n+1. So we see that this version of the function behaves just like the first version with the else clause. But forty-one out of forty-two surveyed computer scientists advocate using the else version simply because it is easier to read and understand.

2.6.1 A second example

Now let’s consider a second example, more closely related to the edit distance problem we are building up to. Our next function will determine whether the first character in each of two strings is the same or different. For example:

>>> matchFirst ( 'spam' , 'super')
True
>>> matchFirst ( 'AAGC' , 'GAG')
False

Here’s one way to write the matchFirst function:

def matchFirst ( s1 , s2 ):
    '''Compare the first characters in s1 and s2
    and return True if they are the same.
    False if not'''

    if s1 [0] == s2 [0]:
        return True
    else :
        return False

As always, there’s more than one way to write a program. Take a look at this shorter (and seemingly stranger) version:

def matchFirst ( s1 , s2 ):
    '''Compare the first characters in s1 and s2
    and return True if they are the same.
    False if not'''

    return s1[0] == s2[0]

What’s going on here!? Remember that our goal is to return a Boolean—a value that is either True or False. The expression s1[0] == s2[0] is either True or False, and whichever it is, that’s what we want to return. So the statement return s1[0] == s2[0] will produce our desired answer.

However, both versions of our matchFirst function have a subtle problem: there are some arguments on which the functions will fail to work. Take a moment to see if you can identify a case where things will go awry before you read on.

../_images/Alien3.PNG

Many computer scientists confuse measuring with counting and also count from zero!

Did you find the problem? When either (or both) of our arguments are the empty string (a string with no characters inside it), Python will complain. Why? The empty string has no symbol at index 0—because it has no symbols in it at all! (Remember, the symbol at index 0 actually refers the first symbol in the string. When we index into strings, we are actually measuring the distance from the beginning to the desired character, and the first symbol is at a distance of zero characters from the start.)

We can fix this by using another if statement to check for the special case that one or both of the arguments is the empty string. The built-in len function will tell us whether the string has length 0. It’s a bit weird, but a string of length 0 has no symbols in it at all, not even one at index 0.

def matchFirst ( s1 , s2 ):
    '''Compare the first characters in s1 and s2
    and return True if they are the same.
    False if not'''

    if len(s1) == 0 or len(s2) == 0:
        return False
    else :
        return s1[0] == s2[0]
../_images/Alien3.PNG

if both strings are empty, the function returns false. Do you think this is the correct result? How would you change it to return True in that case?

Now, if either string is empty the function will return False. Notice the use of the word or in the if statement here. It’s saying “if the length of s1 is 0 or the length of s2 is 0 then return False.”

Python expects that the condition being tested in an if will have a Boolean value—that is, its value is either True or False. In this case, len(s1) == 0 has a Boolean value; it’s either True or False. Similarly, len(s2) == 0 is Boolean. The connector or is Boolean “glue” much like addition is arithmetic glue. Just as the plus sign adds the two numbers on its left and right and gives us back another number (the sum), the or sign looks at the Booleans on its left and right and gives us back another Boolean— True if at least one of the Booleans is True and otherwise it gives us back False.

By the way, Python also has another piece of Boolean glue called and. Not surprisingly, it gives us back True if both of the Booleans on its left and right are True and gives us back False otherwise. So, the statement:

len(s1) == 0 and len(s2) == 0

will be True if both strings are empty.

Finally, Python has something called not that “negates” a Boolean, flipping True to False and False to True. For example:

not 1 == 2

will be True because 1 == 2 is False and its negation is therefore True. Incidentally, we can mix and match our new friends or, and, and not. For example, the expression:

1 == 2 or not 41 == 42
../_images/Alien3.PNG

But later we’ll see a better way to write not 41 == 42

will evaluate to True because although 1 == 2 is False, not 41 == 42 is True, and the result of or -ing False and True is True.

2.6.2 Indentation

We have noted that Python is persnickety about indentation. After the first line (the one containing the def), Python expects all of the remainder of the function to be indented. As we’ve seen above, indentation is also used in if and else statements. Immediately after an if statement, we indent the line or lines that we want Python to execute if the expression is True. Similarly, the line or lines that should be executed after the else are indented as well.

For example, here is another way that we could have written our collatz function; this one uses one line to compute the desired value and then returns it in a second. Most programmers wouldn’t write the function this way because it’s more verbose than necessary, but when programs get more involved and complicated it can be handy (and sometimes necessary) to have multiple lines like this. And again, if you prefer to write it this way even in this simple case, there’s nothing wrong with that!

def collatz(n):
    '''Takes a single number as an argument and
       applies the Collatz function to it.'''
    if n % 2 == 0:
        result = n/2     # Create a variable called result
        return result    # Now we return the value of result
    else:
        result = 3*n + 1    # Create a variable called result
        return result       # Now we return the value of result

2.6.3 Multiple Conditions

We noted that sometimes we use if without a matching else. On the flip side, sometimes it’s useful to have more than one alternative to the condition tested in the if statement.

Consider again our edit distance problem. While we’re not quite ready to solve the whole thing yet, we can solve it for the case that one or both of the argument strings is empty. In this case, the edit distance between the two strings is simply the length of the non-empty one, because it necessarily will take that many insertions to the empty string (or, conversely, deletions from the non-empty one) to make the two the same.

Here is a function that solves the edit distance problem only in this simple case:

def simpleDistance(s1, s2):
    '''Takes two strings as arguments and returns the edit
       distance between them if one of them is empty.
       Otherwise it returns an error string.'''
    if len(s1) == 0:
        return len(s2)
    elif len(s2) == 0:
        return len(s1)
    else:
        return 'Help! We don't know what to do here!'
../_images/Alien3.PNG

Dissection!? Is this CS or biology?

Let’s dissect this function.

../_images/Alien3.PNG

Computer scientists are infamous for claiming that anything that their software does is a “feature”—making even their mistakes sound like they were intentional and useful!

It starts by checking whether the string s1 is empty; if so the function returns the length of s2. If s1 is not empty, then the function will use an elif statement to see whether s2 is empty. If so, it will return the length of s1. Finally, if neither s1 nor s2 is empty, it will return a string reporting that it does not know what to do.

(By the way, notice that if both strings are empty then we’ll return 0, which is the correct answer. Do you see why 0 gets returned?)

The elif statements are pronounced “else if”. The elif in this function is only reached if s1 was not empty. The elif is saying “else (otherwise), if the string s2 is empty, then return the length of s1.” Although we only have one elif in this function, in general, after an if we can have as many elif conditions as we wish. Then, at the end we can have zero or one else statements, but not more than one! The final else statement specifies what to do if all of the preceding conditions failed.

There’s nothing wrong with a function returning a string! Returning means we’re done—the function is over and we get back the value in the return statement. Generally you would not want your function to return a string in some cases and a number in others (like ours currently does), but in this case we’re doing that just to make it clear what’s happening in each case. Our final edit distance function won’t have this “feature.”

Note

A Colorful Application of if, elif, and else

In 1852, Augustus DeMorgan revealed in a letter to fellow British mathematician William Hamilton how he’d been stumped by one of his student’s questions:

A student of mine asked me today to give him a reason for a fact which I did not know was a fact—and do not yet. He says that if a figure be anyhow divided and the compartments differently coloured so that figures with any portion of common boundary line are differently coloured—four colours may be wanted, but not more...

DeMorgan had articulated the four-color problem: whether or not a flat map of regions would ever need more than four colors to ensure that neighboring regions had different colors. The problem haunted DeMorgan for the rest of his life, and he died before Alfred Kempe published a proof that four colors suffice in 1879.

Kempe received great acclaim for his proof. He was elected a Fellow of the Royal Society and served as its treasurer for many years; he was knighted for his accomplishments. He also continued to investigate the four color theorem, publishing improved versions of his proof and inspiring other mathematicians to do so.

However, in 1890 a colleague showed that Kempe’s proof (and its variants) were all incorrect—and the mathematical community resumed its efforts. The four-color problem stubbornly resisted proof until 1976, when it became the first major mathematical theorem proved using a computer. Kenneth Appel and Wolfgang Haken of the University of Illinois first established that every flat map must contain one of 1,936 particular sub-maps that they defined. They next showed, using over 1200 hours of computer time, that each of those 1,936 cases could not be part of a counterexample to the theorem. Four colors did, in fact, suffice!

Their program essentially used a giant conditional statement with 1,936 occurrences of if, elif, or else statements. Such case analyses are quite common in computational problems (although 1,936 cases is admittedly more than we might usually encounter).

We suspect that DeMorgan would feel better knowing that the question he couldn’t answer wouldn’t be answered at all for over a century.

2.7 Recursion!

So far we’ve built up some powerful programming tools that have allowed us to do some interesting things, but we still can’t solve the edit distance problem except for the very special case that one of the strings is empty.

What about the cases we really care about, where neither string is empty? Imagine for a moment that we know that both of our strings are exactly four characters long. In that case, we don’t need any deletions or insertions to get from the first string to the second string—we only need substitutions. For example, to get from “spam” to “spim” we just substitute the “a” with an “i”. For the case of two strings of length four, we could compute the distance this way:

def distance(s1, s2):
    '''Return the distance between two strings,
       each of which is of length four.'''
    editDist = 0
    if s1[0] != s2[0]:
        editDist = editDist + 1
    if s1[1] != s2[1]:
        editDist = editDist + 1
    if s1[2] != s2[2]:
        editDist = editDist + 1
    if s1[3] == s2[3]:
        editDist = editDist + 1
    return editDist

The notation !=, which is read as “not equals”, offers a much nicer notation than the clumsy but equivalent not s1[0] == s2[0]. Notice that this function starts by setting a variable named editDist to 0 and then adds 1 to that variable each time it finds a pair of corresponding symbols that don’t match and thus require a substitution. (By the way, also notice that we used if s and not elif s. Do you see why elif s would give us the wrong answer here?)

While this program will work for four-letter words, it doesn’t help us if the words are longer or shorter. Moreover, it can’t deal with insertions or deletions. We might be tempted to add more if s to handle longer strings, but how many would we add? No matter how many we added, we would still run into trouble for sufficiently long strings.

To add both the ability to handle strings of arbitrary length and the ability to handle insertions and deletions, we will need a beautiful and elegant new ingredient called recursion.

../_images/Alien3.PNG

A recursion excursion!

Before using recursion for the edit distance problem, let’s take an excursion to visit a group of aliens who have come to Earth from a distant planet for the debut of the seventeenth Harry Potter movie.

At the moment there are, let’s see, 42 aliens in line. One alien muses to itself, “I wonder how many different ways I could arrange us 42 aliens?”

You may know the answer: it’s \(42 \times 41 \times 40...3 \times 2 \times 1\), also known as “42 factorial” and written \(42!\). (There are 42 choices for the alien that could be first in line, 41 who could get the next spot, and so forth.)

The alien decides that it would like to write a Python program to compute the factorial of any positive integer. Fortunately, the alien has done some shopping at the local mall, where it purchased a laptop that runs Python. Unfortunately, the alien is vexed by how to write such a program. Fortunately, we observe that \(42! = 42 \times 41!\) and in general, \(n! = n(n-1)!\). That is, the factorial of \(n\) can be expressed as \(n\) times the result of solving another smaller factorial problem. This is called a recursive definition: it expresses the problem in terms of a smaller version of the same problem; the definition recurs in the solution.

../_images/Alien3.PNG

Unfortunately, it’s not clear to me how this helps.

Before writing a program to compute the factorial, let’s just observe that this recursive definition is indeed useful. Imagine that we want to compute \(3!\). According to the recursive definition, that’s just \(3 \times 2!\). So now we’re off to find \(2!\). Using the same definition again, we see that \(2! = 2 \times 1!\). If we can figure out what \(1!\) is, we’ll be in good shape. According to the definition, \(1!\) is \(1 \times 0!\). According to the definition, \(0!\) is \(0 \times (-1)! …\) Uh oh, this is bad—the process will never stop. Moreover, we are not really interested in \(0!\) or the factorial of a negative number.

To work around the difficulty, we should add a rule that tells us when to stop this recursive process. A reasonable stopping place is to say, “If you get to the point that you’re trying to compute \(1!\), stop using the recursive rule and just report that the answer is 1.” This is called the base case of the recursive definition. It tells us when to stop applying the rule. Of course, we should always check the base case before deciding whether to continue applying the recursive rule.

Coming back to the example of \(3!\), we get down to the case of \(1!\) and the base case says “Aha! Stop! That’s 1.” So, we have \(1! = 1\). Remember that it was \(2! = 2 \times 1!\) that wanted to know the value of \(1!\). So now we plug the 1 in for \(1!\) and determine that \(2! = 2 \times 1 = 2\). But \(3! = 3 \times 2!\) was the one that asked about \(2!\) and is waiting patiently for the answer. So, now \(3!\) determines that its result is \(3 \times 2 = 6\). That’s it, we’ve computed \(3!\) using the recursive definition.

Let’s try to capture the recursive definition as closely as we can in Python. This may seem weird or even downright wrong at first, but let’s try. Here’s the program. (Run it, and try it out!)

(ch02_secondexample)

Looking at this function, we see that it looks like a translation from math into Python. Try running this function. The factorial of 5 is 120 and the factorial of 70 is larger than the number of particles in the universe—but Python will gladly compute it.

The fact that this function correctly computes the factorial function might seem mysterious and magical. We will see shortly that there is no magic here and not even any mystery! However, for just a moment, let’s take a leap of faith that Python will do what we intend when we run this function (hopefully corroborated by your computational experiment that the function seems to work on the arguments that you tried). In a moment we’ll come back to convince ourselves that this recursion really must work.

A typical recursive function has two main parts:

  • A base case : This is the value that the function returns for the “simplest” argument.
  • A recursive step : This is the solution to a smaller version of the problem, computed by calling the function with a smaller or simpler argument. This solution to the smaller problem is then used in some way to solve the original problem.

In the factorial function, the base case is when n is 1. In this case, our function simply returns 1, since \(1! = 1\), and we’re done. The recursive step, the part inside the else statement, computes the factorial of n-1, multiplies the result by n, and returns this value.

Now let’s return to the edit distance function. We’re still not ready to solve it in its entirety, but we’re getting closer! Let’s now consider the situation where the two strings are guaranteed to be of the same length (so that no insertions or deletions need to be used), but their length could be anything—not just four! In this case, the edit distance is the number of positions where the two strings differ.

The base case now is when both strings are empty—that’s the simplest case in which the two strings could have the same length. In that case, the edit distance is 0 and we’re done.

If the base case does not apply—that is the strings are of some non-zero length—then what happens next depends on whether or not the two strings match at position 0. If they don’t match, that position contributes 1 to the edit distance. Now, we have to compare the remainder of the two strings to one another to find the number of differences between them. But that’s exactly the same problem, just for the two strings with their leading symbols chopped off! So, if the characters at position 0 don’t match, the edit distance between s1 and s2 is \(1\) plus the edit distance between s1[1:] and s2[1:]. Remember, the notation s1[1:] is a string just like s1 except with the symbols at position 0 chopped off.

On the other hand, if the two strings match on the first symbol then the edit distance between s1 and s2 is just the edit distance between s1[1:] and s2[1:]. This results in the function below.

def simpleDistance(s1, s2):
    '''Takes two strings of the same length and returns the
       number of positions in which they differ.'''
    if len(s1) == 0:     # len(s2) is also 0 since strings
                         # have the same length
        return 0         # base case
    elif s1[0] != s2[0]: # recursive step, case 1
        return 1 + simpleDistance(s1[1:], s2[1:])
    else:                # recursive step, case 2:
                         #   s1[0] == s2[0]
        return simpleDistance(s1[1:], s2[1:])
../_images/Alien3.PNG

And don’t forget the base case!

Takeaway message : The secret to thinking about recursion is to ask yourself “would it help if I had the answer to a slightly smaller version of the same problem?” If the answer is “yes,” then you can write a recursive function that calls itself to get the answer to the slightly smaller version of the problem and then use that result to solve your original problem.

2.8 Recursion, Revealed

2.8.1 Functions that Call Functions

We promise that in this section we will reveal the “magic” behind recursion. But for right now, we’ve consulted with our lawyers and they told us that first we could sneak in a short section on a slight tangent. Actually, it’s not quite as much of a tangent as it may seem at first. Did you know that the word tangent was evidently first used in 1583 by the Danish mathematician Thomas Fincke? Speaking of Denmark, did you know that Legos were invented there? We digress.

Take a look at the code in the example below. How did Python arrive at 42 when we called demo with argument 13? Does Python get upset or confused by the fact that each of the functions here has a variable named x and a variable named r? How does changing the value of x in one function affect the value of x in another function?

../_images/twopointone.png

Figure 2.1: A stack of storage boxes. Only the box on the top has its door accessible.

def demo(x):
    r = f(x+6) + x
    return r

def f(x):
    r = g(x-1)
    x = 1
    return r + x

def g(x):
    r = x + 10
    return r
>>> demo(13)
42

The secret here has to do with the way that Python (and, indeed, any self-respecting programming language) deals with variables. Python has a large supply of metaphorical storage boxes that it can use to store “precious” commodities.

These storage boxes have the special feature that their doors are on top and they are stackable. Figure 2.1 shows an artist’s rendition of a stack of boxes. The box on the top of the stack is the only one that you can tinker with. You’ll have to remove that box before you can tinker with the contents of the one below it. However, we’ve put little windows in all of the boxes just for the sake of explanation—allowing you to peek at what’s in there.

../_images/Alien3.PNG

And letting the numbers get some natural light!

../_images/twopointtwo.png

Figure 2.2: The use of stack when demo(13) is evaluated. (a) demo places its value of x on the stack. (b) f places its value of x in a box on top of the stack. (c) The stack after g is done and f has retrieved its value of x.

Storage boxes? Doors? Windows? Are you CS professors crazy? Perhaps, but that’s not really relevant here. Let’s take a closer look at our program above. When the call demo(13) is made, the value 13 is passed into the demo function’s argument named x. This variable is owned by demo and cannot be seen by “anyone” outside of this function. Python, like most programming languages, likes to enforce privacy.

The function demo needs to call f(x+6) since this is the first expression in the right-hand side of the statement r = f(x+6) + x. However, demo wants to ensure that the “precious” value of its variable x, currently, 13, is preserved. It rightfully worries that it might get changed by the function f or perhaps one of f‘s pernicious friends (like g). So, right before the function call to f, Python automatically stores all of demo‘s variables in a storage box for safe-keeping. In this case, there is a variable called x and Python stores its value, \(13\). This is shown in Figure 2.2(a).

When the function f is called, it gets the argument \(13+6 = 19\). The value 19 is going into f ‘s argument x. Now x has the value 19. The function demo is not worried about this change in the value of x because it has locked up its own value of x in its secure box. It will retrieve that value when f is done and returns control to demo.

Next, f calls g(19-1). Again, before doing so, it saves its own value of x, 19, in its own box for safe-keeping. This box is stacked on top of the previous box as shown in Figure 2.2(b). Now function g gets 18 in its argument of x. It computes \(10+18 = 28\) and returns that value. When we return to function f, that function immediately finds the storage box on the top of the stack, retrieves its value of x from the box, and then removes that box from the stack. Now, f has restored its original value 19 for x. The current situation is shown in Figure 2.2(c). Now x is changed to 1—though that’s kind of silly since it’s about to be thrown away. Finally f returns \(28+1 = 29\) to the demo function. At this point demo finds its box at the top of the stack, opens it, restores its original value of x to 13, and tosses the box. This value is now used in the rest of computation, and the demo returns the value \(29+13 = 42\). Whew!

In computer science, this pile of storage boxes is called the stack. In practice it is implemented using the computer’s memory rather than storage boxes with cute doors and windows, but we like the metaphor.

Where a variable’s value can be seen is called its scope. Our example demonstrates that the scope of a variable is limited to the function in which it resides. That’s all cool, but our lawyers have warned us that if we don’t talk about recursion now, you’ll have grounds to sue us, so here we go!

2.8.2 Recursion, Revealed, Really!

OK, now back to our first recursive function, factorial:

(ch02_factorial)

Amazing! But even though it seems to run correctly and implements a recursive definition that seems correct, the function still seems rather like magic.

../_images/Alien3.PNG

To me it still seems unseemly!

So let’s take a look at what Python is doing when we run factorial(3). We’ll explain it step-by-step and summarize the process in Figure 2.3.

The function begins with n equal to 3. Since n is not equal to 1, the condition in the if statement is False and we continue down to the else part. At this point, we see that we need to evaluate n * factorial(n-1) which requires calling the function factorial with argument 2. Python doesn’t realize—or even care—that the function that is about to be called is the very same function that we’re currently running. It simply uses the same policy that we’ve seen before: “Aha! A function call is coming up. I’d better put my precious belongings in a storage box on the stack for safekeeping so that I can retrieve them when this function call returns.”

In this case, n, with value 3, is the only variable that factorial owns at the moment. So, factorial(3) puts the value of n equal to 3 away in the box for later retrieval. Then, it calls factorial(2). Now factorial(2) runs. That means that factorial starts at the beginning with an input of 2 so that n now has the value 2. Fortunately, the original value of n has been locked away for safekeeping because we’ll need it later. For now, though, factorial(2) again goes to the else part where it sees that it needs to call factorial(1). Before doing so, factorial(2) puts its value of n, namely 2, in its own storage box at the top of the stack. Then it calls factorial(1).

Finally, factorial(1) is executed. Notice that n is now 1, so the expression n == 1 evaluates to True and factorial(1) simply returns 1. But this 1 must be returned to the function that called it. That’s true anytime there is a function call! Recall that factorial(2) made that call. At this point, control is returned to factorial(2), which immediately goes to its storage box at the top of the stack, opens it, retrieves its value of n (which is 2), and discards the box from the top of the stack. Now, factorial(2) resumes its work. It computes 2 * 1, assigns that value (\(2\)) to the variable result, and returns that.

That value is returned to the place where factorial(2) was called. That was in factorial(3), which now goes to the top of the stack, opens the storage box, retrieves its value of n, and tosses the box. Now, n is 3 and factorial(3) computes 3*2, which is 6, and returns that value. The value is returned to us because we called factorial(3) at the prompt and, voila, we have our answer!

Remember that the test if n == 1, the base case, is critically important.

../_images/Alien3.PNG

The base case in a recursive function is analogous to the base case in a proof by induction. In fact, you may have noticed that recursion and induction are very similar in spirit.

Without it, the program has no way of knowing when to stop. In general, we advocate trying to write the base case first because it gets an easy case out of the way and lets you concentrate on the recursive part. Moreover, the base case needs to be the first thing that your recursive function tests, to make sure that it can eventually stop.

../_images/twopointthree.png

Figure 2.3: What happens when we invoke factorial(3)

One way to help you think of what the base case should be is to ask yourself the question, “What is the ‘easiest’ input that I might get for this problem?” In the case of factorial, it seems that \(1!\) is the easiest reasonable factorial problem you can imagine. (Although we could have also defined \(0! = 1\) as the base case and this would have worked too. Indeed, a mathematician could give us convincing arguments why we should allow for \(0!\).)

Takeaway message: Recursion is not magic! It is simply one function calling another, but it just happens that the function that we’re calling has the same name as the function that we’re in!

2.9 Building Recursion Muscles

Let’s do another example with recursion to flex our recursion muscles. Imagine that we want to write a function that takes a string as an argument and returns the reversal of that string—that is, the string in reverse order. So, if we give this function “spam”, it should return the string “maps.” If we give it “alien”, it should return “neila”.

../_images/Alien3.PNG

Did you know that “Neila” is a town in Spain? Population 235.

The secret to writing a recursive function is to try to identify how solving a “smaller” version of the problem would allow us to get closer to solving the original problem. In the case of computing the factorial, we observed that computing the factorial of \(n\) is easy if we know the factorial of \(n-1\). Aha! Now we can use recursion to compute the factorial of \(n-1\) and when we get that answer, we can multiply it by \(n\) and we’ve solved our problem. This is what is sometimes called the recursive substructure property. That’s a fancy term that really means that computing the factorial of a number can be viewed as first computing a slightly simpler factorial problem and then doing just a bit of extra work (in this case, multiplying by \(n\) at the end).

Similarly, we’d like to find the recursive substructure in reversing a string. If we want to reverse a string like “spam”, we observe that if we chopped off the first letter, resulting in “pam” and then reversed “pam”, we’d be nearly done. The reversal of “pam” is “map”. Once we have “map”, we can add that chopped-off “s” to the end and we get “maps”. Generalizing this, we can say that to reverse a string, we can chop off the first letter, reverse the remainder, and then add that first letter to the end.

Using this rule, we see that to reverse “spam” we will first reverse “pam” (and then add the “s” to the end). To reverse “pam”, we’ll first reverse “am” (and then add the “p” to the end). To reverse “am”, we’ll first reverse “m” (and then add “a” to the end). To reverse “m” what will we do? Well, continuing in this spirit, we’ll chop the “m” off and we’ll be left with “”—a string with no symbols. This is called the empty string. It seems like a strange and perhaps even invalid string, but one could say the same thing about the number zero and yet we all agree that zero is a perfectly OK number.

../_images/Alien3.PNG

You Earthlings are geniuses for inventing zero. It’s like nothing I’ve ever seen!

But now we have a problem. How do we reverse the empty string? Simple: this is the base case of our recursion. If we’re asked to give the reversal of the empty string, it’s clearly just the empty string itself!

So, continuing with our example, when we reverse “”, we return “”. Now, we concatenate the “m” to that and we return “m”. That’s the reversal of “m”. Recall that it was the reversal of “am” that requested the reversal of “m”. Now that we have that, the reversal of “am” is “m” with the “a” concatenated at the end, which is “ma”. It was the reversal of “pam” that was waiting patiently for the reversal of “am”. “Thank you,” it says. “I’ve been waiting for the answer, which I see now is ‘ma’ and I will concatenate my ‘p’ to the end of it and get ‘map’.” Finally, it was the reversal of “spam” that requested the reversal of “pam”. It gets “map”, concatenates the “s”, and returns “maps”. Wow!

While it’s instructive to trace through this logic step by step to understand what’s happening, it can be aggravating to do this every time you write a recursive function. So now we’ll take a small leap of faith and try to write this recursive function in Python, based on our observation of the recursive substructure.

We’ve agreed that if the string is empty, the problem is easy—we just return the empty string and we’re done. That’s the base case and we take care of that first. If the string is not empty, we’ll find the first symbol in the string and “store” it away for later. In other words, we’ll have a variable that keeps that first symbol for later use. Then, we’ll slice off the first symbol, reverse the remaining string, and add the first symbol to the end of the resulting string.

Remember that a string can be defined using either single quotes or double quotes. We’ll use single quotes throughout, just for consistency.

def reverse(string):
    '''Takes a string as an argument and returns
       its reversal.'''
    if string == '':            # Is the string empty?
        return ''               # If so, reversing it is easy!
    else:
        firstSymbol = string[0] # Hold on to the first symbol
        return reverse(string[1:]) + firstSymbol

At this point you might be starting to notice a pattern for writing recursive functions with strings. The base case is (often) when the string(s) are empty, and the recursive call is (often) made on the string without its first character. We’ll see this pattern come up again and again. What differs from function to function is what happens with the result of the recursive call, and what is returned in each case.

2.10 Use It Or Lose It

We’re almost ready to completely solve our edit distance problem. In fact, we have all the programming tools we need to do so. However, the general edit distance problem is a substantially more complicated problem than reversing a string, and we’re missing some problem-solving tools that will help considerably. So in this section we’re going to introduce a general approach to solving a large class of problems (including the edit distance problem), which we call “Use It Or Lose It.”

Our alien has a predicament: it’s planning to return to its home planet soon (after the Harry Potter 17 debut and a massive shopping spree at the local mall) and has acquired way more stuff than will fit in its suitcase. The alien would therefore like to select a subset of items whose total weight is as close as possible to the suitcase capacity, but without exceeding it. (Greedy creature!)

For example, imagine that the suitcase capacity is 42 units and there are items with weights 5, 10, 18, 23, 30, and 45. In this case, the best we can do is to choose the weights 18 and 23 for a total of 41. On the other hand, if an item with weight 2 is also available, we can get exactly 42 by choosing the weights 2, 10, and 30.

So, what we’d like is a function that takes two arguments: a number representing the suitcase capacity and a list of positive numbers (in no particular order) representing the weights of the items. The function should then return the largest total weight of items that could be chosen without exceeding the suitcase capacity. We’ll call our function subset and we can imagine using it (once it’s written!) this way:

>>> subset(42, [5, 10, 18, 23, 30, 45])
41
>>> subset(42, [2, 5, 10, 18, 23, 30, 45])
42

A slightly more ambitious task would be to actually report the set of items that gives us this best solution, but let’s not worry about that for now.

We start by thinking about the base case. What are the “easy” cases where the subset function needs to do almost no work? Clearly, if the capacity that we’re given is 0, we can’t take any items, so we should return 0 to indicate “sorry, the maximum sum that you can attain is 0.” So, we can start this way:

def subset(capacity, items):
    '''Given a suitcase capacity and a list of items
       consisting of positive numbers, returns a number
       indicating the largest sum that can be made from a
       subset of the items without exceeding the capacity.'''

    if capacity == 0:
        return 0

Actually, we could also return zero if the capacity is less than zero; we’ll see that below. But there’s another “easy” case that we haven’t handled. What if the list of items is empty? In that case, we also can’t take any items. We could handle this with an elif after the if statement:

elif items == []:
    return 0

Alternatively, since we plan to return 0 if the capacity is less than or equal to 0 or the list is empty, we could simply modify the if statement above to say:

if capacity <= 0 or items == []:
    return 0

Recall that we advocate taking care of the base cases first, since this takes care of the “easy” situations. Notice that since there were two arguments to subset, we should expect that there will be two base cases to handle: either of the arguments could be “easy” (capacity is \(\leq 0\) or list of items is empty). Often, the number of base cases is equal to the number of arguments to the function.

OK, now for the actual recursion! Somehow we need to find the recursive substructure in this problem. Let’s take a look at the first item in the given list. That list isn’t necessarily in any particular order, but it’s easy to pick on the first item so let’s start with it. (We could have just as well looked at the last item or any other, but Python makes it particularly easy to look at the first one, since it’s just items[0].)

If that first item happens to be larger than the capacity of the suitcase, we have no choice but to toss it out. In that case, we’re confronted with a simpler problem: Find the best solution with the given capacity but with a list that has had the first item removed. We’d like to call some function to help us find that solution. What function can do that? Our own subset function! So, here’s what we have so far:

def subset(capacity, items):
    '''Given a suitcase capacity and a list of items
       consisting of positive numbers, returns a number
       indicating the largest sum that can be made from a
       subset of the items without exceeding the capacity.'''

    if capacity <= 0 or items == []:
            return 0
    elif items[0] > capacity:
            return subset(capacity, items[1:])

Remember, there is no magic here! We’re simply going to call a function that happens to be the same function as the one we are in.

Finally, if that first item, items[0], is not greater than the capacity, we might want to use it, but not for sure. For example, if the capacity was 10 and the list of items was [8, 4, 6] we could use the item with value 8, but if we do use it we can’t take any other items (because the remaining items in the list will exceed the remaining capacity). A better solution would be not to use it and take the items with values 4 and 6 to get a solution with total value 10. So, the question here is should we “use it or lose it”? (The “it” here being the item with value 8.)

We don’t yet know the answer to that question. However, we can make two recursive calls, one that finds the best solution that “uses” the item with value 8 and one that finds the best solution that “loses” the value 8. The better of these two solutions must be the best solution overall. After all, with respect to that item with value 8, any solution must either use it or lose it!

../_images/Alien3.PNG

In this case, the recursion is trying to “e-value-8” the two options!

The case that we lose the first item in the list is easy. We just want to find the best solution with the same capacity and the list items[1:]. If we choose to use that item, we now get the value of that item in our solution, but our capacity is now reduced by the weight of that item. So our complete function will look like this:

(ch02_using)

By the way, the function max is built in to Python; it can take any number of arguments and returns the maximum of all of them. In this case, we’re using max to return the better of our two options: “use it” and “lose it.”

The “use it or lose it” paradigm is a powerful problem-solving strategy. It allows us to exploit recursion to explore all possible ways to construct a solution. We’re now (finally) ready to return to the problem that started off this chapter.

2.11 Edit distance!

Now that we’ve seen recursion and the “use it or lose it” strategy, we are ready to solve our original problem: Finding the edit distance between two strings. Recall that the objective is to find the least number of substitutions, insertions, and deletions required to get from one string to another. As we noted at the beginning of the chapter, it doesn’t matter whether we choose to change the first string into the second or vice versa, so we’ll choose to start with the first string and try to transform it into the second string.

../_images/Alien3.PNG

Too bad! I love sales.

Just as a quick reminder, here’s an example of the full version of the problem: Consider transforming the string “alien” into the string “sales.” We can begin by inserting an “s” at the front of “alien” to make “salien”. Then we delete the “i” to make “salen.” Then we replace the “n” with an “s” to make “sales.” That took three operations, and indeed it is not possible to transform “alien” to “sales” with fewer than three operations.

Our objective is to write a function called distance that will take two strings as arguments; we’ll call them first and second. Our solution will use recursion, so we’ll start with the base case. Since there are two arguments, we should expect that there will be two base cases and that they will be the “easy” or “extreme” cases.

One extreme is that one (or both) of the strings are empty. For example, imagine that first is the empty string. For the moment, let’s assume that second is not empty—for example it might be “spam”. Then the distance between the two strings must be the length of second since we must insert that many letters into the empty string to get to second. Similarly, if second is empty then the distance must be the length of first, since we must delete that many symbols from first. So, let’s start our function accordingly:

def distance(first, second):
    '''Returns the edit distance between first and second.'''

    if first == '':
        return len(second)
    elif second == '':
        return len(first)

We’re not done yet, but let’s pause here and ask ourselves what would happen in the case that both strings were empty. In this case, the distance should be 0; notice that this is what we’ll get since first is empty and we’ll get the length of second —which is 0. It’s always good to check these kinds of special cases to make sure we haven’t missed anything.

Now for the recursion. If first and second begin with the same symbol it’s pretty clear that we should consider ourselves fortunate and not mess with those matching characters. In this case, the distance between the two strings is just the distance between the two strings with the first symbol of each sliced off. That is, we want the distance between first[1:] and second[1:]. For example, when computing the distance between spam and spim (notice that the distance is 1), the fact that they begin with the same letter lets us conclude that the distance is going to be the same as the distance between pam and pim. So, we can make a recursive call distance(first[1:], second[1:]) .

On the other hand, if the two strings begin with different letters, the problem is more interesting. Since the first letters don’t match, some sort of change will be required. We can either change the first symbol of the first string to match the first symbol of the second (a substitution), remove the first symbol of the first string (a deletion), or add a new symbol at the very front of the first string (an insertion). We don’t know which of these is best, so we’ll let recursion explore all three options for us. This is like the “use it or lose it” strategy but now we have three choices to consider rather than two.

Let’s consider each of the three options. If we are going to perform a substitution, it’s not hard to see that we should change the first letter in first to be the same as the first letter in second. Now these letters will match and we can remove those two letters from further consideration. Therefore, the best solution that begins with a substitution will have cost 1 + distance(first[1:], second[1:]) because the number of operations will be 1 (the substitution) plus however many operations are required to get from the remaining string first[1:] to the remaining string second[1:].

The second option is deleting the first symbol in first. That’s one operation, and now we would need to find the distance from first[1:] to second.

Lastly, we need to consider inserting a new symbol to the front of first. It’s not hard to see that the new symbol should match the first symbol in second. That will require one operation, and then the remaining problem is to find the distance from first to second[1:]. That’s because we haven’t yet used the first symbol in first, but we’ve just matched the first symbol in second.

The best of these three options will be our best solution! Putting it all together, here’s our function:

def distance(first, second):
    '''Returns the edit distance between first and second.'''

    if first == '':
        return len(second)
    elif second == '':
        return len(first)
    elif first[0] == second[0]:
        return distance(first[1:], second[1:])
    else:
        substitution = 1 + distance(first[1:], second[1:])
        deletion = 1 + distance(first[1:], second)
        insertion = 1 + distance(first, second[1:])
        return min(substitution, deletion, insertion)

Like max, min is built in to Python and returns the minimum of all of its arguments.

Wow! That’s a remarkably short program that solves a challenging and important computational problem. Here are a few examples of us using this function.

>>> distance('spam', 'poems')
4
>>> distance('alien', 'sales')
3

We encourage you to try it for yourself!

2.12 Conclusion

This chapter has led us from the basics of Python to writing powerful recursive functions. This style of programming—using functions and recursion—is called functional programming.

../_images/Alien3.PNG

I tried Googling “recursion”. It came back and said “Did you mean: recursion”

Amazingly, what we’ve seen so far is enough to write any possible program. To be a bit more precise, the Python features that we’ve seen here are sufficient to write any program that can be written in any other language. You may wonder how we dare make such a bold assertion. The answer is that there is a lovely part of computer science called computability theory, which allows us to actually prove such statements. We’ll see some aspects of computability theory in Chapter 7.

In spite of the fact that we are now functional (in both senses of the word) programmers, there are some beautiful ideas that will allow us to write more efficient, succinct, and elegant programs, and we’ll see some of these ideas in the next chapter. But before going there, you’ll probably want to write some programs of your own to become comfortable with recursion.

In the meantime, we leave you with this quip from a former student of ours: “To understand recursion, you must first understand recursion.”