The exercises in this chapter were some of the most challenging exercises I have encountered in this book. It took me a while to wrap my head around recursion and in many ways, I’m still processing the concept. My understanding of recursion is that it is a kind of backwards iterating loop that continuously calls on itself until some condition — the base case — is met. Then, it builds back up to the surface, bringing solutions of each level with until it arrives at the final result. Algorithmic inception, if you will.
I did these exercises back in December, so my process for coming to the solutions might be a bit hazy. So please excuse any vagueness in my discussions of each problem. Yeah, as it turns out, I had a ton to say about each problem. I even included some of the “easier” problems, because both working on and writing about them helped me get a better understanding of how recursion works.
As always, if you’re currently going through the book, please do the problems yourself first, and then take a look at what I’ve done here. And of course, as per usual, the final code for each problem can be found on GitHub.
And one more thing before we get into the problems. For some, I’ve used Trinket so you can run the code and see the results in real time. Thought that would be more fun for the Turtle graphics based exercise that have some degree of randomness in their generation. Just press the little play buttons where you see them.
Problem 1: Factorial
Write a recursive function to compute the factorial of a number.
This took a surprising amount of time for me to get, as I was still trying to understand exactly how recursion worked. Plus, I was used to using built in functions to calculate the factorial. As such, the method I using previously built loops as a basis for understanding in later problems, would not work here.
As you can see from the code below, the solution was fairly straightforward. A factorial represents all possible combinations of \(n\) number of things. It’s calculated by multiplying all numbers between \(n\) and 1 in descending order (I mean the order really doesn’t matter, but when you’re trying to get a program to do it, especially recursively or within a loop, having some kind of sequence to follow is important).
With this definition, a person would intuitively start multiplication process with \(n\) and stop it at 1. The computer does not. And that’s where the base case comes in. We need to tell the computer to check if the number is greater than 1. If it is, we compute the factorial. If it ain’t, we return 1.
Buuut.. we’re still not done, because we still have to deal with the cases of 0 and negative numbers. (If I really wanted to be thorough, I would check for non-numbers as well and throw an error, but I didn’t need to do that for this particular exercise.) In the case of 0, there is only one possible combination of 0 things, so it’s taken care of by the base case. Negative numbers of things, however, cannot be combined in any tangible way, so we return nothing, at least for this particular exercise.
# Runestone.Academy thinkcspy course
# Chapter 16
# Problem 1
def computeFactorial(number):
if number < 0:
return
elif number > 1:
number *= computeFactorial(number - 1)
return number
else:
return 1
Result:
Problem 2: Reverse a List
Write a recursive function to reverse a list.
This is something I’ve done a few times in both JavaScript and Python with strings and lists/arrays. This gave me a foundation upon which to stand. However, I do think this may have given me some false confidence. To understand why, let’s discuss how I solved this same problem with a loop in Python.
I started with a new empty list. I, then, used a for loop to iterate though an existing populated list, adding each successive element of the existing list to the front of the new list.
def reverse(lst):
newlist = []
for num in lst:
newlist = [num] + newlist
return newlist
I want to emphasize how [num] comes before newlist in the above code. Had I instead done newlist = newlist + [num], the list would have come out in the same order it was already in, rather than reversed. This order is important for both the loop and recursive version of the problem.
Now let’s talk about why the rest of it was a bit of a red herring for the recursive solution of this problem. One, I didn’t need to initialize a new empty list, and two, I needed to use the existing list a bit differently. Simply iterating through each element and sliding it into the front of a new list would not be enough. I also needed to resend the existing list one element shorter to its parent function over and over until only the first element was left. From there, it would return that first element and then add the next element in front of it all the way until we finally got to the very last element of the previously unaltered list. In the end, we get the same result as the code above, but with more mind bending logic.
Modify the recursive tree program using one or all of the following ideas:
Modify the thickness of the branches so that as the branchLen gets smaller, the line gets thinner.
Modify the color of the branches so that as the branchLen gets very short it is colored like a leaf.
Modify the angle used in turning the turtle so that at each branch point the angle is selected at random in some range. For example choose the angle between 15 and 45 degrees. Play around to see what looks good.
Modify the branchLen recursively so that instead of always subtracting the same amount you subtract a random amount in some range.
If you implement all of the above ideas you will have a very realistic looking tree.
Realistic might be a stretch, but I can say that I was proud of the end product.
We had been working on this particular exercise throughout the chapter. This is what they started me out with (tracer was added in to speed it up):
Below are my changes to the code to get it up to what the instructions needed. Replacing hard coded numbers with randomized variables was relatively straightforward. I spent a lot of time tweaking the ranges to get something that would be aesthetically interesting in most generations. The part that actually threw me for a loop, though, was the coloring.
The color function, itself was fine. That was fairly straightforward, too. The real issue was that I didn’t reset the state of the color at the end of the tree function. So the trees were doing some weird color changing thing at odd points. Comment out the last line of the tree function (the one above main()) if you want to see what I’m talking about.
Problem 4: Fractal Mountain
Find or invent an algorithm for drawing a fractal mountain. Hint: One approach to this uses triangles again.
This one took me way too long, even with the code they started me out one:
Below is my code.. And uh you know what, when I finally got the result you’ll see when you hit that little play button, I was really fucking excited. I was under no delusion that my “mountain” was …. well it was/is certainly something lol. But man did it take me a minute to get this polygonal monstrosity to even approach the visual ballpark of a tectonic build up.
Remember how my issue in the last problem was getting the colors to cooperate, but the randomization was fairly straightforward? Well, in this exercise those issues switched. Colors? Really easy. All I had to do was switch out the existing list of colors. Getting the triangles to become a weird mass, however? Heh. Yeah no.
As you will see from the code, the key differences were the midpoints. I had to shift those bad boys around just enough to where they weren’t flying completely out of bounds, but also enough to where the pattern wasn’t so obvious. I had issues with both.
My first attempts had triangles flying all over the damn place. An onlooker would have been very confused about what I was trying to do. Hell, I was getting confused about what I was trying to do. The later attempts looked more like the one below, but it the pattern was too repetitive and obvious at every iteration. It looked more like a drunk Sierpinski triangle than a mountain.
At some point in this process, I changed the getMid function beyond repair, so I scrapped it and went back to the original. I hard-coded a single number into delta and then added the positive and negative values of that variable to the original midpoint calculations. This turned out to be the sweet spot. That and a fourth fractalMnt recursion to fill in the centers of the triangles. Below is the result of this process.
Problem 5: Fibonacci Sequence
Write a recursive function to compute the Fibonacci sequence. How does the performance of the recursive function compare to that of an iterative version?
This is honestly pretty similar to Problem 1. Same kind of process and honestly, pretty similar code. And like number 2, I had a JavaScript loop to compare it to. Here is the code for that:
const fibonacci = function(num) {
let fn1 = 0;
let fn2 = 0;
let fib = 0;
try {
newNum = parseInt(num);
if (isNaN(newNum)) {
throw new Error(`"${num}" is not a number.`)
} else {
if (newNum < 0 ) {
return "OOPS";
} else {
for (let i= 0; i <= newNum; i++) {
if (i === 0) {
fib = 0;
} else if (i === 1) {
fib = 1;
} else {
fn2 = fn1;
fn1 = fib;
fib = fn1 + fn2;
}
}
return fib;
}
}
} catch (error) {
return error;
}
};
And below is my recursive Python solution, minus the error handling:
# Runestone.Academy thinkcspy course
# Chapter 16
# Problem 5
def fibonacci(number):
if number < 0:
return
elif number == 0 or number == 1:
return number
else:
number = fibonacci(number - 1) + fibonacci(number - 2)
return number
print(fibonacci(10))
Result:
I gotta say, solving the fibonacci problem recursively is definitely the more concise solution. Playing musical chairs with variables in an attempt to store a constantly rotating cast of numbers is not the move.
Problems 6 and 12: Tower of Hanoi
I wanted to use Trinket so you could play around with the code, but certain methods and functions that I used to make this work aren’t loaded into the playground. Hopefully a screenshot and video will suffice. Later, when I have a better handle on how to integrate Python with web, I may create a version that is more interactive.
Problem 6
Implement a solution to the Tower of Hanoi using three stacks to keep track of the disks.
I don’t remember how I thought to put a function within a function, but I do remember why I did it. While not exactly necessary, I wanted to keep track of the number of rounds the program iterated through. This allowed me to check that the stuff that was supposed to happen on each round, was actually happening. Shot out to Math is Fun for giving me a place to visually simulate, and thus check, the rounds.
Anyway, here is the deal with the variable rounds. If I initialized it in hanoi and didn’t use it as a parameter, the number would be stuck at 1. If I initialized it in hanoi and also used it as a parameter, it would oscillate between 0 and 1. I didn’t want to turn it into a global variable, because it had no purpose as a global variable. So the solution that made sense in this context was one where I could get it as close to being a local variable as possible without it actually being local. That way when it got manipulated within hanoi, rounds would actually work as intended. But of course, trying to access a variable that isn’t global and isn’t local is an issue, because of scope. Using the keyword nonlocal, helped mitigate that issue.
Despite my verbosity in this post, I don’t really like reading unnecessary chunks of text. Seeing some bs like “Disk 1 moved from Rod A to Rod B” would have annoyed the living fuck out of me lol. So instead, I did the text version of visually moving the disks around by using lists. However, that also meant that I had extra work to do in terms of keeping track of disks within lists. So much for not playing musical chairs…
Alright, now we get out of the realm of Octavia’s compulsive tendency to be extra and into the real meat of this problem — moving the disks from rod to rod. In order for the program to play this game, not only did the disks have to move, the rods had to move too. Or more accurately, they needed to be repurposed. If ever you were ever in need of a reminder that computers don’t think like humans, this problem makes that extremely clear.
In the Tower of Hanoi, the goal is to get Rod C to look like Rod A by moving only one disk at a time and stacking smaller disks on top of larger ones. As people, we don’t need to move or relabel the rods to do this. We just need to move the disks.
But in a recursive solution like this, the role of a rod changes depending on the position of the disk being moved. Rod A is the start position for all disks in the beginning, just as B is the auxiliary, and C is the end. But as the disks get shifted around, each Rod has its turn in all of those roles. And if the program is to be ran successfully, this fact must be reflected within the code. As such, when hanoi is recursively called, the rods do a bit of a merry-go-round. It’s a bit of a mind bender, but it does help to reduce inefficiencies in other areas of the code.
# Runestone.Academy thinkcspy course
# Chapter 16
# Problem 6
def stackTowers(num):
A = []
B = []
C = []
rounds = 0
for i in range(num):
A.insert(0, i+1)
def hanoi(num, start, aux, end):
nonlocal rounds
if num == 1:
end += [start.pop()]
rounds += 1
print(rounds, A, B, C)
else:
hanoi(num - 1, start, end, aux)
end += [start.pop()]
rounds += 1
print(rounds, A, B, C)
hanoi(num - 1, aux, start, end)
hanoi(num, A, B, C)
stackTowers(4)
Result:
Problem 12
Modify the Tower of Hanoi program using turtle graphics to animate the movement of the disks. Hint: You can make multiple turtles and have them shaped like rectangles.
I think the hardest part about this was getting the turtles to line up properly on the actual rods in a way that made visual sense. The initial stacking was straight forward enough. I just needed to move them to the \(x\) position of the Rod A and adjust the position depending on the number of rods. Moving them, however, was a different story. My initial attempts had disks flying out of frame, stacking around the rods, hanging out way above or below the them, and even stacking inverted even though the disks themselves were moving in the right order. It was a mess lol.
In order to get the disks to stack with visual logic, I needed to create the dictionary, rods, in stackTowers so that the contents of each pole could be viewed in moveTurtles. Then, I needed to create the dictionary rodsPos, so that I could move the disks to the correct locations on the x-axis. To get the disks stacked appropriately on the y-axis, I needed an account of what was already on the target rod so that the smaller disks would land above of what was already there.
# Runestone.Academy thinkcspy course
# Chapter 16
# Problems 6 and 12
import turtle
import random
def stackTowers(num, turts):
A = []
B = []
C = []
rods = {"A":A, "B":B, "C":C}
for i in range(num):
A.insert(0, i+1)
def hanoi(num, start, aux, end, turts):
if num == 1:
end += [start.pop()]
moveTurtles(turts[end[-1] - 1], rods)
else:
hanoi(num - 1, start, end, aux, turts)
end += [start.pop()]
moveTurtles(turts[end[-1] - 1], rods)
hanoi(num - 1, aux, start, end, turts)
hanoi(num, A, B, C, turts)
def createRods(t):
for i in range(3):
t.penup()
t.goto(300*(i-1), 100)
t.pendown()
t.right(90)
t.forward(200)
t.left(90)
def generateColor():
r = random.randint(0, 255)
g = random.randint(0, 255)
b = random.randint(0, 255)
hexColor = "#{:02X}{:02X}{:02X}".format(r, g, b)
return hexColor
def createTurtles(num):
turtles = []
for i in range(num):
newTurt = turtle.Turtle()
newTurt.shape("square")
newTurt.shapesize(1/2, (i+1)*2, 1)
newTurt.color(generateColor())
newTurt.penup()
newTurt.goto(-300, (num*15 - 100) - i*15)
newTurt.name = str(i+1)
turtles.append(newTurt)
return turtles
def moveTurtles(turt, rods):
rodPos = {"A":-300, "B":0, "C":300}
x = turt.xcor()
y = turt.ycor()
for rods, turtList in rods.items():
if int(turt.name) in turtList:
x = rodPos[rods]
y = len(turtList) * 15 - 100
turt.goto(x, y)
def main():
num = 8
tRod = turtle.Turtle()
tRod.pensize(5)
wn = turtle.Screen()
createRods(tRod)
turts = createTurtles(num)
stackTowers(num, turts)
wn.exitonclick()
main()
Result:
Problems 9 and 10: Jugs
Problem 9
Write a program to solve the following problem: You have two jugs: a 4-gallon jug and a 3-gallon jug. Neither of the jugs have markings on them. There is a pump that can be used to fill the jugs with water. How can you get exactly two gallons of water in the 4-gallon jug?
Lol the hardest part of this exercise wasn’t the coding, it was figuring out the riddle, lol. Spoiler Alert: The key is to completely fill the larger jug with the contents of the smaller one, so that once the larger one is full, the smaller jug is left with just 2 gallons. Then the larger jug can be emptied and then refilled with the remaining two gallons.
The way I achieved this was to create a dictionary for each jug that specified their capacity and current state. From there, a “tap” would fill the the smaller jug which would fill the larger jug in turn. If the larger jug has reached capacity it would be emptied. This process would repeat until the target was reached.
Problem 10
Generalize the problem above so that the parameters to your solution include the sizes of each jug and the final amount of water to be left in the larger jug.
I didn’t really understand what I was being asked to do. To some extent I’m still not sure what’s being asked. However, coming back to write this problem did prompt me to consider a few things:
What happens if the target and Jug A’s capacity are the same?
What happens if the target is higher than Jug A’s capacity?
What if some silly person decides to create a negative target?
I probably should have also thought about if someone added a string, but this isn’t going into production. It ain’t that deep (at least not yet).
In any case, my understanding of “generalize the problem” is that, no matter the size of the jugs or the target, the program should work. So I added code to address those three points. Below is the final result.
# Runestone.Academy thinkcspy course
# Chapter 16
# Problems 9 and 10
def fillJug(rounds, jugA, jugB, target):
pour = 0
if target > jugA["cap"]:
print("Target is too high. Reducing target to Jug A's capacity.")
target = jugA["cap"]
if target < 0:
return
if jugA["state"] == target:
print("Target reached")
return
else:
if jugB["state"] == 0:
jugB["state"] += jugB["cap"] #fill jugB
print(rounds, jugA, jugB)
if jugA["state"] == 0:
pour = jugB["state"] - jugA["state"]
else:
pour = jugA["cap"] - jugA["state"]
#fill jugA with the contents of jugB
jugA["state"] += pour
jugB["state"] -= pour
print(rounds, jugA, jugB)
if jugA["state"] == jugA["cap"] and jugA["state"] != target:
jugA["state"] = 0 #empty jugA if full
print(rounds, jugA, jugB)
fillJug(rounds + 1, jugA, jugB, target)
def main():
jugA = {"name": "Jug A", "state": 0, "cap": 4}
jugB = {"name": "Jug B", "state": 0, "cap": 3}
target = 2
return fillJug(1, jugA, jugB, target)
main()
Result:
Problem 11: Missionaries and Cannibals
Write a program that solves the following problem: Three missionaries and three cannibals come to a river and find a boat that holds two people. Everyone must get across the river to continue on the journey. However, if the cannibals ever outnumber the missionaries on either bank, the missionaries will be eaten. Find a series of crossings that will get everyone safely to the other side of the river.
This one was actually kind of fun! I mostly used a virtual canvas (shot out to Trilium Notes!) to work out how to solve this. The key was to make sure that at least one cannibal was in the boat at all times until all the missionaries were safely on the other side. From there, I just needed to create a series of tests to ensure that the ratio of missionaries to cannibals would always be 1 to 1 or higher on the side of the missionaries before transporting anyone from one side of the bank to the other. Here is my solution:
Side note: As I was writing this, I did catch an issue where the program was returning “None” at the end instead of “Journey Complete”. Turns out I needed to add the return keyword to the recursive call in cross. I could have achieved the same effect if I simply printed “Journey complete” and removed all the return keywords from the entire program, but this change was simpler.
Problem 13: Pascal’s Triangle
Pascal’s triangle is a number triangle with numbers arranged in staggered rows such that
\(a_{nr} = {n! \over{r! (n-r)!}}\)
This equation is the equation for a binomial coefficient. You can build Pascal’s triangle by adding the two numbers that are diagonally above a number in the triangle. An example of Pascal’s triangle is shown below.
Write a program that prints out Pascal’s triangle. Your program should accept a parameter that tells how many rows of the triangle to print.
Full disclosure, I only fixed the formatting of the Pascal’s triangle after I started writing this post. The initial code for the format looked like this:
def createTriangle(numRows):
if numRows < 0:
return
else:
for i in range(numRows+1):
spaces = (" "*(numRows-i))
nums = f"{createRow(i)}"
print(spaces + nums + spaces)
def createRow(currentRow):
row = []
"""Code for getting the values of each row"""
result = " ".join(map(str, row))
return result
Which gave me a result that looked like this for 10 rows:
Kind of in the ball park but certainly nothing to write home about. At the time, though… I was basically like “good enough”, because as you can probably imagine, having gotten to the end of this very lengthy post, I was tired and ready to move on to other things. Shot out to the devs on Stack Overflow who helped me solve my formatting issue.
As for the rest of it, I had already figured out the factorial portion of this exercise in Problem 1. But I still needed to wrap my head around the concept of a binomial and reflecting numbers back so that I didn’t just end up with half a triangle. Because, once again, computers don’t think like people.
You and I can intuitively see the pattern of numbers being added for each row. The computer cannot. Plus, adding individual numbers isn’t exactly the most efficient or even effective way of solving this programmatically. So, I had to school myself in how Pascal formatted his triangle, which as (kind of) seen in the text for the instructions for this problem is \(\lfloor\frac{n!}{k!(n – k)!}\rfloor\), where \(n\) represents the current row of the triangle and \(k\) (written as \(r\) in the instructions) represents a position within that row. (In case you don’t know, the weird bracket thingies represent floor division. Yeah, I just learned that, too. )
And finally, we arrive at the last bit of code for this chapter. It’s been a journey, folks.
# Runestone.Academy thinkcspy course
# Chapter 16
# Problem 13
def createTriangle(numRows):
triangle = []
if numRows < 0:
return
else:
for i in range(numRows+1):
triangle.append(createRow(i))
lastRow = triangle[-1]
numWidth = len(str(max(lastRow))) + 1
triWidth = numWidth * len(lastRow)
for row in triangle:
triStr = ""
for num in row:
numStr = str(num)
triStr += numStr + " " * (numWidth - len(numStr))
print(triStr.center(triWidth))
def createRow(currentRow):
row = []
for i in range(currentRow + 1):
coefficient = getbinomial(currentRow, i)
row.append(coefficient)
return row
def getbinomial(n, k):
numerator = factorial(n)
denominator = factorial(k) * factorial(n - k)
return numerator // denominator
def factorial(number):
if number < 0:
return
elif number > 1:
number *= factorial(number - 1)
return number
else:
return 1
createTriangle(10)
Result:
Bonus: Koch Snowflake and Hilbert Curve
These aren’t actually bonus problems, these were actually part of the main set. However, I’ve done these kinds of L-System problems before in Chapter 9 and Chapter 10 and since the recursion piece — at least in the way that I solved them — is very small, I don’t feel it makes a ton of sense to discuss them here. But as a long time lover of fractals, I still want to include the results here. I may revisit them later and see if I can wrap more of the code into recursion. And if I do, I’ll update them here. Like everything else, the code for these is on GitHub.
Problem 7: Hilbert Curve
Using the turtle graphics module, write a recursive program to display a Hilbert curve.
Result:
Problem 8: Koch Snowflake
Using the turtle graphics module, write a recursive program to display a Koch snowflake.
