Conditionals and Recursion

Modulus Operator

The modulus operator works on integers and yields the remainder when the first operand is divided by the second. In Python, the modulus operator is a percent sign (%). The syntax is the same as for other operators:


In [2]:
quotient = 7 / 3
print(format(quotient, '.2f'))

remainder = 7 % 3
print(remainder)


2.33
1

The modulus operator turns out to be surprisingly useful. For example, you can check whether one number is divisible by another

if x % y is zero, then x is divisible by y.

Also, you can extract the right-most digit or digits from a number.

x % 10 yields the right-most digit of x (in base 10). Similarly x % 100 yields the last two digits.



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:


In [3]:
5 == 5


Out[3]:
True

In [4]:
5 == 6


Out[4]:
False

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


In [6]:
type(True), type(False)


Out[6]:
(bool, 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 =>.

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 of the conditions is true, that is, if the number is divisible by 2 or 3.

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

The boolean expression after if is called the condition. If it is true, then the indented statement gets executed. If not, nothing happens.

The 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 # need to handle negative values!

Alternative Execution

A second form of the if statement is alternative execution, in which there are two possibilities and the condition determines which one gets executed. 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 a message to that effect. If the condition is false, the second set of statements is executed. Since the condition must be true or false, exactly one of the alternatives will be executed. The alternatives are called branches, because they are branches in the flow of execution.

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:


In [2]:
x = 10
y = 9
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')


x is greater than y

The elif is an abbreviation of “else if.” Again, exactly one branch will be executed. 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 executes, and the statement ends. Even if more than one condition is true, only the first true branch executes.

Nested Conditionals

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


In [3]:
x = 18
y = 20
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')


x is less 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. In general, 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:


In [4]:
x = 8
if 0 < x:
    if x < 10:
        print('x is a positive single-digit number.')


x is a positive single-digit number.

The print statement is executed only if we make it past both conditionals, so we can get the same effect with the and operator:


In [5]:
if 0 < x and x < 10:
    print('x is a positive single-digit number.')


x is a positive single-digit number.

Recursion

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:


In [7]:
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.


In [8]:
countdown(3)


3
2
1
Blastoff!

A function that calls itself is recursive; the process is called recursion.

As another example, we can write a function that prints a string n times.


In [9]:
def print_n(s, n):
    if n <= 0:
        return
    print(s)
    print_n(s, n-1)

If n <= 0 the return statement exits the function. The flow of execution immediately returns to the caller, and the remaining lines of the function are not executed.

The rest of the function is similar to countdown : if n is greater than 0, it displays s and then calls itself to display s n 􀀀1 additional times. So the number of lines of output is1 + (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.

Keyboard Input

The programs we have written so far are a bit rude in the sense that they accept no input from the user. They just do the same thing every time.

Python 3 provides a built-in function called input that gets input from the keyboard.

When this function is called, the program stops 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.


In [10]:
text = input()


This is the user's input

In [11]:
print(text)


This is the user's input

Before getting input from the user, it is a good idea to print a prompt telling the user what to input. input can take a prompt as an argument:


In [12]:
name = input('What...is your name?\n')


What...is your name?
...Enes

In [13]:
print(name)


...Enes

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


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


What...is the airspeed velocity of an unladen swallow?
7

In [15]:
int(speed)


Out[15]:
7

But if the user types something other than a string of digits, you get an error:


In [16]:
speed = input(prompt)


What...is the airspeed velocity of an unladen swallow?
What is this?

In [17]:
int(speed)


---------------------------------------------------------------------------
ValueError                                Traceback (most recent call last)
<ipython-input-17-59a44d55c2ef> in <module>()
----> 1 int(speed)

ValueError: invalid literal for int() with base 10: 'What is this?'

Exercises

Exercise 1: Fermat’s Last Theorem says that there are no positive integers a, b, and c such that

$$ a^n + b^n = c^n $$

for any values of n greater than 2.

1.

Write a function named check_fermat that takes four parameters (a, b, c, n) and that checks to see if Fermat’s theorem holds. If n is greater than 2 and it turns out to be true that

$$ a^n + b^n = c^n $$

the program should print, “Holy smokes, Fermat was wrong!” Otherwise the program should print, “No, that doesn’t work.”

2.

Write a function that prompts the user to input values for a, b, c and n, converts them to integers, and uses check_fermat to check whether they violate Fermat’s theorem.


In [ ]:

Exercise 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, it is clear that 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.)

  1. 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.
  2. Write a function that prompts the user to input three stick lengths, converts them to integers, and uses is_triangle to check whether sticks with the given lengths can form a triangle.

In [ ]: