CS106X Autumn 2009

Handout 13

Recursion

October 5th, 2009

Today we'll start working with one of CS106Xs neatest ideas: recursion. Recursion often does the trick whenever the problem to be solved can be broken down into virtually identical (though smaller) sub-problems. The classic introductory example employing recursion is an implementation of the factorial function:
int factorial(int n) { if (n == 0) return 1; return n * factorial(n - 1); }

Go ahead and start reading through Chapters 5 and 6. Your third assignment is going out on Friday, and its all about recursion and recursive backtracking, so read! !

Every recursive function lists a sequence of base cases, and then one or more recursive cases. Occasionally, the problem to be solved is so simple that we can return or terminate execution without any further computation. The first of the two lines in factorial is an example of such a base casefactorial(0) is always 1 and is easily understood. However, whenever the specified integer n is larger than 0, it helps to calculate factorial(n-1) and multiply the result of that computation by n itself. That's precisely what the recursive call is doing. We'll be spending the rest of this week and all of next week learning recursion. Recursion is difficult to understand the first time you see it, so be patient if it doesnt click right away. Ill be covering many of the examples covered in the reader, but I dont reproduce those here. I do, however, have a good number of examples that arent in the reader, and thats what this handout is all about.

2 Fractals I [Courtesy of Eric Roberts] Although fractals have been a mathematical curiosity for more than a century, modern interest in fractals as a practical tool can be traced largely to Benoit Mandelbrot, a researcher at IBM who made an extensive study of the field. As a way of getting people to understand the concept, Mandelbrot posed the following question: How long is the coastline of England? You can look up an answer in an encyclopedia, but that answer turns out to be meaningless unless you know the level of granularity at which it is measured. As you move through successively finer scales, the coast grows progressively longer as you count the length of each little peninsula or inlet. The coastline problem in the text provides the background for one of todays example. Because the fractals come out a little cleaner if you do so, weve changed the dimensions of the triangle from the one in the text so that the angle of the bump in the fractal line is 45 rather than 60 degrees, like this:

45

The code for the finished implementation of DrawCoastline looks like this:
int main() { InitGraphics(); MovePen(0, GetWindowHeight()/2); DrawCoastline(GetWindowWidth(), 0, 7); return 0; } void DrawCoastline(double length, double theta, int order) { if (order == 0) { DrawPolarLine(length, theta); } else { int sign = (RandomChance(0.5)) ? 1 : -1; DrawCoastline(length / 3, theta, order - 1); DrawCoastline(length / (3 * sqrt(2)), theta + sign * 45, order - 1); DrawCoastline(length / (3 * sqrt(2)), theta - sign * 45, order - 1); DrawCoastline(length / 3, theta, order - 1); } } void DrawPolarLine(double length, double theta) { double dx = length * cos(3.1416 * theta / 180); double dy = length * sin(3.1416 * theta / 180); DrawLine(dx, dy); }

3 Fractals II: Boxy Snowflakes Assume youre given the following function, which draws a shaded square of the specified dimension with a solid border, centered at (cx, cy):
void DrawFilledCenteredSquare(double cx, double cy, double side);

Presented below is the recursive implementation of DrawFractal, which is capable of drawing the following order-0, order-1, order-2, and order-3 fractals:

Note our implementation is sensitive to the way the centered squares are layeredclearly the sub-fractals drawn in the southwest and northeast corners are drawn before the large center square, which is drawn before the sub-fractals at 4:30 and 10:30. The same layering scheme is respected at all recursive levels:
void DrawFractal(double cx, double cy, double side, int { if (order >= 0) { DrawFractal(cx side/2, cy side/2, 0.4 * side, DrawFractal(cx + side/2, cy + side/2, 0.4 * side, DrawFilledCenteredSquare(cx, cy, side); DrawFractal(cx side/2, cy + side/2, 0.4 * side, DrawFractal(cx + side/2, cy side/2, 0.4 * side, } } order) order 1); order 1); order 1); order 1);

4 Listing All Subsets The reader invests a good amount of energy talking about how to generate all of the permutations of a stringthat is, how given the string PDQ you can programmatically generate: PDQ PQD DPQ DQP QDP QPD The recursive formulation is easily explained in English, but coding it up is a different matter, so well definitely talk about the permutations problem in lecture (though I dont repeat the code here.) A different but related problem asks not for the permutations of a string, but rather the list of ordered subsets. Given the string "ABCD, for instance, figure out how to print all 16 ordered subsets/subsequences"ABCD", "ACD", "BD", "C", and "" are five of the 16 strings that would need to be generated.
/** * Snapshot: Subsets * ----------------* Exhaustive recursive function to print the 2^n subsets. * At each level of recursion, take the first char of rest * and try both in the subset and out of the subset, * recur from there to try further choices. You hit the * base case when you run out of choices (rest is empty) */ void Subset(string rest, string soFar) { if (rest.empty()) { cout << soFar << endl; return; } Subset(rest.substr(1), soFar + rest[0]); Subset(rest.substr(1), soFar); } void ListSubsets(string str) { Subset(str, ""); } // recur with rest[0] included // recur with rest[0] excluded

5 The Periodic Table As Lexicon [courtesy of Keith Schwarz, CS106L Instructor] Have you ever wondered what English words can be spelled using just the symbols from the periodic table? Youre about to find out. The periodic table lists abbreviations used for all of the known elementshydrogen, lithium, oxygen, carbon, molybdenum, uranium, and so forth. Each element has its own one, two, or three-letter symbol: H for hydrogen, Li for lithium, Mo for molybdenum, Uub for Ununbium etc. All in all, there are 117 elements, so there are 117 abbreviations. For this problem, were pretending that these symbols are the 'letters' of a new alphabet. Your task here is, given a Vector<string> storing all element symbols and a Lexicon of all English words, to print out all those English words that can be constructed using just the symbols from the periodic table. You should only print out words of length 11 or more, and you should retain the capitalization scheme of the atomic symbols when printing out the words. Heres a small window of the words that should be printed out:
... IrReSOLuTiON IrReSOLuTeNEsS IrReSOLuTeNeSS IrReSPONSiBILiTiEs IrReSPONSiBiLiTiEs IrReSPONSIBILiTiEs IrReSPONSIBiLiTiEs ...

Ir is iridium, Re is rhenium, S is sulfur, O is oxygen, Lu is lutetium, etc.: Trust that every capitalized substring identifies some element from the periodic table. The solution builds on a working prefix up from the empty string by recursively considering every single symbol in the periodic table as a possible extension. If you construct a string that isnt even a prefix of a word, then you prune that search, recognize your dead end, and back off. But if you notice that the working string is actually a word, then as a side effect you print the string out and dig even further for a longer word beyond what you already have.
void Print(Vector<string>& elements, Lexicon& lex, string soFar) { if (!lex.containsPrefix(soFar)) return; if (lex.containsWord(soFar) && soFar.length() > 10) { cout << soFar << endl; } for (int i = 0; i < elements.size(); i++) { Print(elements, lex, soFar + elements[i]); } } void PrintAllWords(Vector<string>& elements, Lexicon& lex) { Print(elements, lex, ""); }