Conditionals and Recursion

from os.path import basename, exists

def download(url):
    """Download a file if it isn't already here, and return its filename."""
    filename = basename(url)
    if not exists(filename):
        from urllib.request import urlretrieve

        local, _ = urlretrieve(url, filename)
        print("Downloaded " + str(local))
    return filename

download('https://github.com/porttack/working-in-python/raw/v3/working_in_python.py');
download('https://github.com/AllenDowney/ThinkPython/raw/v3/diagram.py');
download('https://github.com/ramalho/jupyturtle/releases/download/2024-03/jupyturtle.py');

import working_in_python

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. And with the if statement we’ll be able to explore one of the most powerful ideas in computing, recursion.

But we’ll start with three new features: the modulus operator, boolean expressions, and logical operators.

5.1. Integer division and modulus#

Recall that the integer division operator, //, divides two numbers and rounds down to an integer. For example, suppose the run time of a movie is 105 minutes. You might want to know how long that is in hours. Conventional division returns a floating-point number:

minutes = 105
minutes / 60

But we don’t normally write hours with decimal points. Integer division returns the integer number of hours, rounding down:

minutes = 105
hours = minutes // 60
hours

To get the remainder, you could subtract off one hour in minutes:

remainder = minutes - hours * 60
remainder

Or you could use the modulus operator, %, which divides two numbers and returns the remainder.

remainder = minutes % 60
remainder

The modulus operator is more useful than it might seem. For example, it can check whether one number is divisible by another – if x % y is zero, then x is divisible by y.

Also, it 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.

x = 123
x % 10

x % 100

Finally, the modulus operator can do “clock arithmetic”. For example, if an event starts at 11 AM and lasts three hours, we can use the modulus operator to figure out what time it ends.

start = 11
duration = 3
end = (start + duration) % 12
end

The event would end at 2 PM.

5.2. Boolean Expressions#

A boolean expression is an expression that is either true or false. For example, the following expressions use the equals operator, ==, which compares two values and produces True if they are equal and False otherwise:

5 == 5

5 == 7

A common error is to use a single equal sign (=) instead of a double equal sign (==). Remember that = assigns a value to a variable and == compares two values.

x = 5
y = 7

x == y

True and False are special values that belong to the type bool; they are not strings:

type(True)

type(False)

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 to y

x >= y               # x is greater than or equal to y

x <= y               # x is less than or equal to y

5.3. Logical operators#

To combine boolean values into expressions, we can use logical operators. The most common are and, or, and not. The meaning of these operators is similar to their meaning in English. For example, the value of the following expression is True only if x is greater than 0 and less than 10.

x > 0 and x < 10

The following expression is True if either or both of the conditions is true, that is, if the number is divisible by 2 or 3:

x % 2 == 0 or x % 3 == 0

Finally, the not operator negates a boolean expression, so the following expression is True if x > y is False.

not x > y

Strictly speaking, the operands of a logical operator should be boolean expressions, but Python is not very strict. Any nonzero number is interpreted as True:

42 and True

This flexibility can be useful, but there are some subtleties to it that can be confusing. You might want to avoid it.

5.4. if statements#

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 is a Python keyword. if statements have the same structure as function definitions: a header followed by an indented statement or sequence of statements called a block.

The boolean expression after if is called the condition. If it is true, the statements in the indented block run. If not, they don’t.

There is no limit to the number of statements that can appear in the block, but there has to be at least one. Occasionally, it is useful to have a block that does nothing – 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!

The word TODO in a comment is a conventional reminder that there’s something you need to do later.

5.5. The `else` clause#

An if statement can have a second part, called an else clause. The syntax looks like this:

if x % 2 == 0:
    print('x is even')
else:
    print('x is odd')

If the condition is true, the first indented statement runs; otherwise, the second indented statement runs.

In this example, if x is even, the remainder when x is divided by 2 is 0, so the condition is true and the program displays x is even. If x is odd, the remainder is 1, so the condition is false, and the program displays x is odd.

Since the condition must be true or false, exactly one of the alternatives will run. The alternatives are called branches.

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, which includes an elif clause.

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”. There is no limit on the number of elif clauses. If there is an else clause, it has to be at the end, but there doesn’t have to be one.

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 if 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 if statement 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 can be difficult to read. I suggest you avoid them when you can.

Logical operators often provide a way to simplify nested conditional statements. Here’s an example with a nested 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 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.')

5.8. Recursion#

It is 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. Here’s an example.

def countdown(n):
    if n <= 0:
        print('Blastoff!')
    else:
        print(n)
        countdown(n-1)

If n is 0 or negative, countdown outputs the word, “Blastoff!” Otherwise, it outputs n and then calls itself, passing n-1 as an argument.

Here’s what happens when we call this function with the argument 3.

countdown(3)

The execution of countdown begins with n=3, and since n is greater than 0, it displays 3, and then calls itself.…

The execution of countdown begins with n=2, and since n is greater than 0, it displays 2, and then calls itself.…

The execution of countdown begins with n=1, and since n is greater than 0, it displays 1, and then calls itself.…

The execution of countdown begins with n=0, and since n is not greater than 0, it displays “Blastoff!” and returns.

The countdown that got n=1 returns.

The countdown that got n=2 returns.

The countdown that got n=3 returns.

A function that calls itself is recursive. As another example, we can write a function that prints a string n times.

def print_n_times(string, n):
    if n > 0:
        print(string)
        print_n_times(string, n-1)

If n is positive, print_n_times displays the value of string and then calls itself, passing along string and n-1 as arguments.

If n is 0 or negative, the condition is false and print_n_times does nothing.

Here’s how it works.

print_n_times('Spam ', 4)

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. Aside: Compare a `for` loop with recursion#

Consider these two code segments that do the same thing:

# (1) meow() with a for loop
def meow(n):
    for i in range(n):
        print("meow")

meow(3)

# (2) meow() with recursion
def meow(n):
    if n > 0:
        print("meow")
    meow(n-1)

meow(3)

Try running these using pythontutor.com:

Visualize the for-loop version
Visualize the recursion version

5.10. Stack diagrams for recursive functions#

Here’s a stack diagram that shows the frames created when we called countdown with n = 3.

from diagram import make_frame, Stack

frames = []
for n in [3,2,1,0]:
    d = dict(n=n)
    frame = make_frame(d, name='countdown', dy=-0.3, loc='left')
    frames.append(frame)

stack = Stack(frames, dy=-0.5)

from diagram import diagram, adjust


width, height, x, y = [1.74, 2.04, 1.05, 1.77]
ax = diagram(width, height)
bbox = stack.draw(ax, x, y)
# adjust(x, y, bbox)

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.

from diagram import make_frame, Stack
from diagram import diagram, adjust

frames = []
for n in [2,1,0]:
    d = dict(string='Hello', n=n)
    frame = make_frame(d, name='print_n_times', dx=1.3, loc='left')
    frames.append(frame)

stack = Stack(frames, dy=-0.5)

width, height, x, y = [3.53, 1.54, 1.54, 1.27]
ax = diagram(width, height)
bbox = stack.draw(ax, x, y)
# adjust(x, y, bbox)

5.11. 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’s a minimal function with an infinite recursion.

def recurse():
    recurse()

Every time recurse is called, it calls itself, which creates another frame. In Python, there is a limit to the number of frames that can be on the stack at the same time. If a program exceeds the limit, it causes a runtime error.

%xmode Context

recurse()

The traceback indicates that there were almost 3000 frames on the stack when the error occurred.

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.12. 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 input returns what the user typed as a string.

text = input()

Before getting input from the user, you might want to display a prompt telling the user what to type. input can take a prompt as an argument:

name = input('What...is your name?\n')
name

The sequence \n at the end of the prompt represents a newline, which is a special character that causes a line break – that way the user’s input appears below the prompt.

If you expect the user to type an integer, you can use the int function to convert the return value to int.

prompt = 'What...is the airspeed velocity of an unladen swallow?\n'
speed = input(prompt)
speed

But if they type something that’s not an integer, you’ll get a runtime error.

%xmode Minimal

int(speed)

We will see how to handle this kind of error later.

5.13. Debugging#

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:

What kind of error it was, and
Where it occurred.

Syntax errors are usually easy to find, but there are a few gotchas. Errors related to spaces and tabs can be tricky because they are invisible and we are used to ignoring them.

x = 5
 y = 6

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. Error messages indicate where the problem was discovered, but the actual error might be earlier in the code.

The same is true of runtime errors. For example, suppose you are trying to convert a ratio to decibels, like this:

%xmode Context

import math
numerator = 9
denominator = 10
ratio = numerator // denominator
decibels = 10 * math.log10(ratio)

The error message indicates line 5, but there is nothing wrong with that line. The problem is in line 4, which uses integer division instead of floating-point division – as a result, the value of ratio is 0. When we call math.log10, we get a ValueError with the message math domain error, because 0 is not in the “domain” of valid arguments for math.log10, because the logarithm of 0 is undefined.

In general, you should take the time to read error messages carefully, but don’t assume that everything they say is correct.

5.14. Glossary#

recursion: The process of calling the function that is currently executing.

modulus operator: An operator, %, that works on integers and returns the remainder when one number is divided by another.

boolean expression: An expression whose value is either True or False.

relational operator: One of the operators that compares its operands: ==, !=, >, <, >=, and <=.

logical operator: One of the operators that combines boolean expressions, including and, or, and not.

conditional statement: A statement that controls the flow of execution depending on some condition. Informally, this is usually an if-statement (that might contain an elif and else).

condition: The boolean expression in a conditional statement that determines which branch runs.

block: One or more statements indented to indicate they are part of another statement. Statements in a block are frequently said to have the same scope.

branch: One of the alternative sequences of statements in a conditional statement.

chained conditional: A conditional statement with a series of alternative branches.

nested conditional: A conditional statement that appears in one of the branches of another conditional statement.

recursive: A function that calls itself is recursive.

base case: A conditional branch in a recursive function that does not make a recursive call.

infinite recursion: A recursion that doesn’t have a base case, or never reaches it. Eventually, an infinite recursion causes a runtime error.

newline: A character that creates a line break between two parts of a string.

See also: the full vocabulary glossary collects every term in this book, alphabetized, alongside the complete AP CSP exam vocabulary list.

5.15. Exercises#

# This cell tells Jupyter to provide detailed debugging information
# when a runtime error occurs. Run it before working on the exercises.

%xmode Verbose

5.15.1. Exercise#

The time module provides a function, also called time, that returns returns the number of seconds since the “Unix epoch”, which is January 1, 1970, 00:00:00 UTC (Coordinated Universal Time).

from time import time

now = time()
now

Use integer division and the modulus operator to compute the number of days since January 1, 1970 and the current time of day in hours, minutes, and seconds.

You can read more about the time module at https://docs.python.org/3/library/time.html.

5.15.2. Exercise#

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 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.)

Write a function named is_triangle that takes three integers as arguments, and that prints either “Yes” or “No”, depending on whether you can or cannot form a triangle from sticks with the given lengths. Hint: Use a chained conditional.

Test your function with the following cases.

is_triangle(4, 5, 6)   # should be Yes

is_triangle(1, 2, 3)   # should be Yes

is_triangle(6, 2, 3)   # should be No

is_triangle(1, 1, 12)   # should be No

5.15.3. Exercise#

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)

5.15.4. Exercise#

The following exercises use the jupyturtle module, described in Chapter 4.

Read the following function and see if you can figure out what it does. Then run it and see if you got it right. Adjust the values of length, angle and factor and see what effect they have on the result.

This one is optional – try it if you have time, but it isn’t expected.

from jupyturtle import forward, left, right, back

def draw(length):
    angle = 50
    factor = 0.6
    
    if length > 5:
        forward(length)
        left(angle)
        draw(factor * length)
        right(2 * angle)
        draw(factor * length)
        left(angle)
        back(length)

5.15.5. Exercise#

A Koch curve is a fractal made by repeating one simple substitution, over and over. Start with a single straight segment. Replace its middle third with two sides of an equilateral triangle – a small outward bump – so one segment becomes four shorter ones. Now make that same replacement on each of those four segments, and then on each segment that produces, and so on. The more times you repeat it, the more detailed and jagged the edge becomes, while keeping the same zigzag pattern at every size.

one segment:                 _____________________

after one substitution:               /\
                          ___________ /  \ ___________

The recipe below is exactly that substitution, described recursively: draw a smaller Koch curve, turn, draw another, turn, and so on.

To draw a Koch curve with length x, all you have to do is

Draw a Koch curve with length x/3.
Turn left 60 degrees.
Draw a Koch curve with length x/3.
Turn right 120 degrees.
Draw a Koch curve with length x/3.
Turn left 60 degrees.
Draw a Koch curve with length x/3.

The exception is if x is less than 5 – in that case, you can just draw a straight line with length x.

Write a function called koch that takes x as an argument and draws a Koch curve with the given length.

This one is optional – try it if you have time, but it isn’t expected.

The result should look like this:

make_turtle(delay=0)
koch(120)

Once you have koch working, you can use this loop to draw three Koch curves in the shape of a snowflake.

make_turtle(delay=0, height=300)
for i in range(3):
    koch(120)
    right(120)

5.16. Homework#

Do either Exercise 1 or Exercise 2, not both. They’re interchangeable, so pick whichever appeals to you. Doing both is fine, but the second one earns no additional credit. Required work is five exercises (whichever of 1/2 you pick, plus Exercises 3-6), about 38 minutes total. The time check below must be filled in. The extra credit at the end (the Collatz sequence) is optional and never substitutes for a required exercise.

Note: the exercises above (elapsed time since the Unix epoch, is_triangle, the stack-diagram prediction, and the three turtle-drawing exercises) are practice. They aren’t graded. This is the graded homework.

5.16.1. Exercise 1: letter_grade (do 1 or 2)#

Write a function called letter_grade that takes a numeric score from 0 to 100 and prints the corresponding letter grade: 90 and above is A, 80-89 is B, 70-79 is C, 60-69 is D, and below 60 is F. Use a chained conditional, the same construct from earlier in this chapter.

Test your function with the following cases.

letter_grade(89)   # should be B

letter_grade(90)   # should be A

letter_grade(59)   # should be F

letter_grade(60)   # should be D

5.16.2. Exercise 2: rps_winner (do 1 or 2)#

Write a function called rps_winner that takes two strings, a and b, each one of 'rock', 'paper', or 'scissors', and prints 'a wins', 'b wins', or 'tie'. Use a chained conditional with and/or to check the three matchups where a beats b.

Test your function with the following cases.

rps_winner('rock', 'rock')        # should be tie

rps_winner('rock', 'scissors')    # should be a wins

rps_winner('scissors', 'paper')   # should be a wins

rps_winner('rock', 'paper')       # should be b wins

5.16.3. Exercise 3: is_leap_year#

Write a function called is_leap_year that takes a year and prints Yes or No. A year is a leap year if it’s divisible by 4, except century years (divisible by 100), which are leap years only if they’re also divisible by 400. Use the modulus operator and logical operators.

Test your function with the following cases.

is_leap_year(2000)   # should be Yes

is_leap_year(1900)   # should be No

is_leap_year(2024)   # should be Yes

is_leap_year(2023)   # should be No

5.16.4. Exercise 4: debug countdown_by_two#

Here’s a function that’s supposed to work like countdown, but counting down by twos instead of by ones.

def countdown_by_two(n):
    if n == 0:
        print('Blastoff!')
    else:
        print(n)
        countdown_by_two(n-2)

Run it with a couple of different starting values – try countdown_by_two(6), then try countdown_by_two(5). One of them behaves fine. The other runs into the same kind of error this chapter covered earlier.

countdown_by_two(6)

%xmode Context

countdown_by_two(5)

In the markdown cell below, explain what goes wrong with countdown_by_two and for which starting values of n. Then, in the code cell after that, write a corrected version and test it with a few different starting values, including at least one that would have broken the original.

Type your answer here.

5.16.5. Exercise 5: high-low, one round#

Pick a secret number and hard-code it in your solution. Prompt the player with input(), convert their guess with int(), and print Too low, Too high, or Correct! using a chained conditional. Just one round – no loop.

5.16.6. Exercise 6: reflection#

This chapter showed two ways to handle a problem with several possible outcomes: a chained conditional (if/elif/elif/…/else) or nested conditionals (an if inside another if’s else). Which did you reach for more naturally while working through this chapter’s exercises, and why?

Answer in the markdown cell below, the same way you did in chap01 through chap04.

Type your answer here.

5.16.7. Time check#

This is graded on being filled in, not on the numbers. There’s no right answer, and low numbers don’t score better. If this chapter took you three hours, I need to know that. These are estimates: nobody expects you to have timed yourself, so a rough number is exactly what’s wanted.

# Fill this in before you submit. Rough estimates are fine, and low numbers
# don't score better. Don't count time on the extra credit below.
# chapter_minutes -> reading the chapter and its practice exercises
# extra_exercises_minutes -> the six numbered exercises above
# longest -> which exercise took longest, e.g. 1
chapter_minutes = 0
extra_exercises_minutes = 0
longest = 0

from working_in_python import time_check
time_check(chapter_minutes, extra_exercises_minutes, longest)

5.17. Extra credit: recurse on the Collatz sequence#

Write the collatz function below for extra credit. It doesn’t substitute for a required exercise. This is worth 0.5 points.

If you’d like to watch recursion draw something first, the koch/snowflake cells above (optional practice) are worth running if you haven’t already – this notebook ships with no saved output, so nothing renders until you run the cells yourself.

5.17.1. Collatz (extra credit)#

The Collatz conjecture starts from any positive integer n. If n is even, the next number is n // 2. If n is odd, the next number is 3 * n + 1. Repeat, and every starting value anyone has ever tried eventually reaches 1 – though no one has proved that it always must.

Write a recursive function called collatz that takes a positive integer n, prints it, and then calls itself with the next number in the sequence. Once n reaches 1, print it and stop – don’t recurse past it. Test your function with a few different starting values, including at least one that takes many steps to reach 1.

5.17.2. Finished? Copy your work#

This isn’t part of Exercise 6. It’s a tool. Run the cell below to copy this notebook (including anything you’ve run) so you can paste it into a document.

working_in_python.show_copy_notebook_button()

Working in Python — modified by Eric Brown for a high school Computer Science Principles class. Source and modifications: github.com/porttack/working-in-python

Think Python: 3rd Edition

Code license: MIT License

Text license: Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International

5.18. Standards alignment#

AP CSP: 3.5 Boolean Expressions and 3.6 Conditionals (Big Idea 3, 30–35% of the exam). Also 3.7 Nested Conditionals, 1.2 Program Function and Purpose, and 1.4 Identifying and Correcting Errors (Big Idea 1, 10–13%), headers only. California 9-12: 9-12.AP.14 CSTA 2026: HS-PRO-RD-17, HS-ALG-PS-02. Also HS-ALG-PS-03, headers only. CA CTE (ICT): C4.9 (Pathway C), 5.12, 5.9 (Anchor Standards). Also 5.5 and C5.6, headers only.

This chapter’s boolean expressions and if statements are 3.5 and 3.6 directly, and California’s AP.14 anchors recursion here to chapter 6’s Fibonacci comparison. Nested conditionals get the same secondary treatment the text itself gives them — the book shows logical operators replacing them, not the other way around, which is CSTA’s own reworked-for-clarity standard. Recursion has no pseudocode form on the exam, but it is exactly CTE’s “function that calls itself,” and the chapter’s debugging section traces symptoms back to their real cause rather than guessing.

Vocabulary: this book writes the modulus operator as %. The exam writes MOD.

Conditionals and Recursion

Contents

5. Conditionals and Recursion#

5.1. Integer division and modulus#

5.2. Boolean Expressions#

5.3. Logical operators#

5.4. if statements#

5.5. The else clause#

5.6. Chained conditionals#

5.7. Nested Conditionals#

5.8. Recursion#

5.9. Aside: Compare a for loop with recursion#

5.10. Stack diagrams for recursive functions#

5.11. Infinite recursion#

5.12. Keyboard input#

5.13. Debugging#

5.14. Glossary#

5.15. Exercises#

5.15.1. Exercise#

5.15.2. Exercise#

5.15.3. Exercise#

5.15.4. Exercise#

5.15.5. Exercise#

5.16. Homework#

5.16.1. Exercise 1: letter_grade (do 1 or 2)#

5.16.2. Exercise 2: rps_winner (do 1 or 2)#

5.16.3. Exercise 3: is_leap_year#

5.16.4. Exercise 4: debug countdown_by_two#

5.16.5. Exercise 5: high-low, one round#

5.16.6. Exercise 6: reflection#

5.16.7. Time check#

5.17. Extra credit: recurse on the Collatz sequence#

5.17.1. Collatz (extra credit)#

5.17.2. Finished? Copy your work#

5.18. Standards alignment#

5.5. The `else` clause#

5.9. Aside: Compare a `for` loop with recursion#