Lecture 4: Recursion & Turtles

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

  • practice some more with recursion,
  • write more efficient solutions to recursive programs,
  • draw with the turtle.

Writing recursive functions can be tricky, so we'll start off this week by practicing writing recursive functions. Next, we will talk about the turtle module, which will allow you to write your first graphics programs!

recursion examples

Remember the two main ingredients we need to write a recursive function: we need to treat a base case and a recursive step. Ultimately, you need to make sure that your recursive function calls will eventually reach the base case - otherwise your program could run forever! Note that you might also have multiple base cases.

When Carl Friedrich Gauss was 7 years old (in the 1780s), his teacher (wanting to quiet down the class) gave the class a seemingly impossible task: add up all the numbers from 1 to 100. This should have kept them busy for hours. However, Gauss finished the problem almost immediately! In fact, Gauss proved that the sum of the first $n$ natural numbers (i.e. the sum of the numbers starting at $1$ and going until $n$) is equal to $n(n+1)/2$. Write a recursive program called sumn to compute the sum of the first $n$ integers, starting at 1. Ensure that your program computes the correct result for $n = 100$, i.e. it should be equal to $100 \times 101 / 2 = 5,050$.

It's spring time, so bunnies are starting to take over Middlebury. Fibonacci actually studied an idealized model for bunny population growth. Assume that we start by placing two baby rabbits somewhere in Middlebury. Rabbits mature into adult rabbits after 1 month at which point they breed a new pair of baby rabbits (this is an assumption in our idealized model). So at the beginning, we have no rabbits, but then after 1 month we have a pair of baby rabbits. The next month, these baby rabbits have matured into a pair of adult rabbits. The month after that, these adults rabbits had a new pair of baby rabbits, which then mature into a new pair of adult rabbits for the following month. Thus, every month, any existing pair of adult rabbits had a new pair of baby rabbits and any baby rabbits at the start of the month are now fully grown adult rabbits. We can express the total number of rabbit pairs $F(n)$ in terms of the month $n$. Our model is therefore

$$ F(n) = F(n-1) + F(n-2) \quad \mbox{for } n \ge 2,\quad \mbox{ and } \quad F(0) = 0,\ F(1) = 1. $$

This is the Fibonacci sequence! The $n$-th Fibonacci number is called $F(n)$, which can be expressed as the sum of the $(n-1)$-th Fibonacci number plus the $(n-2)$-th Fibonacci number. Write a recursive program fib which computes the $n$-th Fibonacci number. How many base cases should you have? Ensure that your function correctly computes $F(10) = 55$.

Fibonacci sequences appear in various patterns in nature, including branching in trees, fruitlets of a pineapple and the flowering of the leaves of artichokes and pinecones to name a few.

My first job was a cashier job at a bakery (a bagel shop, actually) - let me know if you want some Montreal bagel secrets :) Every time I would give a customer back their change, I had to do the math in my head as to how many toonies, loonies, quarters, dime, nickels and pennies (pennies have since been obsoleted in Canada) I should give back to the customer. We can actually write a recursive algorithm to do this math for us. Suppose a customer gives you $n$ dollars to pay for something that costs $m$ dollars (and cents). You would then need to return $c = n - m$ in coins. How many toonies (2 $\$$), loonies (1 $\$$), quarters (25 cents), dimes (10 cents), nickels (5 cents) and pennies (1 cent) should you give back to the customer? Write a function that computes the total number of coins to return to the customer for a certain change of amount (in cents). Try to minimize the total number of coins you give them and assume you have an infinite number of each coin in your register. Verify that you return 3 coins for amount $ = 3.25 \$$ (325 cents) and return 8 coins for amount $ = 3.24\$ $ (324 cents).

Let's revisit the Fibonacci example above. Try to run fib(20), and then run fib(30). You can even be ambitious and run fib(40). What do you notice? It's really slow eh - in fact, I don't recommend trying fib(40) or you'll be waiting a loooong time! Well, even though writing a recursive function is elegant because it looks almost exactly like the math, it can be inefficient. So be careful when you write recursive functions.

The reason that our fib function is slow is because it recomputes many values that have already been computed. For example, let's expand fib(5):

$$ F(5) = F(4) + F(3) = (F(3) + F(2)) + (F(2) + F(1)) = (F(2) + F(1)) + (F(1) + F(0)) + (F(1) + F(0)) + F(1). $$

Notice how many times we are recomputing $F(n-2)$ since $F(n-1)$ depends on it. There are few ways around this: (1) store these previous values or (2) come up with a more efficient solution that does the solution backwards. We will see how to do the former in a few weeks, but the latter can be solved by keeping track of how many Fibonacci numbers we still need to compute in order to compute the $n$-th Fibonacci number, starting from $F(0)$. For example, if we want to compute $F(5)$, then we know that $F(0) = 0$ and $F(1) = 1$, so we need to compute $F(2)$, $F(3)$ and $F(4)$ to compute $F(5)$. This means that we have 3 Fibonacci numbers remaining to be computed. Whenever we want to compute those remaining Fibonacci numbers, they will require one less Fibonacci number to be computed (i.e. remaining-1). Check out the solution to this problem below. This is a pretty confusing solution to the Fibonacci number calculation, but it now allows you to compute fib(40) which we weren't able to do before. I suggest printing out the values (uncomment Line 4) to see the order in which fib_helper is called, and all the values for the previous, current and remaining Fibonacci numbers. Although this solution is much more efficient, it's much harder to read and understand.

And we're off, like a herd of turtles! -- Michael Scott

It's time to write your first graphics program! You will now be introduced to the turtle module. Just like the math module we used before, you need to import the turtle whenever you want to use it: importturtle. Since the turtle functions are all contained within this module, you will also need to use "dot notation" to call the turtle drawing functions.

Remember Lightbot from homework 1? The turtle is kind of like the robot in Lightbot. We will issue commands to the turtle, like going straight, turning left/right, and then it will draw some things to a new window! With just a few basic commands + some of the programming techniques we have seen so far, you can create some pretty neat drawings. Here are a few useful commands:

  • forward(distance): moves the turtle forward by some distance (in pixels),
  • backward(distance): moves the turtle backwards by some distance (in pixels),
  • left(angle): turns the turtle left by some angle (in degrees),
  • right(angle): turns the turtle right by some angle (in degrees),
  • up: lifts the turtle so that any call to forward or backward does not draw anything until we put the turtle back down,
  • down: puts the turtle back down so that we can draw stuff with calls to forward or backward
  • done: this tells the turtle that we're done drawing, so we can interact with the pop-up window properly.

To get a feel for the turtle click on the buttons on the right to go forward or backward by a certain distance, or to go left or right by some input angle. Try and draw a triangle, or some other shape (or letter).

   


Let's do some examples, so you can see how the turtle module works. We'll start off by drawing a square which has a side length of length (on each of the four sides). See if you can draw two cascading squares using this function. Note: after running the trinket, you will need to click the "Stop" button before re-running it.

We can draw cascading squares by using our square function twice, and making sure that we lift the pen (and then put it back down) in between calls to the squarefunction. Try typing this into the script portion of the trinket above.

Developing graphics programs can be useful for practicing with recursion. Try to write a recursive function called nestedSquares(length, level) which draws a square with a side length of length for a particular level, only if we are in the recursive step. Otherwise (we are in the base case), and we draw nothing. The recursive step should further call nestedSquares with a smaller side length (maybe make it smaller by 30 or so). You should also decrement the level by 1 during the recursive step so that you eventually get to your base case (which will be reached when either level is equal to 0, or the length becomes negative). Test your nestedSquares function by calling it with an initial length of 150 and 5 levels: nestedSquares(150,5).


Note: if you don't want to see the turtle "tracing" animation, you can set turtle.tracer(False) before doing any drawing commands, which will do the drawing without showing you the animation. This will be useful when you are performing a lot of drawing commands and don't want to wait for the animation to run.
Another note: turning the tracer off in repl.it doesn't seem to work: a workaround is to set the turtle "speed": setting turtle.speed(0) is the fastest.

Let's do another recursive example with the turtle. This time, we'll draw a spiral. Our spiral function will take in length that we would like to draw for the current level (same concept as the previous example). The base case will be if the current "level" is equal to zero, in which case we return (back through all the recursive function calls). Otherwise, in the recursive step, we will go forward by some length, then turn left by an angle of 30 degrees, and then keep recursing by calling spiral with a smaller length (95% of the current length) and decrement the level by 1. After drawing a part of the spiral and performing the recursive call, we would also like the turtle to return to it's starting position, so we need to re-orient the turtle by turning right by 30 degrees, and then moving backwards (undoing the forward call) by the same length.

© Philip Claude Caplan, 2021