Mar 6: Recursion
Definition:
- Recursion
- See recursion
Trees
The joke is not that far from the truth — recursion is basically when something is defined in terms of itself. To avoid an infinite regress, however, we have to make sure that there is some difference between the original and its self-referential definition, and that we know when to stop self-referencing. An example is a tournament. To find the best two players (or teams, depending on the type of tournament), we find the best from one half of the league and have them compete against the best from the other half. To find the best from one half, we pit the best from half of that against the best from the other half of that (the quarterfinals). And so forth, down to the initial set of players or teams. "The best" of a group is defined in terms of "the best" of a sub-group, and eventually the sub-sub-...-sub-groups are small enough (here, just one member) that we can stop.
Reas & Fry 22-09 shows how to draw something that looks kind of like a tournament (upside down). I've simplified it here. We start with the ability to draw a single "T":
line(x, y, x, y-r); // vertical line(x-r, y-r, x+r, y-r); // horizontal
Then we stack two smaller "T"s, of size r/2, on top of that "T" — one starting at (x-r,y-r) and the other starting at (x+r,y-r). To draw each of those "T"s, we do exactly the same thing, although the values used in the function are now different — the new x is the old x, plus or minus r, the new y is the old y minus r, and the new r is the old r divided by two. Then each of those "T"s stacks a pair of "T"s on top of it, and so on. To keep from getting microscopically small "T"s, we only continue stacking if r is at least 1.
void setup() { size(400,400); drawT(width/2, height, width/4); } void drawT(int x, int y, int r) { line(x, y, x, y-r); // vertical line(x-r, y-r, x+r, y-r); // horizontal if (r>1) { // only continue stacking if half size will be non-zero drawT(x-r, y-r, r/2); // stack on left side drawT(x+r, y-r, r/2); // stack on right side } }
[applet]
This looks kind of like a tree, though more like a family tree than a natural one. The Processing demo Topics | Fractals | Tree has a very similar approach in terms of doing recursion, but yields something more tree-like. Here we draw a line, and then split off two lines from the end of it. The first line is the trunk. We then translate() to the end of it, rotate() left and draw one branch, and rotate right and draw another branch. To draw a branch, we draw a line, translate to the end of it, and then rotate left and draw one sub-branch and right and draw another. And so forth. Each branch is smaller (2/3 the length) than the one that it grows out of. Thus we stop when the branches are too small (2 pixels). How much to rotate is controlled by the mouse.
Greenberg (2-01) gives an even cooler looking tree. I've simplified the code here to bring out the analogous recursive structure. This sketch doesn't use the translate/rotate approach, but instead explicitly keeps track of the (x,y) coordinates of where a branch starts. Then each branch is a "twisted" line rather than a straight one — put several random segments together going the same vertical distance, but with random offsets for the horizontal positions along the way. Furthermore, the branches are thicker at the bottom than at the top, and their lengths are random (with the possible length being varied as we go up the tree). The variable depth refers to how far away we are from the trunk (0 for the closest ones), so "deeper" branches are towards the top of the tree. Near the top of the tree, the branches are drawn greenish, to give an appearance of leaves. There are some magical choices made to control the branch lengths (e.g., in the difference in the length adjustment for deeper branches); I've left the basic structure intact, but they don't give quite the same effect as in Greenberg's sketch.
// how many recursions drawing branches, and overall (rest drawing "leaves") int branchDepth=4, leafDepth=6; void setup() { size(900,600); background(255); // trunk strokeWeight(40); stroke(30,10,5); float trunkLength = random(130,180); int numTrunkSegments = floor(random(7,12)); float x = orgLine(width/2,height, width/2,height-trunkLength, numTrunkSegments, 22); // begin branching from top of trunk branch(x, height-trunkLength, 0, 25, 50, 30); } // x and y are start of branch // depth is how many recursive calls // thickness is weight of stroke for branch // xo and yo are initial offsets for incrementing x and y (plus an additional random amount) void branch(float x, float y, int depth, float thickness, float xo, float yo) { if (depth <= leafDepth) { int numBranches=2; // more numerous branches higher up if (depth>branchDepth) numBranches = floor(random(2,17)); int dir=1; // alternate left/right for (int i=0; i<numBranches; i++) { // end of branch float x2 = x+dir*(xo+random(-30,30)); float y2 = y-yo+random(-40,40); dir = -dir; // draw branch strokeWeight(thickness); // branch or "leaf" color if (depth <= branchDepth) stroke(30,10,5); else stroke(random(60),random(50,140),random(20),230); // line(x,y, x2,y2); x2 = orgLine(x,y, x2,y2, 8, 5); // branches shorten and thin out float thick2 = thickness*pow(0.75,numBranches); float xo2, yo2; if (depth<branchDepth) { xo2 = xo-numBranches*random(1); yo2 = yo-numBranches*random(.5); } else { xo2 = xo-numBranches*random(3); yo2 = yo-numBranches*random(1.5); } // recursive call branch(x2,y2,depth+1,thick2,xo2,yo2); } } } // generates oragnic looking branches // y will end up at y1, but x may be off some, so it's returned float orgLine(float x1, float y1, float x2, float y2, int numSections, int maxTwist) { float dx=(x2-x1)/numSections, dy=(y2-y1)/numSections; float x=x1, y=y1; // each section increments y by dy, and x by dx plus a random "twist" amount for (int i=0; i<numSections; i++) { float twist = random(-maxTwist,maxTwist); float xn=x+dx+twist, yn=y+dy; line(x,y, xn,yn); x = xn; y = yn; } return x; }
[applet]
Non-tree-looking trees
The idea of splitting something in half (or thirds, or whatever) and doing something for each half (or other fraction) is a very common one, both in solving problems (think of trying to find a word in the dictionary) and in generating complex visualizations. A couple of Processing examples render a "binary tree" structure with discs instead of as a tree. Basics | Structure | Recursion draws a big circle, and within that circle draws two smaller circles, each of which draws two still smaller circles, etc. Basics | Structure | Recursion2 then injects some randomness, giving from 2 to 6 sub-circles positioned around inside the circle, at random angular spacing.
The DrunKandinsky sketch of Sean McCullough goes even further, making the discs dynamic. (It also has a convenient "t" keypress to show/hide the underlying tree structure.) This sketch illustrates recursively defined objects, in addition to recursively defined functions. It keeps a Disc object for each disc that's drawn. The children field of a disc remembers which sub-discs were created for that disc. To draw, then, we draw the outermost ("root") disc, and it asks its children to draw themselves, and they ask their children to draw themselves.... The dynamic aspect comes in the draw loop where we periodically change the bend amount (rotation) and scalingFactor (size of the ellipses). Again, the change is made at the root, and is propagated from parent to children. The size and position of each child is calculated relative to the current values for the parent.
Fractals
Fractals are a class of recursively defined geometric shapes, where the structure at a finer resolution is similar to that at a coarser resolution. Our trees are fractals; for some amazing examples of natural-looking fractals (and recursively constructed things more generally), see the book Algorithmic Beauty of Plants, available electronically (but worth seeking out as a book). Other fractals aren't so natural-looking, but have a different type of beauty, e.g., the famous Mandelbrot set. (Images below from Wikimedia Commons.)
 |
 |
We only have time here to scratch the surface of fractals here; I'll show a couple of simple examples that further illustrate recursion and may pique your interest.
Let's start with one side of a "Koch snowflake". The basic idea is to take a segment and recursively divide it into four segments. The first segment is the first third of the original segment, and the last segment is the last third. The middle two segments then jut out triangularly from the original segment. (It's an equilateral triangle, so a little trig lets us calculate the coordinates of the jutted-out point. The following sketch proceeds one level deeper into the recursion each time the mouse is pressed. It keeps a list of the vertices of the segments, and for each recursion inserts three interior points (1/3, 1/2-jutted, and 2/3) between each pair.
float[] x, y; // Coordinates of the points on the curve int depth; // How deeply we've recurse void setup() { size(400,400); background(255); initKoch(); drawCurve(x,y); } void draw() {} // Each time the mouse is pressed, recurse one more level void mousePressed() { background(255); depth++; if (depth==6) initKoch(); // wrap around else expandKoch(); println(depth); drawCurve(x,y); } // Set up the initial curve -- a horizontal line void initKoch() { depth = 0; x = new float[2]; y = new float[2]; x[0] = 0; y[0] = height/2; x[1] = width; y[1] = height/2; } // Update the points by putting a triangular part jutting out // between each pair of points in the current set void expandKoch() { // new points int l2 = 1 + 4*(x.length-1); float[] x2 = new float[l2], y2 = new float[l2]; // index into new points int i2=0; for (int i=0; i<x.length-1; i++) { // consider each adjacent pair of points float dx = x[i+1]-x[i], dy = y[i+1]-y[i]; // first point is the same x2[i2] = x[i]; y2[i2] = y[i]; // second point is 1/3-way between x2[i2+1] = x[i]+dx/3; y2[i2+1] = y[i]+dy/3; // third point is 1/2-way between, sticking out x2[i2+2] = x[i]+dx/2 + sin(radians(60))*dy/3; y2[i2+2] = y[i]+dy/2 - sin(radians(60))*dx/3; // fourth point is 2/3-way between x2[i2+3] = x[i]+dx*2/3; y2[i2+3] = y[i]+dy*2/3; i2 += 4; } // last point is the same x2[l2-1] = x[x.length-1]; y2[l2-1] = y[y.length-1]; x = x2; y = y2; } // draw a shape with vertices for the points void drawCurve(float[] x, float[] y) { beginShape(); for (int i=0; i<x.length; i++) vertex(x[i],y[i]); endShape(); }
[applet]
Now to generate a snowflake, we do this for each side of a triangle. That just requires appropriately rotating and translating the computed curve. (The curve is put at the origin, to allow the rotation and translation, and is a bit smaller, so the snowflake will fit.
void drawSnowflake() { pushMatrix(); translate(width/4,height/4); drawCurve(x,y); popMatrix(); pushMatrix(); translate(width*3/4,height/4); rotate(radians(120)); drawCurve(x,y); popMatrix(); pushMatrix(); translate(width/2, height/4+width/2*sin(radians(60))); rotate(radians(240)); drawCurve(x,y); popMatrix(); }
[applet]
With just a small change to the original Koch curve sketch, we can get a "Heighway dragon". The initial segment occupies the middle half of the window. Each recursion, we treat a segment as the hypotenuse of a right triangle, and replace it with the other two sides. One segment's triangle will go one way, and the next's the other.
// Set up the initial curve -- a horizontal line void initDragon() { depth = 0; x = new float[2]; y = new float[2]; x[0] = width/4; y[0] = height/2; x[1] = width*3/4; y[1] = height/2; } // Update the points by treating each segment as the hypotenuse // and replacing it with the other sides of a right triangle void expandDragon() { // new points int l2 = 1 + 2*(x.length-1); float[] x2 = new float[l2], y2 = new float[l2]; // index into new points int i2=0; // alternate left/right int dir=-1; for (int i=0; i<x.length-1; i++) { // consider each adjacent pair of points float dx = x[i+1]-x[i], dy = y[i+1]-y[i]; // first point is the same x2[i2] = x[i]; y2[i2] = y[i]; // second point is opposite vertex of the right triangle x2[i2+1] = x[i]+dx/2 + dir*sin(radians(90))*dy/2; y2[i2+1] = y[i]+dy/2 - dir*sin(radians(90))*dx/2; i2 += 2; dir = -dir; } // last point is the same x2[l2-1] = x[x.length-1]; y2[l2-1] = y[y.length-1]; x = x2; y = y2; }
[applet]