Chapter 5 Conditionals and recursion
The main topic of this chapter is the if statement, which executes different code depending on the state of the program. But first I want to introduce two new operators: floor division and modulus.
5.1 Floor division and modulus
The floor division operator,
>>> minutes = 105 >>> minutes / 60 1.75
But we don’t normally write hours with decimal points. Floor division returns the integer number of hours, dropping the fraction part:
>>> minutes = 105 >>> hours = minutes // 60 >>> hours 1
To get the remainder, you could subtract off one hour in minutes:
>>> remainder = minutes - hours * 60 >>> remainder 45
An alternative is to use the modulus operator,
>>> remainder = minutes % 60 >>> remainder 45
Also, you can extract the right-most digit or digits from a number. For example, x % 10 yields the right-most digit of x (in base 10). Similarly x % 100 yields the last two digits.
5.2 Boolean expressions
A boolean expression is an expression that is either true or false. The following examples use the operator ==, which compares two operands and produces True if they are equal and False otherwise:
>>> 5 == 5 True >>> 5 == 6 False
>>> type(True) <class 'bool'> >>> type(False) <class 'bool'>
The == operator is one of the relational operators; the others are:
x != y # x is not equal to y x > y # x is greater than y x < y # x is less than y x >= y # x is greater than or equal to y x <= y # x is less than or equal to y
Although these operations are probably familiar to you, the Python symbols are different from the mathematical symbols. A common error is to use a single equal sign (=) instead of a double equal sign (==). Remember that = is an assignment operator and == is a relational operator. There is no such thing as =< or =>.
5.3 Logical operators
There are three logical operators: and, or, and not. The semantics (meaning) of these operators is similar to their meaning in English. For example, x > 0 and x < 10 is true only if x is greater than 0 and less than 10.
n%2 == 0 or n%3 == 0 is true if either or both of the conditions is true, that is, if the number is divisible by 2 or 3.
Finally, the not operator negates a boolean expression, so not (x > y) is true if x > y is false, that is, if x is less than or equal to y.
Strictly speaking, the operands of the logical operators should be boolean expressions, but Python is not very strict. Any nonzero number is interpreted as True:
>>> 42 and True True
This flexibility can be useful, but there are some subtleties to it that might be confusing. You might want to avoid it (unless you know what you are doing).
5.4 Conditional execution
In order to write useful programs, we almost always need the ability to check conditions and change the behavior of the program accordingly. Conditional statements give us this ability. The simplest form is the if statement:
if x > 0: print('x is positive')
if statements have the same structure as function definitions: a header followed by an indented body. Statements like this are called compound statements.
There is no limit on the number of statements that can appear in the body, but there has to be at least one. Occasionally, it is useful to have a body with no statements (usually as a place keeper for code you haven’t written yet). In that case, you can use the pass statement, which does nothing.
if x < 0: pass # TODO: need to handle negative values!
5.5 Alternative execution
A second form of the if statement is “alternative execution”, in which there are two possibilities and the condition determines which one runs. The syntax looks like this:
if x % 2 == 0: print('x is even') else: print('x is odd')
If the remainder when x is divided by 2 is 0, then we know that x is even, and the program displays an appropriate message. If the condition is false, the second set of statements runs. Since the condition must be true or false, exactly one of the alternatives will run. The alternatives are called branches, because they are branches in the flow of execution.
5.6 Chained conditionals
Sometimes there are more than two possibilities and we need more than two branches. One way to express a computation like that is a chained conditional:
if x < y: print('x is less than y') elif x > y: print('x is greater than y') else: print('x and y are equal')
elif is an abbreviation of “else if”. Again, exactly one branch will run. There is no limit on the number of elif statements. If there is an else clause, it has to be at the end, but there doesn’t have to be one.
if choice == 'a': draw_a() elif choice == 'b': draw_b() elif choice == 'c': draw_c()
Each condition is checked in order. If the first is false, the next is checked, and so on. If one of them is true, the corresponding branch runs and the statement ends. Even if more than one condition is true, only the first true branch runs.
5.7 Nested conditionals
One conditional can also be nested within another. We could have written the example in the previous section like this:
if x == y: print('x and y are equal') else: if x < y: print('x is less than y') else: print('x is greater than y')
The outer conditional contains two branches. The first branch contains a simple statement. The second branch contains another if statement, which has two branches of its own. Those two branches are both simple statements, although they could have been conditional statements as well.
Although the indentation of the statements makes the structure apparent, nested conditionals become difficult to read very quickly. It is a good idea to avoid them when you can.
Logical operators often provide a way to simplify nested conditional statements. For example, we can rewrite the following code using a single conditional:
if 0 < x: if x < 10: print('x is a positive single-digit number.')
The print statement runs only if we make it past both conditionals, so we can get the same effect with the and operator:
if 0 < x and x < 10: print('x is a positive single-digit number.')
For this kind of condition, Python provides a more concise option:
if 0 < x < 10: print('x is a positive single-digit number.')
It is legal for one function to call another; it is also legal for a function to call itself. It may not be obvious why that is a good thing, but it turns out to be one of the most magical things a program can do. For example, look at the following function:
def countdown(n): if n <= 0: print('Blastoff!') else: print(n) countdown(n-1)
If n is 0 or negative, it outputs the word, “Blastoff!” Otherwise, it outputs n and then calls a function named countdown—itself—passing n-1 as an argument.
What happens if we call this function like this?
The execution of countdown begins with n=3, and since n is greater than 0, it outputs the value 3, and then calls itself...
The execution of countdown begins with n=2, and since n is greater than 0, it outputs the value 2, and then calls itself...The execution of countdown begins with n=1, and since n is greater than 0, it outputs the value 1, and then calls itself...The execution of countdown begins with n=0, and since n is not greater than 0, it outputs the word, “Blastoff!” and then returns.
The countdown that got n=3 returns.
3 2 1 Blastoff!
As another example, we can write a function that prints a string n times.
def print_n(s, n): if n <= 0: return print(s) print_n(s, n-1)
The rest of the function is similar to countdown: it displays s and then calls itself to display s n−1 additional times. So the number of lines of output is 1 + (n - 1), which adds up to n.
For simple examples like this, it is probably easier to use a for loop. But we will see examples later that are hard to write with a for loop and easy to write with recursion, so it is good to start early.
5.9 Stack diagrams for recursive functions
In Section 3.9, we used a stack diagram to represent the state of a program during a function call. The same kind of diagram can help interpret a recursive function.
Every time a function gets called, Python creates a frame to contain the function’s local variables and parameters. For a recursive function, there might be more than one frame on the stack at the same time.
Figure 5.1 shows a stack diagram for countdown called with n = 3.
The four countdown frames have different values for the parameter n. The bottom of the stack, where n=0, is called the base case. It does not make a recursive call, so there are no more frames.
As an exercise, draw a stack diagram for
5.10 Infinite recursion
If a recursion never reaches a base case, it goes on making recursive calls forever, and the program never terminates. This is known as infinite recursion, and it is generally not a good idea. Here is a minimal program with an infinite recursion:
def recurse(): recurse()
File "<stdin>", line 2, in recurse File "<stdin>", line 2, in recurse File "<stdin>", line 2, in recurse . . . File "<stdin>", line 2, in recurse RuntimeError: Maximum recursion depth exceeded
This traceback is a little bigger than the one we saw in the previous chapter. When the error occurs, there are 1000 recurse frames on the stack!
If you encounter an infinite recursion by accident, review your function to confirm that there is a base case that does not make a recursive call. And if there is a base case, check whether you are guaranteed to reach it.
5.11 Keyboard input
The programs we have written so far accept no input from the user. They just do the same thing every time.
Python provides a built-in function called input that
stops the program and
waits for the user to type something. When the user presses Return or Enter, the program resumes and
>>> text = input() What are you waiting for? >>> text 'What are you waiting for?'
>>> name = input('What...is your name?\n') What...is your name? Arthur, King of the Britons! >>> name 'Arthur, King of the Britons!'
If you expect the user to type an integer, you can try to convert the return value to int:
>>> prompt = 'What...is the airspeed velocity of an unladen swallow?\n' >>> speed = input(prompt) What...is the airspeed velocity of an unladen swallow? 42 >>> int(speed) 42
But if the user types something other than a string of digits, you get an error:
>>> speed = input(prompt) What...is the airspeed velocity of an unladen swallow? What do you mean, an African or a European swallow? >>> int(speed) ValueError: invalid literal for int() with base 10
When a syntax or runtime error occurs, the error message contains a lot of information, but it can be overwhelming. The most useful parts are usually:
>>> x = 5 >>> y = 6 File "<stdin>", line 1 y = 6 ^ IndentationError: unexpected indent
In this example, the problem is that the second line is indented by one space. But the error message points to y, which is misleading. In general, error messages indicate where the problem was discovered, but the actual error might be earlier in the code, sometimes on a previous line.
The same is true of runtime errors. Suppose you are trying to compute a signal-to-noise ratio in decibels. The formula is SNRdb = 10 log10 (Psignal / Pnoise). In Python, you might write something like this:
import math signal_power = 9 noise_power = 10 ratio = signal_power // noise_power decibels = 10 * math.log10(ratio) print(decibels)
Traceback (most recent call last): File "snr.py", line 5, in ? decibels = 10 * math.log10(ratio) ValueError: math domain error
The error message indicates line 5, but there is nothing wrong with that line. To find the real error, it might be useful to print the value of ratio, which turns out to be 0. The problem is in line 4, which uses floor division instead of floating-point division.
You should take the time to read error messages carefully, but don’t assume that everything they say is correct.
The time module provides a function, also named time, that returns the current Greenwich Mean Time in “the epoch”, which is an arbitrary time used as a reference point. On UNIX systems, the epoch is 1 January 1970.
>>> import time >>> time.time() 1437746094.5735958
Write a script that reads the current time and converts it to a time of day in hours, minutes, and seconds, plus the number of days since the epoch.
Fermat’s Last Theorem says that there are no positive integers a, b, and c such that
for any values of n greater than 2.
If you are given three sticks, you may or may not be able to arrange them in a triangle. For example, if one of the sticks is 12 inches long and the other two are one inch long, you will not be able to get the short sticks to meet in the middle. For any three lengths, there is a simple test to see if it is possible to form a triangle:
If any of the three lengths is greater than the sum of the other two, then you cannot form a triangle. Otherwise, you can. (If the sum of two lengths equals the third, they form what is called a “degenerate” triangle.)
Exercise 4 What is the output of the following program? Draw a stack diagram that shows the state of the program when it prints the result.
def recurse(n, s): if n == 0: print(s) else: recurse(n-1, n+s) recurse(3, 0)
The following exercises use the turtle module, described in Chapter 4:
Read the following function and see if you can figure out what it does (see the examples in Chapter 4). Then run it and see if you got it right.
def draw(t, length, n): if n == 0: return angle = 50 t.fd(length*n) t.lt(angle) draw(t, length, n-1) t.rt(2*angle) draw(t, length, n-1) t.lt(angle) t.bk(length*n)
The Koch curve is a fractal that looks something like Figure 5.2. To draw a Koch curve with length x, all you have to do is
The exception is if x is less than 3: in that case, you can just draw a straight line with length x.
Are you using one of our books in a class?We'd like to know about it. Please consider filling out this short survey.