Skip to main content Link Menu Expand (external link) Document Search Copy Copied

Lab 10

17 November, 2023 - Recursion & Hashable Objects

  1. PyCharm recap
  2. Overview of This Lab
  3. Hashable Objects
  4. Exercise 1: Hashable Number class (standard)
  5. Exercise 2: Sets (standard)
  6. Recursive Functions
  7. Exercise 3: Recursive Product (standard)
    1. Exercise 3 extra: Recursive Unfold Product (challenge, hard)
  8. Exercise 4: Recursive Reverse (standard)
  9. Exercise 5: Recursive Palindrome (standard)
  10. Exercise 6: Recursive Sequences (standard)
    1. Exercise 6a: Standard implementation (standard)
    2. Exercise 6b: Fast implementation (challenge, hard)
  11. Exercise 7: Tower of Hanoi (challenge, hard or very hard)
    1. Tower of Hanoi: Recursive Algorithm Explanation (challenge, hard)
  12. Exercise 8: Permutations (challenge, very hard)

Welcome to week 11, lab 10!

PyCharm recap

This week we continue using PyCharm and running code in the terminal. In lab 7 you can find information about: installing anaconda, opening projects, configuring unittests, reading unittests results, and debugging.

Overview of This Lab

This week we have … different exercises that range in difficulty:

All students, regardless of experience, should be able to complete the five standard exercises. Whether you complete all five is up to you.

The five exercises marked as “challenge” provide additional practice for interested students. We believe that any student in this class who completes the standard exercises should be able to complete the “medium” difficulty challenge.

For more advanced students, you might find the more difficult tower of hanoi and permutation exercises to be more interesting. Feel free to skip the standard exercises if you think they are insufficiently challenging. You can also look at previous labs for challenging exercises.

If you feel that this week’s challenges are too hard for you, feel free to do a challenging exercise from last week which should be easier now that you know more.

Hashable Objects

Dictionaries and sets are very useful datastructures. Sets can be used to store objects you have already seen (in a search algorithm) or create a list with unique objects. Sets are faster than normal lists if you want to know if an object is in either one of them. We already used dictionaries several times and one of their advantages is the fast lookup. Both sets and dictionaries achieve their speed by using hash functions.

Hash functions work by mapping a certain object to a place in memory. This way you do not have to search where the objects is in for example a dictionary, but you can calculate the location.

The downside of hash functions is that they need an immutable object as input because otherwise the location will change each time the object changes. This is the reason that string work as dictionary keys but list do not. A way to make any object work with sets and dictionaries is to make it hashable. This means that two magic methods are needed: __hash__ and __eq__. The magic method __hash__ contains the hash function and __eq__ is needed to determine when to objects are the same. Often the simplest way to make a hash function is to use an immutable attribute of your class and use the hash() function. Below, you find an example for a Person class.

class Person():
    def __init__(self, name):
        self.name = name
        
    def __hash__(self):
        return hash(self.name)
    
    def __eq__(self, other):
        return self.name == self.other
    
    def __repr__(self):
        return f"The name is {self.name}"

Exercise 1: Hashable Number class (standard)

In this exercise, you will create a hashable class “Number”. Open exercise number.py, follow the instructions and complete the class. Also, try to test how an object of your own class works when using it in a dictionary or set.

Exercise 2: Sets (standard)

In this exercise, you will practise with the use of sets. A set can be created similar to a list only difference is that sets use curly brackets {...} instead of square brackets [...]. A programming set is comparable to a mathematical set. There is no order (no index), it contains unique items, and it stores several objects. Another way to look at sets, is as a dictionary without values. For example, the set with the integers 1 and 2 can be created as follows: {1, 2}. Important note, an empty set can not be created with curly brackets {} as that syntax is already reserved for empty dictionaries. However, similar to other datastructures such as lists and dictionaries it can be created using set() with no argument.

Open exercise sets.py, follow the instructions and complete the functions.

Recursive Functions

Recursion is often an elegant way to write an algorithm. However, at one moment in time humans are often only capable of keeping track of a few recursive steps. For example, without practise people tent only to think a few steps a head in chess. Therefore, it is often hard to come up with a recursive algorithm. In A&DS, you will get a lot more practise with it but for now we want to give you some tips and tricks.

The first step into making a recursive algorithm is te recognize if a problem can be recursively solved (or is suitable for it). A problem is most suitable for recursion if, at one point in the algorithm, the next step can be calculated without knowing what the previous steps were and any outside information. For example, in chess you don’t need to know what happened before a certain move to do the next. Ofcourse most people use certain strategies which consists of previous moves, but technically each bord configuration has its optimal move which can be determined by just examining the bord.

The next step is to make the recursive algorithm which consists of a base case and a recursive step. Some people like to think about the base case first and vice versa. For now, let’s start with the recursive step.

The best tip for coming up with a recursive step is to think about a small step you can do that needs the same algorithm to solve the step but makes it a little bit smaller. This is a bit cryptic so let’s examine an example. Let’s say we want to solve the problem of summing up the following list of numbers:

numbers = [1, 4, 3, 6]

Think about a small step you can do, which result in the same problem. The easiest solution would be just do nothing and repeat the problem. However, this would lead to an endless loop of doing nothing. So, we need to make the problem smaller. One option for calculating the sum of a list would be to take the first number, repeat the problem with the rest of the list and added those numbers together. Thus:

def recursive_sum(numbers):
    ...
    
    first_number = numbers[0]
    smaller_problem = recursive_sum(numbers[1:])
    return first_number + smaller_problem

Note, that sometimes a recursive step splits into multiple smaller numbers. We could (needlessly) simulated this by splitting the list in two parts after taking the first number. This would create two smaller problems. Just a note for more advanced programmers, the only upside of this approach would be to limit the recursive depth.

def recursive_sum(numbers):
    ...
    
    first_number = numbers[0]
    middle = len(numbers) // 2
    smaller_problem1 = recursive_sum(numbers[1:middle])
    smaller_problem2 = recursive_sum(numbers[middle:])
    return first_number + smaller_problem1 + smaller_problem2

There is a reason that both function have dots because we did not add a base case. A base case is a moment in the recursive algorithm when you can’t make the problem smaller or the problem is at its smallest. Another way to say this is the base case determines when the algorithm needs to stop. Often a base case is just an if statement to check for a certain condition. In our example, there are two possible base cases. Think for a moment what these base cases could be? In other words, ask yourself when should you stop the recursion?

Maybe the most natural base case would be when the input of the function is an empty list. The reason is very simpel the sum of an empty list is always zero. However, you could argue that when a list only contains one element you also know the sum. Below, you will find the final recursive algorithm.

def recursive_sum(numbers):
    if not numbers:
        return 0
    
    first_number = numbers[0]
    smaller_problem = recursive_sum(numbers[1:])
    return first_number + smaller_problem

Exercise 3: Recursive Product (standard)

In the example above you saw how to implement sum recursively. Here, you will implement product recursively. The product of a list is all the number multiplied together. For example, the product of the list [1, 2, 3] is 6. Open exercise product.py, follow the instructions and complete the recursive function recursive_multiply.

Exercise 3 extra: Recursive Unfold Product (challenge, hard)

In this extra exercise, you will expand the previous implemented recursive product to be able to calculate the product of nested lists. In other words, if you would unfold a nested list into a one dimensional list and take the product over that list. For example, the product over the following nested list [2, [[3, 1], 4]] would be 24. Open exercise product.py, follow the instructions and complete the recursive function recursive_unfold_multiply.

Exercise 4: Recursive Reverse (standard)

In this exercise, we will recursively reverse a sequence which is either a list or a string. Open exercise reverse.py, follow the instructions and complete the recursive function. Even though unittest are provided, check with a small script and print statements how your function works and if it works as expected. Often, this is easier to debug then understanding why an unittest fails.

Tip: Try to think about how you could reverse one item in a list assuming the rest is already reversed.

Exercise 5: Recursive Palindrome (standard)

In this exercise, we will reversely check if a sequence is a palindrome and create a palindrome from a given sequence. A palindrome is a sequence of words, letters or numbers that reads the same backwards as forwards. For example, radar is a palindrome because when you reverse the word it is the same. Another example would be the sequence [0, 1, 1, 0]. It does not matter if a sequence has an oneven or even length as long as it is the same backwards as forwards. For more information on palindromes you can visit the wiki.

Open exercise palindrome.py, follow the instructions and complete the recursive functions.

Exercise 6: Recursive Sequences (standard)

Last week, you made iterable classes for several integer sequences. In this week’s exercise, you will make a recursive function to calculate a specific index in the sequence. In this exercise, we will use the following sequences:

 - Fibonacci        (0, 1, 1, 2, 3, 5, 8, 13, 21, 34) p(n) = p(n-2) + p(n-1)
 - Tribonacci       (0, 0, 1, 1, 2, 4, 7, 13, 24, 44) p(n) = p(n-3) + p(n-2) + p(n-1) 
 - Powers of three  (1, 3, 9, 27, 81, 243, 729, 2187) p(n) = p(n-1) * 3
 - factorial        (1, 1, 2, 6, 24, 120, 720, 5040)  p(n) = p(n-1) * n

Exercise 6a: Standard implementation (standard)

Open exercise recursive_sequences.py, follow the instructions and complete the recursive functions.

Exercise 6b: Fast implementation (challenge, hard)

Even though recursive function are very elegant solutions in a lot of situations, often they are not very fast in their basic form. Let’s investigate what behind the scenes is needed to calculate the 8th fibonacci number. Open this link and in frames you can see the stack of recursions. Note, how many steps it takes to calculate the 8th fibonacci number. Think about why it takes so many steps?

You probably noticed that a lot of fibonacci number are calculated numerous time. You can draw a calculation tree which shows you this very clearly. Below you can see such tree. Here, you can see the steps that need to be taken to calculate the 7th fibonacci number.

image

As you can see, calculating the fibonacci sequence this way is not very efficient. Imaging you need multiple fibonacci number during your program, this would be very slow and inefficient. The core problem is that each recursion you have two recursion steps. An easy solution would be to just remember all the fibonacci numbers you calculated. Open this link and have a look how this would work. Notice, that this code takes significantly fewer steps to calculate the 8th fibonacci number.

Ofcourse rewriting both codes would result in a different number of steps on the waterloo website. However, we can also have a look at speed. Open recursive_speedtest.py and run the file. The 35th fibonacci number is chosen to show the difference but make the wait time manageable. you can try different numbers to see what happens. However, keep in mind that going from the n to (n+1) fibonacci index takes almost twice as long for the basic implementation.

In recursive_speedtest.py is also a test added to calculate the 900th value of the sequence power of three. Here, it does not matter which implementation you use. Why does it not matter now? (think about how this calculation tree would look like).

The fast recursive function for the fibonacci sequence is already implemented in the examples. Now, make a fast recursive function for the sequences:

 - Padovan     (1 ,1 ,1 ,2 ,2 ,3 , 4, 5, 7, 9)   p(n) = p(n-3) + p(n-2)
 - Tribonacci  (0, 0, 1, 1, 2, 4, 7, 13, 24, 44) p(n) = p(n-3) + p(n-2) + p(n-1)

Open exercise recursive_sequences_memory.py, follow the instructions and complete the recursive functions.

A final educational note, coding a recursive function where you remember previous calculation is often called dynamic programming. In your next course, A&DS, you will learn more about this.

Exercise 7: Tower of Hanoi (challenge, hard or very hard)

In this exercise, you will implement the fastest solution to solve the tower of hanoi problem for any number of blocks. The tower of hanoi is a well known toy/problem where you need to move a tower from rod A to rod C. The tower exist of several disks with different size. While, this problem seems trivial, it is not when you need to follow the following rules:

Below you can see the start position of the tower of hanoi problem with three disks. Note, that the tower of hanoi can have any number of disks.

image

This problem is very well suited for a recursive solution and if you really want to challenge yourself, you can open the file tower_of_hanoi.py, follow the instructions, and try to solve the problem. As a guideline, the number of steps it takes to solve this problem is 2n - 1, where n is the number of disks. For students that want a challenge but not that hard, you can read the explanation of the recursive algorithm below.

Tower of Hanoi: Recursive Algorithm Explanation (challenge, hard)

The reason that the tower of hanoi problem lents itself very well for a recursive solution is that for any number of disks the same three steps need to be taken. When you want a tower from a source rod to a destination rod you can follow these steps:

You may have noticed that step 1 and 3 are not necessarily legal moves (step two is). However, step 1 and 3 are just moving a tower from one rod to another. Therefore, step 1 and 3 can be complete in the following exactly the same three steps described above. This looks like a infinite loop of repeating the same steps but note that each time the tower becomes one disk shorter. Thus, eventually step one and three are legal moves because the top of the tower only consists of one disk.

Below, you can see an example for the a tower of hanoi with three disks. The first three steps can be seen here:

image

Then, step 1 in the previous image can be solved as follows:

image

Finally, step 3 of the first image can be solved like this:

image

Open exercise tower_of_hanoi.py, follow the instructions and complete the recursive function.

Exercise 8: Permutations (challenge, very hard)

In lab 8 Using 2Dvectors: shortest path, you could have used itertools.permutations to find the shortest path by just trying all orders of the list with coordinates. In this exercise, we will make our own permutation function. Generating permutations is not any easy task but making them recursive is a bit easier. Think about what each step of the recursion should do and how to yield each permutation back. Tip: First, just try to print all the permutations.

If you want you can open exercise permutations.py, follow the instructions and complete the recursive function. However, below we will give you some hints on how to do this.

Hints: