Well, we know recursion and we know graphics. So, it makes sense to put them together and we'll just have some fun in interesting applications. These recursive graphics are all over the place in art and literature in popular culture. You're familiar with the work of MC Escher which involves recursion. That's a famous cacao box. There's, well, I don't think that's Da Vinci's work, or is that? Even in New York Times, one time did a recursive headline of a newspaper that has a picture of itself on the cover. So, let's look at how to make images like this. We'll look at some similar, more simpler and more practical images, but let's see what we can do. So, one of the simplest programs that's actually very useful is called an H-tree. So, this is recursive graphics. What we're going to do is base our recursion on the image of an H center. To get an H-tree of order n, we're going to draw four H-trees of order n minus 1, half the size centered at the tips of the H. So, our first one is just an H. Our second one, we have a smaller H centered at each one of the tips. Third, again, four Hs half the size, centered at each of the tips. So, that's an H-tree. So, these are some bigger ones, four, five, six. So, this actually has important practical application. It's called what's called a space-filling curve. You can imagine if you had a source that you want to connect electrically to lots of sites like on an integrated circuit chip or wiring a city for cable TV, you want to use a structure like this that gives you a connection to everywhere in an organized fashion. Actually, people have studied many different types of space-filling curves. This is just a first application. So, what's the code to implement an H-tree look like? Well, it almost writes itself and you certainly could write this code. The trickiest thing is to just figure out exactly how to draw the H. So, we're supposed to in the recursive call make the new ones half the size. So, we have to keep the track of the size as one of the parameters in the recursive function, and then xy coordinates of where's the center of it. So, we're going to compute the four corners of the H, x0, y0, x1, y1, just by taking the xy coordinates and subtracting half the size. So, then we draw a line from x0 to x1, and y. That's a bridge to the H. Then from y0 to y1 and x0, that's one side. From y0 to y1 and x1, that's the other side. So, that draws the H centered on x and y. Then we're going to have four recursive calls at each of the four corners, x0, y0, x0, y1, x1, y0, and x1, y1. Those are all of size over two. Don't forget, we need a termination condition if n equals zero return. So, we're going to keep an integer argument that gives the size of the H-tree. Another thing we could do is just use the variable size, and when the things get so small, we can make that our termination condition as well. Then just take the H from the command line, and draw the thing at the center, and that gives our H-tree. Again, we not only have recursion in graphics, we also have sound, so we might as well play a note and get a tune. [MUSIC] So, that's recursive H-tree implementation. Okay, here's a related thing that is useful as a model in all kinds of scientific situations. So, this is a process that models many different phenomenon. The price of stocks. So, you're familiar with stock curves, and then there's the price of a couple of stocks. That's an actual stock on the left, and the one on the right is a model with two different parameters, that people think should represent some model of the actual stock. There's lots of other things. So, this is a model that's supposed to look like a mountain. That's the actual shape of a mountain. This idea of fractal Brownian motion is actually quite useful as producing simple models for all these different sorts of phenomenon. It's widely used in lots of scientific applications. Turns out to be a recursive program, not too different from the ones we've been writing. Let's look at the simulation of it. It's called the midpoint displacement method. So, what we're gonna do is we have a line segment that goes from two given points. If it's just short enough, we're just going to draw it and return. That's our base case for the recursion. Otherwise, we divide it in half and figure out the point at the middle. It's just x0 plus x1 over 2, y0 plus y1 over 2. Then we're just going to perturb that a little bit. So, we're going to compute a number Delta. It's going to be random, but we're going to use the Gaussian distribution. We talked about Gaussian distribution and Sinner standard random module. So, we'll just add that value Delta to the middle point, and could be plus or minus actually. Then just recurse and draw two line segments, and then call that recursively. That's the process. Here's just the example of running this process a few times. So, let's look at what the code looks like. Again, it's a very simple recursive program, very similar to the other ones that we've done. If our points are close enough together, we just draw the line. Otherwise, we compute the middle. We compute this value Delta. Now, there's a parameter in here, that I'm not going to talk about in detail, that controls the Gaussian distribution. So, it's called the Hurst exponent, and that's described in the book. On the book side of it that actually does. But other than that complication, it's a recursive program with the same structure the other ones that we've been doing. Divide in the middle and recurse them two halves. So, if you use this with the parameter one that looks a little bit like the mountains and if you use it with a small parameter like one-eighth, it looks a little bit like the stock price. It's very surprising that such a simple process can model so many natural things. There's a two-dimensional version called plasma clouds, and it's a similar idea just in two dimensions. We'll describe it in terms of pixels, you could do it in terms of rectangles, just like we did the lines. But it's a little simpler to think about in terms of pixels. So, that's what we're gonna do in this lecture slide. So, if you've got a rectangle and your pixels at the four corners and they have colors. So, again if it's small, just return. That's the base case. But what you want to do is, for each side, you want to color the midpoints, the average of the endpoint colors. So, that's between 0 and 20, you put 10 there. This is with grayscale. You can do it with colors as well. Twenty to a 100, you put 60 there, 60 to a 100, you put 80, zero to 60, you put 30. So, you could do that for each RGB value if its in color. Okay. Then the last thing you do is, again, choose a little Delta from a Gaussian distribution so that it's not completely rigid. It's got a little bit of randomness in it. What you're going to do is the center pixel of the rectangle, you're going to average the four colors but add Delta. So, in this case, if you actually averaged the four colors, it should be 45, but instead it's going to be 49. Now, you've got four rectangles. Again, Booksite code actually draws rectangles there rather than pixels. Now, you've got four quadrants, and you just recurse on the four quadrants. I'm not going to show the code for that. It's very similar to the combination of the H-tree code and the 1D Brownian model code. What's amazing is the results that it gives. So, again recurse on the four quadrants and then you get lots more colored dots until all the pixels are colored. So, that's the result of running that computation. Looks very much like a cloud. It's a model of something that we experienced in the real world. You can argue about whether the real world operates in exactly the same way as the model, or the model reflects reality in some way. This has very important practical uses. For example, here's a scene created giving different parameters and different colors. Actually, many of the scenes that you see nowadays in movies and video games are created in this way. It's an important application of a simple recursive process.
