When we are going to draw a recursive image, it's extremely important to define it orally. For each unique definition - a unique algorithm can be written. How would you define the image in the first frame? It's known as Sierpinski Triangle.
- Well, it's a triangle, inside each angle there is a similar, but half in size triangle, inside each angle of which there is a smaller half-sized triangle, and so on.
- Your description is perfect, but though the process should go to the infinity, in reality, computer and time resources are limited and we should decide in advance how many steps we are going to do in this process. Or, as the process should be a recursive one, that means, we should decide what will be the highest level of recursion.
Now you remember that we have two ways to draw a triangle,
using RT's (then we call it a "right" triangle) or using LT's (in which
case we have a "left" triangle). When we come to recursive drawing we
have to vote for one of two: either ALL triangles are "right" or ALL triangles are "left".
- Let's all of them be "right" ones.
- OK! Also of importance is the direction and the starting point of our drawing. Many times a difficult algorithm becomes easy for implementation if we select cleverly our point of start and heading.
- I think we might begin from the low left angle of the largest triangle.
- Very good! Let's denote the side length of the largest triangle by :size and the highest recursion level by :level.
Then our steps should be the following:
1. Draw the shape of a smaller size (:size/2) and the lower level (:level-1).
2. Go to the next angle and make a right turn of 120 degrees to take the "initial position". Now we are ready to draw the next shape of a smaller size and lower level. From this point, where we are now, our relation to the shape is EXACTLY as the relation from the previous point to the previous shape. It's very important to view this resemblance.
3. And, we should repeat steps 1-2 three times, for there are three shapes of the lower level inside our triangle.
That's all! It's good to know what's happening inside the computer brain while executing our commands, but this understanding is not absolutely necessary. This is my interpretation of our above algorithm in MSWLogo:
to main ; I advice to name the superprocedure of every program of you
; main. This way one can recognize the superprocedure at once,
; even when the procedures are scrambled.
cs ht ; plain cosmetics
rt 30
print [input side size and recursion level]
shape rw rw
end
to shape :size :level
if :level<1 [stop] ; every recursive program needs a stop rule
repeat 3[shape :size/2 :level-1 fd :size rt 120]
end
Try and enjoy!
Now tell me please, what should be changed, if we are going to draw the same shape, but made of squares?
- Let me see... First, there will be four smaller shapes inside each square. Then, we should change the turn angle from 120 to 90.
And, this same way we can draw shapes made of pentagons and hexagons!
- Very good! Let's try...
Well, somehow you are not very fond of your work, why?
- It's hard to see something in this crossed lines!
- So, in this case the smaller shape should be smaller, shouldn't it? What prevents you from doing it three times smaller, 2.2 times smaller?
And I'm sure, it's not a problem for you now to make drawings, displayed by the second "window" and try to invent something on your own. This will be your homework, OK?
As I can see you don't need any break and, we can have our second lesson just now. Any objections? Very good!
Well, let's look at the drawing in the right window.
In this case on each side of a square there is a square which is two times smaller.
What is the crucial difference from our point of view
between this shape and those, we have just investigated?
- I see, that starting point for the large shape and the smaller shape don't coincide. Moreover, if we begin from the left low angle and make a step of :size/4 and reach the smaller shape, it would be a "left" shape, but we decided our shapes all be "right" ones.
- Very good observation! So, why not, beginning from the low left angle make a step of :size/4, then of :size/2 and make a turn of 180 degrees? Where we are now?
- We are just at the starting point for drawing the smaller shape!
- Surely. Then, after finishing with the smaller shape, we should reach the second angle of the largest square. For that we should again make a turn of 180 degrees and make a step of :size/4. Do you agree? And, to make all this with the next side we should make a turn of 90 degrees. So, our central procedure may go as follows:
to draw :size :level
if :level<1[stop]
repeat 4[fd .75*:size rt 180 draw :size/2 :level-1
rt 180 fd .25*:size rt 90]
end
But, you see, the expression in the brackets is rather complicated and it will be more clear,
if we define a new procedure
to shape :size fd .75*:size rt 180 draw :size/2 :level-1 rt 180 fd .25*:size end
And, adding the procedure, which fills our squares with bright colors, we are finishing our program:
to main ; Colored Squares cs ht pu setxy -32 -32 pd setpc 6 draw 64 5 end to draw :size :level if :level<1[stop] repeat 4[shape :size rt 90] pu fill_it pd end to shape :size fd .75*:size rt 180 draw :size/2 :level-1 rt 180 fd .25*:size end to fill_it rt 45 fd :size/2 setfc :level fill bk :size/2 lt 45 end
Well, that's all for now. You may consider the drawings in the two middle windows as your homework. If you face some serious problems, you may look here for a possible solution.
Best of luck!
And when you are done with your homework, you'll get your third recursion lesson.
Back to the first page of the story
Lesson three