5b. Prof. Rosenthal’s Review

5b. Prof. Rosenthal’s Review#

A review of Chapter 5: Conditionals and Recursion, for students who have already studied the chapter. Use the two lists under Concepts covered as a checklist (click a list’s title to hide it), then work through the Questions, which go from easy to hard. Each question has a suggested answer under Answer. Try the question first, then open the Answer.

Run this page on Colab

Concepts covered#

Python Syntax and Semantics

Integer division and modulus

  • X // Y divides and rounds down to an integer: 105 // 60 is 1, and -7 // 2 is -4.

  • X % Y (the modulus operator) is the remainder when X is divided by Y: 105 % 60 is 45.

  • X % Y == 0 is true when X is divisible by Y. X % 10 is the last digit of X, and X % 100 its last two digits.

  • (START + DURATION) % 12 is clock arithmetic: it wraps around after 12 (use % 24 for a 24-hour clock).

Boolean expressions

  • True and False are the two values of the type bool. They are not strings.

  • The relational operators compare two values and produce True or False: X == Y (equal), X != Y (not equal), X > Y, X < Y, X >= Y, X <= Y.

  • = assigns a value to a variable; == compares two values.

  • A and B is true when both are true. A or B is true when either or both are true. not A is true when A is false. For example, x > 0 and x < 10 is true when x is between 0 and 10.

  • LOW < X < HIGH is shorthand for LOW < X and X < HIGH.

  • Any nonzero number counts as true when used as a condition. (This can be confusing; it is better to use boolean expressions.)

if statements

  • This runs the indented block only if the condition is true:

    if CONDITION:
    BLOCK

    For example, this displays x is positive if x is greater than 0:

    if x > 0:
    print('x is positive')

  • A block must have at least one statement. pass is a statement that does nothing, used as a placeholder.

  • With an else clause, exactly one of the two blocks runs:

    if CONDITION:
    BLOCK1
else:
    BLOCK2

  • A chained conditional checks the conditions in order and runs only the block of the first true one (or the else block, if none is true):

    if CONDITION1:
    BLOCK1
elif CONDITION2:
    BLOCK2
else:
    BLOCK3

    There can be any number of elif clauses. The else clause is optional, and must come last.

  • Separate if statements, one after the other, are each checked: several of their blocks can run.

  • An if statement can be nested inside a block of another one. A nested conditional can often be replaced by one condition with and.

Recursion

  • A function can call itself. Each call has its own parameters and local variables.

  • A recursive function needs a base case: a branch that does not make a recursive call. Each recursive call should move closer to the base case.

  • Statements after a recursive call run after that call has finished, so they run in the opposite order of the calls.

  • If the base case is never reached, the recursion goes on until Python’s limit on the number of frames (about 1000; the exact number depends on the environment) is exceeded, which is a RecursionError.

Keyboard input

  • input() stops the program, waits for the user to type something and press Enter, and returns what they typed, as a string.

  • input(PROMPT) first displays the prompt. '\n' in a string is a newline (a line break), so input('Your name?\n') lets the user type below the prompt.

  • int(input()) converts the input to an integer; if the user types something that is not an integer, it is a ValueError.

Error messages

  • Indenting a line that should not be indented is an IndentationError.

  • Leaving out the colon at the end of an if header is a SyntaxError, and so is using = instead of == in a condition.

  • An error message says where the error was discovered, which may be after the line where the mistake is.

The jupyturtle module (used by one question)

  • make_turtle() starts a drawing with the turtle in the middle, facing east; forward(DISTANCE) moves and draws (a negative distance moves backward); left(DEGREES) and right(DEGREES) turn; penup() and pendown() stop and restart drawing.

Definitions, etc.

Definitions

  • DEFINITION: The modulus operator, %, computes the remainder when one integer is divided by another.

  • DEFINITION: A boolean expression is an expression whose value is either True or False.

  • DEFINITION: A relational operator is one of the operators that compare their operands: ==, !=, >, <, >= and <=.

  • DEFINITION: A logical operator is one of the operators that combine boolean expressions: and, or and not.

  • DEFINITION: A conditional statement is a statement that controls which statements run, depending on a condition.

  • DEFINITION: A condition is the boolean expression in a conditional statement that decides which branch runs.

  • DEFINITION: A block is one or more statements indented to show they are part of another statement.

  • DEFINITION: A branch is one of the alternative blocks in a conditional statement.

  • DEFINITION: A chained conditional is a conditional statement with a series of alternative branches (if, elif, …, else).

  • DEFINITION: A nested conditional is a conditional statement inside a branch of another conditional statement.

  • DEFINITION: Recursion is calling the function that is currently running. A function that calls itself is recursive.

  • DEFINITION: The base case is a branch of a recursive function that does not make a recursive call.

  • DEFINITION: Infinite recursion is a recursion that has no base case or never reaches it. It ends with a runtime error.

  • DEFINITION: A newline is a character, written \n, that makes a line break in a string.

Other ideas

  • Nested conditionals are hard to read; avoid them when a simpler condition can do the same job.

  • TODO in a comment is a conventional reminder of something still to be done.

  • In a stack diagram of a recursive function, each call has its own frame with its own value of each parameter; the frame of the base case is at the bottom.

  • When you see an infinite recursion, check that there is a base case and that every call is guaranteed to reach it.

  • The most useful parts of an error message are the kind of error and where it happened. Read error messages carefully, but the actual mistake may be earlier in the code.

Questions#

One question draws a picture with jupyturtle, a small turtle-graphics module for Jupyter notebooks. The turtle starts in the middle of the canvas, facing east (to the right). make_turtle() starts a new drawing, forward(d) moves the turtle d units while drawing a line (backward if d is negative), left(a) and right(a) turn it a degrees, and penup() and pendown() stop and restart the drawing.

The setup cell below downloads jupyturtle and imports those functions.

from os.path import basename, exists

def download(url):
    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/ramalho/jupyturtle/releases/download/2024-03/jupyturtle.py');

from jupyturtle import make_turtle, forward, left, right, penup, pendown

Question 1 (easy): what is displayed?#

Predict what this code displays, then open the Answer to check.

minutes = 135
print(minutes // 60, minutes % 60)
print(17 % 5, 20 % 5, 3 % 7)
print(7 // 2, -7 // 2)

Answer

2 15
2 0 3
3 -4

135 minutes is 2 hours (135 // 60) and 15 minutes left over (135 % 60). 20 % 5 is 0 because 20 is divisible by 5, and 3 % 7 is 3 because 7 goes into 3 zero times, with 3 left over. // always rounds down, so -7 // 2 is -4, not -3.

Question 2 (easy): what is displayed?#

x = 5
y = 7
print(x == y, x != y)
print(x < y and y < 10)
print(x > y or y == 7)
print(not x < y)
print(type(True))

Answer

False True
True
True
False
<class 'bool'>

x < y and y < 10 is true because both parts are true. x > y or y == 7 is true because one part, y == 7, is true. x < y is true, so not x < y is false. True and False belong to the type bool.

Question 3 (easy): what is displayed?#

def check(n):
    if n % 2 == 0:
        print(n, 'is even')
    else:
        print(n, 'is odd')

check(4)
check(7)
check(0)

Answer

4 is even
7 is odd
0 is even

A number is even when the remainder of dividing it by 2 is 0. 0 % 2 is 0, so 0 is even. Exactly one of the two branches runs in each call.

Question 4 (easy): write a function#

Write a function called sign that takes a number x and displays positive, negative or zero.

Start from this header (replace ... with the body):

def sign(x):
    ...

Examples

sign(12)
sign(-0.5)

positive
negative

sign(0)

zero

Answer

A chained conditional, with one branch for each case:

def sign(x):
    if x > 0:
        print('positive')
    elif x < 0:
        print('negative')
    else:
        print('zero')

Then try: sign(12) and sign(-0.5).

The same thing with a nested conditional, which is harder to read:

def sign(x):
    if x == 0:
        print('zero')
    else:
        if x > 0:
            print('positive')
        else:
            print('negative')

Question 5 (medium): what is displayed?#

def grade(score):
    if score >= 60:
        print('pass')
    elif score >= 90:
        print('excellent')
    else:
        print('fail')

grade(95)
grade(70)
grade(30)

Answer

pass
pass
fail

In a chained conditional, only the first true branch runs. For 95, score >= 60 is already true, so the elif is never checked, and excellent is never displayed for any score. To fix it, check score >= 90 first:

def grade(score):
    if score >= 90:
        print('excellent')
    elif score >= 60:
        print('pass')
    else:
        print('fail')

grade(95)
grade(70)
grade(30)

excellent
pass
fail

Question 6 (medium): what is displayed?#

x = 15
if x > 10:
    print('big')
if x > 5:
    print('medium')
if x > 0:
    print('small')
else:
    print('not positive')

Answer

big
medium
small

These are three separate if statements, and each one is checked, so all three blocks whose conditions are true run. The else belongs only to the last if. With elif instead of the second and third if, only big is displayed:

x = 15
if x > 10:
    print('big')
elif x > 5:
    print('medium')
elif x > 0:
    print('small')
else:
    print('not positive')

big

Question 7 (medium): what is displayed?#

def describe(x):
    if 0 < x < 10:
        print(x, 'is a positive single digit')
    else:
        if x <= 0:
            print(x, 'is not positive')
        else:
            print(x, 'is 10 or more')

describe(5)
describe(-3)
describe(10)

Answer

5 is a positive single digit
-3 is not positive
10 is 10 or more

0 < x < 10 means 0 < x and x < 10, which is false for 10. The nested conditional could be written as one chained conditional:

def describe(x):
    if 0 < x < 10:
        print(x, 'is a positive single digit')
    elif x <= 0:
        print(x, 'is not positive')
    else:
        print(x, 'is 10 or more')

5 is a positive single digit
-3 is not positive
10 is 10 or more

Question 8 (medium): find the error#

Each part has one mistake. Predict the error for each, then open the Answer to check.

Part a

x = 5
if x = 5:
    print('five')

Part b

x = 5
if x > 0
    print('positive')

Part c

x = 5
 y = 6

Answer

Part a: = assigns; comparing needs == (a SyntaxError):

    if x = 5:
       ^
SyntaxError: invalid syntax. Maybe you meant '==' or ':=' instead of '='?

Part b: The header of an if statement must end with a colon (a SyntaxError):

    if x > 0
            ^
SyntaxError: expected ':'

Part c: The second line is indented by one space, but it is not inside a block (an IndentationError):

    y = 6
    ^
IndentationError: unexpected indent

Python finds each of these mistakes before it runs any of that part’s code, so nothing is displayed and x is never assigned.

Question 9 (medium): write a function#

Write a function called end_hour that takes start (an hour on a 24-hour clock, from 0 to 23) and duration (a number of hours), and displays the hour when the event ends, also from 0 to 23.

Start from this header (replace ... with the body):

def end_hour(start, duration):
    ...

Examples

end_hour(9, 3)
end_hour(22, 5)

12
3

end_hour(20, 28)

0

Answer

The remainder after dividing by 24 wraps around midnight:

def end_hour(start, duration):
    print((start + duration) % 24)

Then try: end_hour(9, 3) and end_hour(22, 5).

22 + 5 is 27, which is 3 more than 24, so the event ends at 3. 20 + 28 is 48, exactly two days, so it ends at 0 (midnight).

Question 10 (medium): write a function#

Write a function called fizzbuzz that takes a positive integer n and displays FizzBuzz if n is divisible by both 3 and 5, Fizz if it is divisible by 3 only, Buzz if it is divisible by 5 only, and otherwise n itself.

Start from this header (replace ... with the body):

def fizzbuzz(n):
    ...

Examples

fizzbuzz(9)
fizzbuzz(10)

Fizz
Buzz

fizzbuzz(30)
fizzbuzz(7)

FizzBuzz
7

Answer

Check the most specific case first: a number divisible by both 3 and 5 is also divisible by 3, so if n % 3 == 0 came first, 30 would display Fizz.

def fizzbuzz(n):
    if n % 3 == 0 and n % 5 == 0:
        print('FizzBuzz')
    elif n % 3 == 0:
        print('Fizz')
    elif n % 5 == 0:
        print('Buzz')
    else:
        print(n)

Then try: fizzbuzz(9) and fizzbuzz(10).

A number divisible by both 3 and 5 is divisible by 15, so the first condition can also be n % 15 == 0:

def fizzbuzz(n):
    if n % 15 == 0:
        print('FizzBuzz')
    elif n % 3 == 0:
        print('Fizz')
    elif n % 5 == 0:
        print('Buzz')
    else:
        print(n)

Question 11 (medium): write a function#

Write a function called largest that takes three numbers and displays the largest of them. Use if statements (not the built-in function max).

Start from this header (replace ... with the body):

def largest(a, b, c):
    ...

Examples

largest(3, 9, 4)
largest(10, 2, 7)

9
10

largest(5, 5, 1)
largest(-1, -8, -0.5)

5
-0.5

Answer

a is the largest if it is at least as large as each of the others; otherwise the larger of b and c is:

def largest(a, b, c):
    if a >= b and a >= c:
        print(a)
    elif b >= c:
        print(b)
    else:
        print(c)

Then try: largest(3, 9, 4) and largest(10, 2, 7).

Using >= instead of > matters when two numbers are equal: with a > b and a > c, largest(5, 5, 1) would skip the first branch, but still display 5 from the second one.

Another approach keeps track of the largest so far:

def largest(a, b, c):
    biggest = a
    if b > biggest:
        biggest = b
    if c > biggest:
        biggest = c
    print(biggest)

Question 12 (hard): what is displayed?#

def mystery(n, s):
    print('n =', n, 's =', s)
    if n == 0:
        print('result:', s)
    else:
        mystery(n - 1, s + n)

mystery(3, 0)

Answer

n = 3 s = 0
n = 2 s = 3
n = 1 s = 5
n = 0 s = 6
result: 6

Each call passes n - 1 and s + n to the next one, so s adds up 3 + 2 + 1. The call with n = 0 is the base case: it does not call mystery again. In general, mystery(n, 0) displays the sum of the integers from 1 to n.

Question 13 (hard): what is displayed?#

def up_down(n):
    if n > 0:
        print('*' * n)
        up_down(n - 1)
        print('*' * n)

up_down(3)

Answer

***
**
*
*
**
***

Each call displays its line, makes the recursive call, and displays its line again after that call has finished. So the first print calls happen in the order 3, 2, 1, and the second ones in the opposite order, 1, 2, 3. The call up_down(0) is the base case: its condition is false, so it does nothing.

Question 14 (hard): infinite recursion#

Run this cell to define countdown_by_two.

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

Two correct ways to call it:

countdown_by_two(4)

Blastoff!

countdown_by_two(10)

Blastoff!

What happens with this call? How would you fix the function? (Try your fix in a new cell, so that the cell above keeps the original code.)

countdown_by_two(5)

Answer

The calls get n = 5, 3, 1, -1, -3, … and never 0, so the base case is never reached. This is infinite recursion. It ends when there are too many frames on the stack (a RecursionError):

----> 1 countdown_by_two(5)

In countdown_by_two(n):
      3         print('Blastoff!')
      4     else:
----> 5         countdown_by_two(n - 2)

... last 1 frames repeated, from the frame below ...

In countdown_by_two(n):
      3         print('Blastoff!')
      4     else:
----> 5         countdown_by_two(n - 2)

RecursionError: maximum recursion depth exceeded

Fix it by making the base case catch every number at or below zero:

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

countdown_by_two(5)

Blastoff!

Question 15 (hard): write a recursive function#

Write a recursive function called stairs that takes a positive integer n and displays n lines: n copies of #, then n - 1 copies, and so on, down to one. Do not use a for loop.

Start from this header (replace ... with the body):

def stairs(n):
    ...

Examples

stairs(3)

###
##
#

stairs(5)

#####
####
###
##
#

Answer

Display the first line, then let a recursive call display the rest. When n reaches 0 there is nothing left to do (the base case):

def stairs(n):
    if n > 0:
        print('#' * n)
        stairs(n - 1)

Then try: stairs(3).

The same thing with the base case written out:

def stairs(n):
    if n <= 0:
        pass          # nothing to display
    else:
        print('#' * n)
        stairs(n - 1)

Moving print after the recursive call would display the lines in the opposite order, from one # up to n.

Question 16 (hard): write two recursive functions#

Write two recursive functions that take a non-negative integer n and display its digits, one per line: digits_backward(n) from the last digit to the first, and digits_forward(n) from the first to the last. Use % 10 (the last digit) and // 10 (the number without its last digit), and no loops.

Start from this header (replace ... with the body):

def digits_backward(n):
    ...

def digits_forward(n):
    ...

Examples

digits_backward(472)

2
7
4

digits_forward(472)

4
7
2

digits_forward(5)

5

Answer

A number with one digit (less than 10) is the base case. Otherwise, display the last digit and handle the rest recursively, or the other way around:

def digits_backward(n):
    print(n % 10)
    if n >= 10:
        digits_backward(n // 10)

def digits_forward(n):
    if n >= 10:
        digits_forward(n // 10)
    print(n % 10)

Then try: digits_backward(472).

The only difference is the order: digits_forward displays its digit after the recursive call has displayed all the earlier digits. Another way to write the base case:

def digits_forward(n):
    if n < 10:
        print(n)
    else:
        digits_forward(n // 10)
        print(n % 10)

Question 17 (hard): what is drawn?#

This recursive function draws with jupyturtle. Describe what it draws, then open the Answer to check.

def branch(length):
    if length > 10:
        forward(length)
        left(30)
        branch(length * 0.6)
        right(60)
        branch(length * 0.6)
        left(30)
        forward(-length)

make_turtle(delay=0, height=220)
left(90)            # face up
penup()
forward(-100)       # move down without drawing
pendown()
branch(70)

Answer

A tree: a trunk of length 70 that splits into two branches, each of which splits into two, and so on, each time 0.6 times as long, until the length is 10 or less:

Turtle drawing

branch draws a line, turns left 30 degrees and draws a smaller tree, turns right 60 degrees and draws another smaller tree, then turns back and moves backward to where it started, facing the same way. That last step is important: each call leaves the turtle where it found it, so the next branch starts in the right place. The base case is a length of 10 or less, where nothing is drawn. The lengths are 70, 42, 25.2, 15.12, then 9.072, so there are four levels.

Summary and questions by Prof. Y. Rosenthal, based on Think Python: 3rd Edition by Allen B. Downey. Text license: Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International