CS 4: Lecture 20 Wednesday, April 5, 2006 FRACTALS AND RECURSION ====================== _Fractals_ are shapes that are _self_similar_, meaning that they appear similar or identical at all scales of magnification. A simple example is called the _Sierpinski_triangle_. Here's the idea. Start with an equilateral triangle, filled in with black. (Technically, you should think of the triangle as an infinite set of points in the plane, namely all the points inside the triangle or on its boundary.) Then, shrink the triangle to half its former width and height, make three copies of it, and arrange them in a triangle. Then repeat. /\ /\ /\ /88\ /88\ /88\ /8888\ /8888\ /\ 7\ /888888\ ===> /888888\ ===> /88\/88\ /88888888\ /\ 7\ /\ 7\ /8888888888\ /88\ /88\ /88\ /88\ /888888888888\ /8888\ /8888\ /\ 7\ /\ 7\ /88888888888888\ /888888\/888888\ /88\/88\/88\/88\ But that's not a fractal yet. It becomes a fractal after you iterate an infinite number of times. The Sierpinski triangle has some strange properties. First, although it looks solid enough, its area is zero. You see, every time we iterate the process, we reduce the triangle's area by a factor of 0.75. After an infinite number of iterations, there's no area left. Second, it's not exactly a two-dimensional object, because its area is zero. But it's more than one-dimensional, because the total length of all its edges is infinite. So what is its dimensionality? The Sierpinski triangle has dimension log 3 ~ 1.585. (The wiggly "=" means "approximately equals.") 2 ~ (That's the base-2 logarithm of 3, aka log 3 / log 2.) Where did this crazy dimension come from? Well, suppose you have a piece of paper with a one-dimensional curve on it, like a line. If you photocopy the paper at 2x magnification, the line gets twice as long. But if the paper also has a square on it, the area of the square gets four times bigger, because its height and width are each multiplied by 2. Since a square is two-dimensional, its area increases by a factor of 2^2 = 4. If you could photocopy a cube, its volume would increase by a factor of 2^3 = 8. What if the paper has a Sierpinski triangle on it? When you photocopy a Sierpinski triangle at 2x magnification, you get 3 copies of the original Sierpinski triangle. So its "measure" (which is not just length, but not quite area) increases by a factor of 3. Sure enough, because the triangle is (log_2 3)-dimensional, we can calculate that its measure increases by a factor of (log_2 3) 2 = 3. How would you write code to draw a Sierpinski triangle? Well, the bad news is you can never draw one exactly, because they're "infinitely complex." The good news is that if you iterate the process above a finite number of times--say, 10 or 12--your eye won't be able to tell you didn't do infinity iterations. So we'll use recursion to visit smaller and smaller triangles. The base case happens when the recursion goes deep enough--so there are 10 or 12 copies of the recursive method on the stack. For the base case, we'll just draw a (normal) triangle. The parameters for the following code include the x-coordinates of the left and right vertices of the triangle's bottom edge; the y-coordinates of the bottom edge and top vertex; and a number "n" that says how many more iterations need to be done before the recursion bottoms out. public static void sierpinski(int left, int right, int down, int up, int n) { if (n == 0) { /* Base case: draw a triangle. */ int[] vertices = {left, down, right, down, (left + right) / 2, up}; canvas.fillPolygon(vertices, Color.red); } else { /* Make 3 smaller triangles. */ int leftRight = (left + right) / 2; int leftish = (3 * left + right) / 4; int rightish = (left + 3 * right) / 4; int downUp = (down + up) / 2; sierpinski(leftish, rightish, downUp, up, n - 1); sierpinski(left, leftRight, down, downUp, n - 1); sierpinski(leftRight, right, down, downUp, n - 1); } } Observe that this code calls itself three times: once for the top triangle, once for the lower left triangle, and once for the lower right triangle. The Koch Curve -------------- A different way to approach fractals starts with a line segment, which is one-dimensional, rather than a triangle, which is two-dimensional. But we'll still end up with an object whose dimension lies between one and two. Imagine a line segment in the plane, connecting a start point p to an end point q. Then, suppose we replace the line segment with four line segments all of the same length, as follows. (All the angles are 60 or 120 degrees.) p____________________________q v | /\ /\ | / \ ___/ \___ v / \ ---> \ / u / \ w ^ > < ^ p_________/ \_________q ___/ \___/ \___/ \___ Each line segment is _directed_, so we know which side of the line segment to add the bump on. The directed line segment (p, q) is replaced by the four directed line segments (p, u), (u, v), (v, w), and (w, q), all having the same length. (The deleted segment (u, w) also has the same length, and uvw is an equilateral triangle.) Then you replace each directed line segment with four smaller directed line segments. After you iterate this procedure an infinite number of times, you have a _Koch_curve_. The Koch curve is one of the earliest fractals in the mathematical literature, dating to a 1904 paper by Helge von Koch. Even more famous is the _Koch_snowflake_, which is three Koch curves glued together in a ring, with the bumps sticking out. You get it by starting with an equilateral triangle, instead of just one line segment. You can also generate a _Koch_antisnowflake_ this way, which is three Koch curves glued together in a ring, with the bumps sticking in. The Koch curve is as weird as the Sierpinski triangle. First, it has infinite length, because every iteration increases the length by a factor of 4/3. After an infinite number of iterations, the length is infinite. Benoit Mandelbrot wrote a paper entitled "How Long Is the Coast of Britain?" in which he pointed out that coastlines are like fractal curves--the closer you look, the more sinuous they appear. The more you magnify, the more coastal length you find hiding in grains of sand, until you're down to the size of molecules and there is no longer a clearly defined line at all. So it really isn't possible to measure the length of a coast in a meaningful way. The second strange fact is that the Koch curve has dimension log_3 4 ~ 1.26, because if you photocopy it at 3x magnification, you get four copies of the original curve. The third strange fact is that the Koch curve is continuous everywhere, but differentiable nowhere. In other words, there is no point on the Koch curve where you can draw a tangent line, or say what the slope is. In 1872, Karl Weierstrass made mathematical history by demonstrating the first continuous function that is nowhere differentiable. This and related discoveries by Weierstrass were a major driving force in the development of real analysis. Unfortunately, Weierstrass' function is not intuitive--it's an infinite series of sine functions. Koch invented his snowflake to create an intuitive, geometric example. It may look like just a fun toy, but Koch's snowflake holds in it the nub of modern analysis. The Levy C Curve ---------------- In lab, you'll write recursive code to draw a C-shaped curve invented by Paul Levy. It's like the Koch curve, except that the iteration rule is even simpler. You just replace each segment with two segments meeting at a right angle. All the angles are 90 or 180 degrees. /\ /\ ________ / \/ \ /\ | | / \ ====> / \ ====> | | ====> / \ / \ | | \ / __________ / \ | | \ /