5.3. 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.3.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:

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

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

Or you could use the modulus operator, %, which divides two numbers and returns the 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.

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.

The event would end at 2 PM.

5.3.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:

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.

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

The == operator is one of the relational operators; the others are:

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

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:

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

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:

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

5.3.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 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 1 < 2:
    print('Yep!')             ###

if 1 < 2:
    print('yep!')             ### yep

5.3.4.1. The else clause

An if statement can have a second part, called an else clause.

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

>>> num = int(input("Please enter an integer: "))
Please enter an integer: 

>>> if num % 2 == 0:
...     print("num is even")
... else:
...     print("num is odd")

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

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

The alternatives are called branches.

if 1 < 2:
    print('first')
else:
    print('last')

if 1 > 2:
    print('first')
else:
    print('last')

5.3.5. Chained Conditional: elif

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.

elif is an abbreviation of “else if” and is used to add multiple conditions inside an if block. Observe the following example:

>>> num = int(input("Please enter an integer: "))
Please enter an integer: [an integer]

>>> if num > 0:
...     print("positive")
... elif num == 0:
...     print("neither positive or negative")
... elif num < 0:
...     print("negative")

We can see that the elif keyword allows us to add multiple conditional tests.

5.3.6. The else

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.3.7. Nested Conditionals

One conditional can also be nested within another. We could have written the example in the previous section like this:

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.

The print statement runs only if we make it past both conditionals, so we get the same effect with the and operator.

For this kind of condition, Python provides a more concise option:

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

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.

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.

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.

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

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.

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

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:

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.

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

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

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

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.

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.