This lab has you write several recursive algorithms. Writing recursive functions can be tricky, so make sure you take time to think about the following issues before you start typing:
L, you might try recursing on L[1:] and then figuring out what to do to combine the information in L[0] and the result of the recursive computation on L[1:].
It's easy to get stuck when you're working on recursion. Once you've come up with some test cases and have ideas for what the base case should be, ask for help if you're not confident about how to implement a solution.
A palindrome is a word or phrase that reads the same forwards and backwards. Here are some examples:
You will be writing an is_palindrome function to solve this problem. Before you start this process, write a main program that calls is_palindrome on the examples listed above and prints the results. Also call is_palindrome on some strings that are not palindromes.
Now that you have some tests in place, write a recursive function is_palindrome that takes a string as a parameter and returns true if its parameter is a palindrome, and false otherwise. Remember you can slice strings in Python. As an example of slicing, 'abcdefg'[2:5] is 'cde'. You can even slice from the end using negative numbers: 'abcdefg'[1:-3] is 'bcd'. In Java, you use the String method substring.
Hint: What are your base cases?
See recursion.py and Recursion.java.
Two strings are anagrams if and only if they contain exactly the same characters, used the same number of times. For example, ate and eat are anagrams, as are The eyes and They see. Uppercase and lowercase letters are often treated the same, so Eleven plus two and Twelve plus one can be considered anagrams.
Write a recursive function anagrams that takes a string as a parameter and returns a list of all of the anagrams of that string. Don't worry if your anagrams list contains duplicates (when would the list contain duplicates?).
Hint: Take out a piece of paper and write down what anagrams returns on the empty string. What if you call it with 'a'? How about 'ab'? 'bc'? 'abc'? How does the answer for the shorter strings help you build the answer for longer strings?
Write a main program that calls anagrams on "a", "horse", "smart", and "cat" and prints the results.
Humans often use the base 10 number system, where we use the digits from 0 to 9. When we write a number, each digit represents an increasing power of ten. For example, the decimal number 101 is 1 * 100 + 0 * 10 + 1 * 1 = 1 * (10^2) + 0 * (10^1) + 1 * (10^0) = 101.
In the base 2 number system there are only two possible digits: 0 and 1. These are often called bits. Each bit is an increasing power of 2 (that is, each bit counts for twice as much as the bit to the right), so the binary number 101 is 1 * 4 + 0 * 2 + 1 * 1 = 1 * (2^2) + 0 * (2^1) + 1 * (2^0) = 5.
Here is a table of the first 8 non-negative numbers in both binary and decimal.
| Binary | Decimal |
|---|---|
| 0 | 0 |
| 1 | 1 |
| 10 | 2 |
| 11 | 3 |
| 100 | 4 |
| 101 | 5 |
| 110 | 6 |
| 111 | 7 |
| 1000 | 8 |
Again, before you start solving the problem, write a main program that calls binary_rep on some of the examples listed above and prints the results.
Now that you have some tests in place, write a function binary_rep that takes a non-negative integer as a parameter and returns the binary representation of that number (as a string of 0's and 1's).
Hint 1: you can figure out the least significant binary digit by using the remainder operator: number % 2. You can also use integer division to get rid of the last digit, halving the number. For example, 19 % 2 is 1, and 19 / 2 is 9.
Hint 2: You need to do the recursive call and then append either a 0 or a 1 to that result.
Hint 3: What are your base cases?
In the previous section, you wrote code to convert from base 10 to base 2. Extend your code to permit conversion between any bases between base 2 and base 36 inclusive. Your function will need at least three parameters.
Digits higher than 9 are often represented with letters, with A=10, B=11, C=12, etc. For example, the base 16 number DEADBEEF is equal to 3735928559 in base 10.
Test your code by round-tripping some value: that is, convert a number from one base into another one, then convert that result back into the first. You should get the same value back out. What are good numbers to test? What are poor testcases?
Writing a maze solver is a fantastic recursion exercise. This part requires a lot of prep work (reading input files, building a Maze class, writing a solver). It is open-ended in the sense that you can involve exception handling (what to do with badly-formed input files?), graphics, and stacks and queues. (Stacks and queues can be used to write iterative solutions.)
Click for an example of a maze. It must be completely enclosed by walls, which are represented by #. There is one start point, represented by the number 1. There is one end point, represented by the number 2.
The goal is to have your program solve the maze so that it now includes a path from the number 1 to the number 2. We will represent the path using '.'. Furthermore, if your program looked at a square but didn't use it in the solution, it should be marked with an 'x'. If your program didn't look at a square at all, it should remain as a space. Here is a possible outcome of the same maze.
You are encouraged to create and post your own mazes on the discussion board. (Please use a single thread for this.)
Print the maze and try it yourself. As you solve it, keep track of .'s and x's. Do one square at a time. Of course, you can't move into walls, and you have to move into spaces to try them out, but should you try to move into .'s? How about x's?
Don't skip this step!
Your program will have a class called Maze whose constructor takes as a parameter a filename (as a string) or an open input stream. Store the maze contents in a list of lists (each sublist represents a row in the maze, and is a list of 1-letter strings or chars). You may have other instance variables as well if you like.
Class Maze must also have a method solve that has no parameters. This method solves the maze and modifies the list of lists as appropriate.
Method solve must make use of a recursive method try_to_solve that has two parameters: r (the current row number), and c (the current column number). This method returns true or false depending on whether a solution was found involving the current coordinate. The maze contents should be modified with .'s and x's as appropriate.
Which coordinate will you start at?
This part requires the Python Imaging Library.
Red eye is often a problem with pictures. In this section, you'll write a recursive program to remove red eye.
The Python Imaging Library (PIL) is an image-manipulation library. These two lines open a picture:
from PIL import Image
im = Image.open("RedEye.jpg")
This line saves an image into a new file called NewRedEye.jpg.
im.save("NewRedEye.jpg")
Pixel (160, 290) is a red pixel in one of the eyes. You're going to write code to change it, and all other red pixels in that eye, to black. But first, some colour theory.
Each pixel is a tuple made up of a red, green, and blue component, each a number in the range 0 to 255. The higher the value, the more of a colour there is. Bright red is (255, 0, 0), green is (0, 255, 0), and blue is (0, 0, 255). If you mix these three colours in varying amounts, you can make other colours. White is (255, 255, 255), and black is (0, 0, 0). Turquoise is something like (64, 224, 208), brown is (165, 42, 42), and so on.
The distance between two colours is defined to be the Euclidean distance: subtract the individual components, and compute the square root of the sum of the squares of those differences:
def distance(c1, c2):
'''Return the distance from colour c1 to colour c2, where c1 and c2 are
tuples representing (red, blue, green) values.'''
red_diff = c2[0] - c1[0]
green_diff = c2[1] - c1[1]
blue_diff = c2[2] - c1[2]
return math.sqrt(red_diff ** 2 + green_diff ** 2 + blue_diff ** 2)
We have provided redeye.py, which contains starter code. Complete it so that it removes the red eye at pixel (160, 290); start with 20 as the distance and adjust it until you find the right value.