Lecture Notes
Introduction to Programming and Algorithm Design (COP-1000)

Conditionals and recursion

This chapter explains how to use conditional execution in your programs, and how to implement a form of iteration (loops) by having a function call itself recursively.


The modulus operator

  • The modulus operator requires two integer operators, and yields the integer remainder of dividing the first by the second
  • Python (and C and Java) use the % symbol as the modulus operator:

>>> print 7 % 3
1
>>> print 8 % 3
2
>>> print 9 % 3
0
>>> print 3 % 4
3

  • The modulus operator can be used to determine if one integer is evenly divisible by another, or to extract the rightmost digit of a number:

>>> n = 25437
>>> print "The right digit of", n, "is", n % 10
The right digit of 25437 is 7


Boolean expressions

  • A boolean expression is an expression that evaluates to either true or false, which are given the values 1 and 0, respectively
  • Boolean expressions are often constructed to compare two values with one of six comparison operators:
Operator Meaning Example Result Other phrases
== is equal to 5 == 5 True the same as
not different from
!= is not equal to 5 != 5 False different from
unequal
> is greater than 5 > -5 True more than
exceeds
>= is greater than
or equal to
5 >= 10 False at least
not less than
< is less than 5 < 10 True not as much as
 
<= is less than
or equal to
5 <= 5 True not more than
at most
  • Of course, either or both of the operands can be arbitrarily complex:

>>> x = 8
>>> y = 4
>>> print x - 5 > y
False
>>> print x % y == 0
True
>>> print x != "Hello"
True
>>> print x != int( "8" )
False

  • A common mistake is to confuse the assignment operator (=) with the equality comparison operator (==):

>>> print x == 8
True
>>> print x = 8
SyntaxError: invalid syntax


Logical operators

  • More complex boolean expressions can be formed using the logical operators and, or, and not:

>>> x = 8
>>> 3 < x and x < 10
True
>>> 3 < x or x == 10
True
>>> not(x == 8)
False


Conditional execution

  • Boolean expressions are used to implement conditional statements
  • Conditional statements are those that may or may not be executed, depending on a condition during execution of the program
  • We implement conditional execution with the if statement, whose syntax is:
if exp:
    stmt
    ...
  • When an if statement is encountered in the execution of a program, the exp, which is a boolean expression, is evaluated; then,
    • if it is True, the statement (stmt) in the block indented under the if are executed
    • if it is False, the block is not executed, and flow of control passes to the first statement after the block:
>>> x = 8
>>> if x == 8:
        print "This statement should print."


This statement should print.
>>> if x != 8:
        print "This statement should not print"


>>>
  • A flowchart version of conditional execution logic looks like:

  • There is no limit to the number of statements that can be used in a block following the if all of them will be executed if exp is True
  • See example program getA.py
    • Uses conditional execution
    • round() function used to round input
    • trailing , in print statement to suppress newline

Alternative execution

  • Second form of if is alternative execution, whose syntax is:
if exp:
    stmt
    ...
else:
    stmt
    ...
  • In flowchart form, this looks like:

  • One of the two blocks of statements will be executed: if the condition is True, the statements following the if are executed; if the condition is False, the statements following the else are executed
  • See example program passfail.py

Chained conditionals

  • Sometimes we need to choose from among several alternatives; the chained form of the if statement can do this; its syntax:
if exp:
    stmt
    ...
elif exp:
    stmt
    ...
...
[else:
    stmt
    ...]
  • There can be as many elif branches as necessary; the first True condition determines which block will be executed
  • If none of the conditions is True, the block following the optional else (the default case) are executed; if there is no else block, execution continues with the next statement
  • Here is the flowchart version:

  • See example program calcHonors.py
  • Also see the example program calcHonors2.py, that reverses the order of the conditions in the above program

Nested conditionals

  • A block can contain any statement, even another if statement such statements are called nested conditionals
  • See example program evenodd.py

Decision Tables

  • Sometimes the specification for part a program's logic is given in the form of a decision table. Here is an example:
Total Purchased at least $5000 ? Y Y N N N N
Total Purchased at least $1000 but less than $5000 ? N N Y Y N N
Is account current ? Y N Y N Y N
Discount = 10% X          
Discount = 5%     X      
Discount = 2%         X  
Discount = 0%   X   X   X
  • The job of a programmer would be to translate the table into code. There are many possible ways to do this. Here is one:

if account_current == True:
    if total >= 5000:
        discount = 0.10
    elif total >= 1000:
        discount = 0.05
    else:
        discount = 0.02
else:
    discount = 0.0

  • Python pretty much forces you to use the indentation necessary to implement the correct logic. In other languages (like Java and C), indentation is ignored by the compiler, making it much harder to debug a program unless the programmer is careful to maintain an orderly and consistent system of indentation


The return statement

  • The return statement always returns control (as in flow of control) to the function that called it
  • Returning control from a function causes any remaining (unexecuted) statements in the function to be skipped
  • See example program printlog.py

Recursion

  • A function can call itself this is known as recursion, and is one way of constructing a loop in a program (there are other, more straightforward ways we'll get to, but it's an interesting topic and introduced here just to show you that all you need to write any program is the if statement)
  • The idea is that there is a base case that the function can test for and execute; if the function is called and the base case is not the current condition, the function calls itself, usually with a modified argument
  • See example program countdown.py; it also demonstrates use of the sleep() function from the time module to slow down the program
  • See the example program gcd.py; it implements Euclid's algorithm for finding the greatest common denominator of two integers.

Stack diagrams for recursive functions

  • This section explains that each recursive function call generates a new (but separate) variable of the same name (each is a local variable)
  • Here is the stack diagram for a 3-second run of the countdown.py program:


Infinite recursion

  • Recursive function calls require the computer to keep track of a lot of information, so it can manage the flow of control back up the stack
  • In practice, there is a limit to this, and anything over the limit generates a runtime exception
  • Try running a 1000-second countdown.py

Keyboard input

  • This section explains how to get input from the keyboard; we have been doing this, so the idea isn't new, but a new function raw_input is explained
  • raw_input is useful for obtaining string input:

>>> nameIn = raw_input("What is your name? ")
What is your name? Steve
>>> print "Hello,", nameIn
Hello, Steve

  • The raw_input function inputs a string rather than try to interpret characters typed at the keyboard as numbers, the way input does:

>>> x = input("Enter a number: ")
Enter a number: 12
>>> type(x)
<type 'int'>
>>> x = raw_input("Enter a number: ")
Enter a number: 12
>>> type(x)
<type 'str'>

  • The example program tomato.py demonstrates use of raw_input to obtain a string from the keyboard
  • Another way we will use raw_input is to obtain input as strings, and then extract/convert what we need with the built-in functions int and float
 Updated: 12.13.2010