HW17: Recursion and Fractals

The goal of this assignment is to get experience writing recursive algorithms.

You may work with a partner on this assignment.

For the first part of this assignment, you'll use recursion to compute some values that are also straightforward to compute in other ways, just to give yourself some practice with it.

Create a file named recursion.py. In that file, write the following functions:

1. min(numlist) — takes a list of numbers as an argument, and returns the smallest. (Hint: the smallest number in a list is the smaller of two things: either the first item in the list, or the smallest item in the rest of the list.)
2. palindrome(word) — takes a string (of only lowercase letters; no spaces or punctuation) and returns True or False, depending on whether or not the argument is a palindrome (a word that is written the same backwards as forwards, like “tenet” or “deed”). (Hint: if the first and last letter are the same, and everything in between is a palindrome, then the whole word is a palindrome.)

Your code must contain no loops, and cannot use higher-level Python built-in methods: just recursion, along with indexing, comparison, binary operators, and the like. The arguments you pass to comparison operators must be of constant size: booleans, numbers, or strings of length 1 or less. Comparisons of whole lists or longer strings use loops under the hood, and so they are not allowed for this assignment.

Also write two testing functions — testMin() and testPalindrome() that run your functions on a few example inputs and verify that they return the correct values. Come up with challenging inputs, and remember that “big” is not the only type of “challenging”.

A Defter Palindrome Tester

When you're first learning about recursion, you spend a lot of time with little problems like those above (or computing factorials, or reversing strings, etc.). All of these problems can be solved pretty easily using loops, so a skeptic might say “recursion is cool, but why bother?”

Here's why. Some important problems are so naturally recursive that most people find it effectively impossible to solve them in a non-recursive way. For example, suppose you wanted to print out the complete list of all the permutations of a set (i.e. all the different ways you can order the elements of the set). If, say, your set is {goat, moose, emu}, then your permutations would be:

goat    moose   emu
goat    emu     moose
moose   goat    emu
moose   emu     goat
emu     goat    moose
emu     moose   goat

Permuting a set is tricky with recursion, but the resulting code is just a few lines long. (Notice any patterns in the case above, with 3 elements? Any ideas about how to do it with 4?) Permuting a set without recursion — well, let me just encourage you to think about how you would do that for a set of 10 items.

Another naturally recursive problem is the drawing of fractals — images that are identical or nearly identical to a sub-part of themselves. For a classic example of a fractal, take a look at Sierpinski's Triangle. If you look at just one corner of the full Sierpinski's triangle, what you see is another Sierpinski's triangle — just a little smaller. As with all recursive algorithms, you solve the big problem (“draw Sierpinski's triangle”) by breaking it into smaller problems of the same type (“draw three Sierpinski's triangles of half the height of the big one”).

The program sierpinski.py illustrates the kind of recursive technique you can use to draw Sierpinski's triangle (using the graphics.py library). Your job is to adapt these techniques to draw the figure below:

More specifically, in recursion.py, write a function squareFractal(levels) that takes an argument levels — the number of different sizes of squares to draw. The result of calling this function should be that the corresponding figure gets drawn in a new graphics window. You do not need to create a class to implement this functionality, though if it makes it easier for you, you're welcome to do so.

The example above has 4 levels of squares. The examples below have 2, 3, and 5 levels of squares, respectively.

Write a main function that asks the user for a number of levels, draws the correct fractal figure, and then waits for a nonce input (like the Sierpinski program does) so that the window stays open.

Submit your recursion.py on Moodle.

• min() — 3 points
• palindrome() — 6 points
• squareFractal() — 9 points
• Testing code and main function — 2 points
• Comments, style, and design — 5 points