Lecture 3: Conditions & Recursion

By the end of this lecture, you will be able to

  • use conditional statements to branch the flow of execution of your programs,
  • repeat calculations automatically using recursion,
  • draw stack diagrams to track variables within frames.

Last time, we talked about how to write and call functions to perform calculations that are abstracted in terms of some input variables. However, we were still pretty much using Python as a calculator - our calculations (within a function or script) could be seen as a single equation that returned a value. Today, we will look at a new control structure called conditionals. Conditionals allow us to perform different calculations depending on the variables we have (again, whether in a script or function). By combining conditionals with our previous knowledge about functions, we will then be able to repeat calculations (iterate) using a technique known as recursion.


Whenever a squirrel reaches a fork in a tree,
it must decide which branch to visit next in order to reach it's nest.
You'll be able to draw something like this next week - stay tuned!

Remember comparators from the last lecture? We only briefly talked about them, but they're really useful for making decisions in your programs. As an example, think about how your alarm works. How does it know when to wake you up? Well, suppose it keeps track of a time variable. Let's say there's a mini program inside your clock that just runs forever. At any point in time, you can check if your wakeUp time is reached, at which point your alarm should start beeping.

Your alarm will make the decision to start beeping if some condition is true. Here, the condition is time == wakeUp, which means the current time is greater than the wakeUp time. Whoever designed your alarm probably used a conditional like this (but they probably added other features like checking if you hit the snooze button to determine if your alarm should go off).

When writing a conditional statement, we need a few ingredients. As you read through these, follow along with the syntax for writing a conditional in Python on the right.

  • Tell Python you are starting a conditional statement with the if keyword. Any conditional must start with the if keyword.
  • After the if keyword, write your conditional expression. This will involve using a comparator (<, >, <=, >=, ==, !=). Note that this conditional expression must evaluate to either True or False.
  • Use a colon (:) after the conditional expression to tell Python you're ready to start branching the execution of your program. When your conditional expression evaluates to True then the block of code immediately after the conditional will be executed. Note that this block of code must be indented by one tab relative to your if keyword.
  • optional: use an elif keyword (aligned with the first if keyword) along with another conditional to control whether another block of code is executed in the event the first conditional is False. Note: you can have as many elifs as you want!
  • optional: use an else keyword (aligned with the first if keyword) to control whether a block of code is executed in the event that all if and elif's evaluated to False. Note: there is no conditional expression to write after the else keyword. Simply use a colon (:) after the else keyword and follow the same principle of indenting the statements you want executed.

When you branch your code into a block of statements, all other blocks are ignored. In fact, the program will jump to the end of the entire if statement after evaluating the block of code. In the example above, this means that if condition1 is False but condition2 is True then statement2 will be executed, and then the program will jump to Line 17 (the print statement).

Within an if statement, you can have other if statements. As you can imagine, this means you can branch the execution of a program into many different paths! Remember, the squirrel from the beginning of the lecture? Each decision the squirrel made caused it to branch into a new part of the tree. The particular path the squirrel took represented a single flow of execution through the program.

Let's do some examples to practice writing conditions and functions in Python.

Write a function absolute that returns the absolute value of a number $x$. Recall that the absolute value, denoted by $\lvert x\rvert$, is equal to $x$ if $x \ge 0$ and is equal to $-x$ if $x$ is less than zero. Test your function with the inputs $1$, and then $-5$ (already set up for you), and ensure that you obtain $1$ and $5$, respectively. If you get stuck, you can view the solution by clicking on the solution.py tab.

Write a function getLetterGrade that returns a string representing the letter grade a student should receive based on their final grade percentage. Assume that if the grade percentage (represented by the variable score) is greater than 90, then we assign a letter grade of A. If the score is greater than 80, then assign a letter grade of B. If the score is greater than 70, then assign a letter grade of C. If the score is greater than 60, then assign a letter grade of D. Otherwise, assign a letter grade of F. Don't worry about grade modifiers (- or +), but feel free to try this out if you want. Test your function by calling it with the grades: 93, 89.99999, 81, 74 and then 52. If you get stuck, you can view the solution by clicking on the solution.py tab.

As mentioned above, you can have an if statement nested within other if statements. Write a function getWeatherForecast that returns a message as to what the weather will be for the day, given a temperature T (degrees Fahrenheit) and a precipitation P (in percent). Here is the message you should return for the different cases:

Use your weather forceaster to determine which weather icon should be used for today's weather in Middlebury. You can visit the DarkSky website to find the temperature and precipitation values for a particular day: https://darksky.net/forecast/40.7127,-74.0059/us12/en. Click on "Today" and then "more details" to see the temperature and precipitation charts.

As an extra challenge, try to incorporate some "wind" variable (W) into your function! Maybe report that it will be windy if W is greater than 20 mph.

introduction to recursion

With functions and conditionals, we can start repeating computations. We will use a technique known as recursion, and in a few weeks we will cover another method for repeating computations. Recursion can be tricky so we will start with the basics this week, and then do a lot more practice next week.

Imagine you are at the dining hall, and there is a huge line to get curly fries. There are too many people in line to count all of them, so you tap the person in front of you on the shoulder and ask them how many people are ahead of them. Whatever they say, you can just add 1 to get the total number of people in front of you. Maybe they follow the same idea: they ask the person in front of them how many people are ahead of them and add 1 to the result. Suppose this continues until the person at the start of the line is reached. How many people are in front of this person? None! So they inform the person behind them that there are no people in front of them. The second person in line then adds 1 and tells the third person in line that there is 1 person ahead of them. The third person in line then adds 1 and tells the fourth person in line that there are 2 people ahead of them. This continues until you are finally reached, at which point you know the total number of people ahead of you in the line. Click on in the demo on the right to see how this works.

This is main idea of recursion: keep calling the same function until we reach some base case. The base case consists of a problem we know how to solve, so we just do some computation and then return. Otherwise, we keep calling the function recursively: we need to make sure that the inputs to our recursive function calls are getting closer and closer to our base case. Otherwise, the program would run forever!



The main ingredients we need for writing a recursive function are a recursive step and a base case. At the beginning of our recursion, the problem is too difficult to solve, but we can break it up into a problem(s) we know how to solve and use that result to solve our current problem. The outline of a recursive function is shown on the right, and the ingredients are described below.

  • base case: represents a problem you know how to solve.
  • recursive step represents a problem you don't know exactly how to solve, however you can break it up into smaller problems that you know how to solve, and then use the result to solve your current problem.

This probably sounds super vague right now, but don't worry, it'll make sense once we start doing some examples. In the curly fries example, the "big problem" was figuring out how many people are in front of us. Since we couldn't solve this directly, we broke it up into a "smaller problem", in which we asked the person in front of us how many people are in front of them and then added 1 to the result.

The example above contains two versions of a template for a recursive function. We are given some input that we will use to do some computation. However, we can't directly solve our problem with this input, unless we have reached the base case, which we check with the conditional baseCase (treat this as some conditional, so it returns either True or False). If we haven't reached the base case, then we will call our function "recursively" by breaking up the input into something smaller, with the hopes that we eventually reach the base case (in which we know what computation to perform). This recursive function call might return something that we need to use to perform additional computation before returning the result.

Check your understanding by determining if both versions (switch the version by clicking on the tabs) do the same thing.

This was more of an exercise in the syntax for writing conditionals and functions. In fact, yes, both versions do exactly the same thing. In Version 1, the recursive step is written in the else portion, which is never reached if the base case is reached. In Version 2, we automatically return from the function after doing some computation for the base case. So the stuff on Line 14 are not reached if the base case is reached (but they are reached for functions that call the base case).

Let's write a recursive function to compute the value of some input number $x$ raised to te power of an integer $p$, denoted by $x^p$. Yes, I know that Python can do this with x ** p but let's write a recursive function to do this. For an integer $p$, we can write out $x^p$ as

$$ x^p = \underbrace{x \times x \times x \times \dots \times x}_{\mbox{$p$ times}} = x \times (\underbrace{x \times x \times \dots \times x)}_{\mbox{$p-1$ times}}. $$ So we have broken up our problem (which we can't solve directly) into a smaller problem and then use the solution to that smaller problem to compute the solution to our problem. Eventually, as we keep decrementing (subtracting 1 from $p$), we will reach $p = 0$. What's $x^0$? It's just 1! This is our base case. Try completing the power function below. Check that your function works correctly by calling power(2,4) and making sure you get 16.

Let's do another math-y example, this time with the factorial, represented with an exclamation point. Recall that $5! = 5 \times 4 \times 3 \times 2 \times 1$. Observe that $5! = 5 \times 4!$ and $4! = 4 \times 3!$. Hmm, this sounds pretty recursivey. So in order to compute $5!$, we can just multiply $5$ times whatever we get from $4!$, and then keep doing that until we get to our base case. What is our base case? Well when we get to $1$, then $1! = 1$ (in fact, $0!$ is also equal to $1$). See if you can complete the factorial function below.

Okay, that's enough math. Let's try and get a feel for the path Python takes through a program. Consider the following recursive function that hopefully clarifies the path a recursive function call takes.

The goBack function takes in some integer n. If we reached the base case (we chose n == 0 for this example, but it could have been something else), then we print "stop". Otherwise, we are in the recursive case, in which we want to print "go" (along with the current value of n). We then call goBack recursively with an input of n-1 (we make the current input smaller for the recursive call). Within the goBack(n-1) function call, we may still not reach the base case, so it will again print "go" with the current value of n (which is equal to n-1 relative the "caller" of this function). After we finally reach the base case, then we come back up the recursive calls and print "back" followed by the local value of n.

The goBack function in the last exercise revealed the "path" a recursive function takes after it is called, which can be tricky to visualize. One useful method for visualizing the path your program takes is through what's called a stack diagram. A stack diagram is composed of frames, in which each frame represents a particular function call. You can draw out this frame as a box, kind of like the "ships" we saw last week. Inside each box, you should put a title for the box which includes the function name and values for the input variables. Now your job is to "be the computer", in other words, do the calculations Python would do for you, calculating intermediate variables and then writing out call the "calls" to other functions. Whenever you need to call another function, create a new frame! You should also draw an arrow between the frames as (1) a function is called from another function (the "caller") and (2) a function returns a value to it's caller. At the end of the day, you should have two arrows between all the frames: one when you go down the functions calls, and one when go back up.

Have a look at the following demo on for the goBack function. This demo describes the steps you would take to draw a stack diagram for the initial input of goBack(5). Click on the to take a single "step" through the execution of the program. Notice which line is currently being executed in the editor on the left.



You should also investigate the use of the debugger in Thonny in order to play around with stack diagrams. Thonny's debugger is a really nice tool that "pops out" a new window every time a new frame is created. You can also see the values of the variables in each frame. The "step in" button in Thonny is kind of like the above - it "steps" one line at a time.

Technically speaking, there is also a frame for the "main" portion of the script. Our goal is to focus on a particular function call so we will usually omit this "main" frame. I will specify which function call to start your stack diagram at, such as goBack(5) in the above example.

© Philip Claude Caplan, 2021