A large number of complicated patterns can be defined very simply using recursion, whereby a simple shape is drawn over and over again until a complete pattern is built up. Recursion means, simply, repetition and the term can be used to describe any repetitive process.
A 'replacement rule' is repeatedly applied to the initial pattern, and this principle may also determine the size and position of successive versions of the shape relative to the original.
Here is a simple example:
In this case the initial pattern is a diamond. The rule applied here is to draw a smaller diamond centred about each of the corners of the original. As you can see, this rule does not have to be applied many times before a complicated pattern emerges.
The BASIC interpreter on the BBC machine allows you to define recursive procedures. A recursive procedure has a call to itself within its definition. Here is an example showing how a recursive procedure can be used to mimic the action of a FOR... NEXT loop. (Obviously in this case the FOR... NEXT loop would be much neater and more efficient.)
Example
10 PROCLOOP(0)
20 END
30 DEF PROCLOOP(N%)
40 IF N%=11 THEN ENDROC
50 PRINT N%
60 PROCLOOP(N%+1)
70 ENDPROC
Description of program
10 Call PROCLOOP with 0. 20 Stop. 30 PROCLOOP takes one parameter N%. The value of N% determines the number of times we recurse. 40-60 If N% is equal to 11 then return, otherwise print out N% and call PROCLOOP with the value N%+1. 70 This final ENDPROC is vital.
This program will print the numbers from 0 to l0. The recursive procedure PROCLOOP consists of three parts which are:
In general these parts can be found in some form in every recursive procedure. The order in which these sections appear is important; for example, if the procedure calls itself before it has tested for the end condition it will never be able to stop recursing and will run out of room.
Each time a new call of the procedure is made the 'depth' of recursion increases. The depth of recursion is in some cases similar to the number of times a loop is executed. When a program leaves a procedure it returns to the level it was at just before entering it. The deeper a program recurses the more information it has to store about how to get back to the top level.
Local variables can only be altered inside the procedure in which they appear, and have no effect on any variable outside their own procedure. This is generally useful since it is possible to define a procedure without worrying about name clashes.
In recursive procedures it is often vital to declare variables to be local. If this is not done recursive calls of the procedure will alter the variables in calling the procedure, and the effects of this can be obscure.
In BBC BASIC the parameters of a procedure are automatically treated as local variables; for any other variable to be local it must be explicitly declared to be so. This program, which prints out coloured blobs, demonstrates a typical case in which a local variable is required:
Example
l0 MODE 7
20 PROCDO(I)
30 END
40 DEF PROCDO(L%)
50 LOCAL I%
60 IF L%=5 THEN ENDPROC
70 FOR I%=1 TO 7
80 PROCDO(L%+1)
90 VDU (l28+I%),255
100 NEXT
110 ENDPROC
Each time PROCDO is called it should call itself seven times in the loop starting at line 70. If I% is not declared to be local the recursive calls of PROCDO would affect the value of I% in the first procedure. Try removing line 50 to see how this affects the program.
The great power of recursion is that it can provide a very neat solution to certain kinds of problem. This power must be judged against some of its limitations.
The main problems are:
The first problem can arise because each time a procedure is called there is a delay while the parameters are passed to the procedure and local variables are set up. The speed at which this is done depends on how efficiently this mechanism has been implemented.
Luckily the interpreter on the BBC machine is quite fast and the overheads incurred each time a procedure is called are not very large. Since recursive procedures require many procedure calls they will run faster if the cost of each call is kept to a minimum. This can be achieved by not passing unnecessary parameters that do not change, and keeping the number of local variables to a minimum.
Each time a procedure is called some more memory is required to hold the local variables and the return address from which the procedure was called. Recursion allows procedures to call themselves, and at each new level some more memory is needed. It is very easy to define a procedure which can gobble up memory at an alarming rate, for example if a large number of local variables are used and if the procedure recurses many times. To avoid this care must be taken to ensure that the end condition stops the recursion before it runs out of room. Also, because all the parameters are saved every time the procedure is called, the number of parameters used should be limited to avoid passing parameters that do not alter, thus avoiding possible wastage of valuable memory.
The next two programs are examples of patterns that are derived from repeatedly applying a replacement , rule to an initial pattern. Both start from a very simple pattern. Surprisingly, the outline of the final pattern depends more on where the replacements are made than on the original shape.
This program illustrates how a complicated pattern crew easily be defined and rapidly drawn using a recursive procedure. The pattern is formed by drawing a diamond followed by four diamonds, each half the size of the original, centred about its corners, as shown on page 63. On each of these diamonds a further four smaller diamonds are drawn. This continues until the size of the diamonds has become less than the minimum size spec if ied.
RECDIA
10 MODE 1
20 VDU 5
30 M%=400
40 REPEAT
50 VDU 19,RND(3),RND(7);0;
60 GCOL 3,RND(3)
70 PROCDIA(640,512,512)
80 M%=M%/2
90 UNTIL M%<16
100 GOTO 30
110 DEFPROCDIA(X%,Y%,S%)
120 IF S%<M% THEN ENDPROC
130 S%=S%/2
140 PROCDIA(X%+S%,Y%,S%)
150 PROCDIA(X%-S%,Y%,S%)
160 PROCDIA(X%,Y%-S%,S%)
170 PROCDIA(X%,Y%+S%,S%)
180 VDU 29,X%;Y%;
190 MOVE 0,S%
200 DRAW S%,0:DRAW 0,-S%:DRAW -S%,0:DR
AW 0,S%
210 ENDPROC
Description of program
10 4-colour mode 20 Remove text cursor 30 M% gives the minimum size a diamond can be. 40 Call the recursive procedure PROCDIA (X%,Y%,S%) each time round this loop. 50 Redefine one of the three logical colours to appear as any of the possible non-flashing colours. 60 Select a random colour and graphics action EOR. 70 Call PROCDIA in the centre of the screen with an initial size of 512. 80 Halve the maximum line length; this will cause PROCDIA to recurse one level deeper next time it is called. 90 If M% was less than this the recursion would take too long and the lines very small. 100 Start all over again. 110 Each time PROCDIA(X%,Y%,S%) diamond of size S% is drawn the point (X%,Y%), provided drawn would be is called a centred about that S% is bigger than M%; otherwise, the procedure does nothing, 120 Do nothing if the size is less than M%. 130 Halve the size. 140-170 Call PROCDIA to draw half-sized diamonds at each corner. 180 Put the origin at the point (X%,Y%). 190-200 Draw a diamond of size S%.
This pattern is similar to the recursive diamonds pattern. Here the recursive step is to replace one square by the original square plus four smaller squares lying on its sides. Because the squares are drawn with the graphics action Exclusive-OR, in a random colour, this step can cause parts of the original square to be erased. The procedure is called repeatedly recursing to a deeper level on each call. This method produces a wide range of dynamic patterns.
Pattern construction
RECSQ
0 REM Recursive Squares
20 MODE1
30 VDU5
40 V%=300
50 REPEAT
60 GCOL3,RND(3)
70 VDU19,RND(3),RND(7);0;
80 PROCC(500,400,256)
90 V%=V%/2
100 UNTILV%<8
110 GOTO40
120 END
130 DEFPROCC(X%,Y%,S%)
140 IF S%<V% THEN ENDPROC
150 PROCC(X%+S%/4,Y%+S%,S%/2)
160 PROCC(X%+S%,Y%+S%/4,S%/2)
170 PROCC(X%-S%/2,Y%+S%/4,S%/2)
180 PROCC(X%+S%/4,Y%-S%/2,S%/2)
190 VDU29,X%;Y%;
200 MOVE0,0
210 DRAW0,S%:DRAWS%,S%:DRAWS%,0:DRAW0,
0
220 ENDPROC
Description of program
40 V% controls how many times PROCC will recurse. 50 Each time around this loop we call PROCC. 60 Select graphics action EOR with a random logical colour. 70 Display any of the 6 colours. 80 Call PROCC in the centre of the screen with initial size 256. 90 Reduce V% causing PROCC to recurse one level deeper next time it is called. 100 Limit V%. Since each pixel is 4x4 this seems a reasonable limit. If V% were much less than this then the time required for PROC would be excessive. 110 Start again. 120 (We never get here.) 130 Draw a square at (X%,Y%) of size S%. 140 Do nothing if S% is less than V%. 150-180 Call PROCC on each side of the square. 190 Move the origin to (X%,Y%). 200 Draw the square.
In the previous examples the number of recursive calls and the way in which the parameters are altered at each call remain the same at every level. This introduces a very strict regularity to the pattern produced. It is possible to have a parameter that controls the nature of the recursive calls. This leads to exciting possibilities in which different actions can be taken at different levels of recursion,
This program draws a pattern built up from circles of decreasing size growing outwards from the central circle. The program uses recursion and has a very simple way of ensuring that circles are not drawn on top of each other.
This is done by having a parameter in the circle-drawing procedure that indicates where the current circle is joined to its parent. By examining this parameter it is possible to avoid any recursive calls that would cause circles to be overwritten. A result of this is that the final pattern is square and fills the screen in a surprisingly intelligent way.
Effect of the parameter P%
CIRCLES
0 REM Circles
20 MODE1
30 VDU5
40 VDU19,0,4;0;
50 PROCCIRCLES(640,512,240,0,0)
60 REPEATUNTIL0
70 DEF PROCCIRCLES(OX%,OY%,R%,L%,P%)
80 IFL%=5 THEN ENDPROC
90 VDU29,OX%;OY%;
100 GCOL3,L%MOD3+1
110 FORA=0TO2*PI-PI/R% STEPPI*4/R%
120 MOVE0,0:DRAWR%*COSA,R%*SINA
130 NEXT
140 IFP%<>3 PROCCIRCLES(OX%-R%,OY%-R%,
R%/2,L%+1,1)
150 IFP%<>4 PROCCIRCLES(OX%+R%,OY%-R%,
R%/2,L%+1,2)
160 IFP%<>1 PROCCIRCLES(OX%+R%,OY%+R%,
R%/2,L%+1,3)
170 IFP%<>2 PROCCIRCLES(OX%-R%,OY%+R%,
R%/2,L%+1,4)
180 ENDPROC
Description of program
40 Make the background dark blue. 50 Call PROCCIRCLES. The centre of the first circle will be at (640,512) and it will have a radius of 240. The next parameter determines the level of recursion and the colour. The last value determines where circles are drawn around the current circle. 60 This stops the prompt from BASIC appearing once the pattern has been drawn. 70 PROCCIRCLES takes the following parameters: OX%,OY% are the coordinates of the centre of the circle. R% The radius of the circle. L% The depth of recursion, also used select a new colour at each level. P% The position at which the current is joined to its parent circle. 80 Stop after 5 recursions. 90 Move the origin. 100 Select a colour specified by L% with action EOR. 110-130 Draw the radial circle lines. 140-170 Call PROCCIRCLES at a maximum of four positions around the edge of the original. Omit the position that connects the current circle to its parent. 170 Leave the procedure.
If a procedure is to call itself a large number of times, it would be very inconvenient to have to write out each call explicitly. By placing the call in a loop the desired effect is produced. However, there are some pitfalls to avoid if this is done.
The value of the control variable of the loop must not after while the procedure in the loop is being executed. If the procedure being called is the same as the calling procedure it is bound to have a loop contr'ol Variable with the same name. To ensure the variable retains its value across the recursive call the loop variable must be declared to be a local variable. The following program uses this method.
The Koch flake is sometimes called the snowflake curve, because its curious shape resembles a snowflake. Here it is constructed by repeatedly drawing smaller stars on the arms of stars that have already been drawn. The resulting pattern has the outline of two koch flakes embedded in it. These may show up more clearly when the entire pattern has been finished and the palette changes begin. At this stage there is a two-second delay between each colour change, unless you hold down any key, in which case this delay is removed and you can rapidly step through the colours until an interesting colour scheme is found.
KOCH
0 REM Koch Flake
20 MODE1
30 VDU5
40 VDU19,1,4;0;:VDU19,2,6;0;
50 CS=COS(PI/6)
60 PROCSTAR(640,512,500,2)
70 REPEAT
80 VDU19,RND(3),RND(8)-1;0;
90 A=INKEY(200)
100 UNTIL FALSE
110 END
120 DEFPROCSTAR(X%,Y%,S%,C%)
130 LOCAL I
140 IF S%<12 THEN ENDPROC
150 IF C%=0 THEN GCOL0,2 ELSE GCOL0,C%
160 VDU29,X%;Y%;
170 XL%=S%*CS:YL%=S%/2
180 MOVE 0,S%:MOVE XL%,-YL%:PLOT85,-XL
%,-YL%
190 MOVE 0,-S%:MOVE XL%,YL%:PLOT85,-XL
%,YL%
200 FORI=0 TO 2*PI-PI/3 STEP PI/3
210 PROCSTAR(X%+S%*SIN(I)*0.68,Y%+S%*C
OS(I)*0.68,S%/3,(C%+1)AND3)
220 NEXT
230 ENDPROC
Description of program
40 Make cold colours appear while the flake is being drawn. 50 This value is going to be used often so to speed things up save it as CS. 60 Call PROCSTAR to draw the pattern centered about (640,512) with initial size 500 and logical colour 2. 70 Change the colours on the screen at random. 80 Do a random palette change. 90 Wait 2 seconds if no key is pressed. 100 Carry on until someone presses ESCAPE. 110 We never get here but this helps to show where the procedure declarations start. PROCSTAR(X%,Y%,S%,C%) draws a star in logical colour C% centred about the point (X%,Y%) of size S%, it then calls itself on each of the arms of the star it has just drawn. 130 This will hold an angle that determines which arm the next call of PROCSTAR is for. 140 Do nothing if the size is less than 12. 150 Choose the colour. 160 Put the origin at (X%,Y%). 170 Draw the star using XL% and YL%. 180-190 Draw two overlapping triangles to form a star. 200 This loop calls PROCSTAR for each arm of the star just drawn. 210 Call PROCSTAR to draw a star centred in the middle of the arm pointing at an angle I, with S% one third its previous value and a new colour. 230 Leave the procedure.
The next two programs produce patterns obtained by repeatedly applying a replacement rule to every straight line in the pattern. In both cases the initial pattern here is simply one straight line.
The two programs produce very different results despite the fact that there is only a slight difference in the two replacement rules. Many other interesting patterns could be produced by modifying the way in which the parameters are altered in the recursive line-drawing procedure.
A C-curve is produced by recursively replacing a straight line between two points by two shorter lines at right-angles to each other that form an elbow connecting the points. The curve is plotted when the length of the lines has become less than a given value. The first few steps in the construction are shown on the next page:
The pattern that results depends on the length 6f the initial line and the depth of recursion. As given, the program is quite slow since it has to calculate a sine and a cosine for each line drawn. One simple way to speed this up would be to save all the possible values of sin and cos that will be required in an array.
0 REM C-Curve
20 MODE1
30 VDU5
40 MIN%=15
50 GCOL0,2
60 MOVE300,200
70 PROCC(700,0)
80 REPEAT UNTIL FALSE
90 DEFPROCC(L%,ANGLE)
100 IF L%<MIN% THEN PLOT 1,L%*COS(ANGL
E),L%*SIN(ANGLE):ENDPROC
110 L%=L%/SQR(2)
120 PROCC(L%,ANGLE+PI/4)
130 PROCC(L%,ANGLE-PI/4)
140 ENDPROC
Description of program
40 MIN% gives the maximum length of any line that will be plotted. This is a way of controlling the depth of recursion. If MIN% is large the program will not recurse very far. 60 This is the starting point from which the curve grows. 90 PROCC(L%,ANGLE) will draw a line of length L% at an angle ANGLE starting at the current position if L% is less than MIN%. 100 If the length is short enough, draw the line and then stop. 110 Reduce the length. 120-130 Call PROCC twice for each of the new shorter lines.
The dragon curve is so called because of its contorted shape which resembles a Chinese dragon. It is produced by a very similar technique to that used to draw the C-curve, Here the recursive step is to replace a straight line between two points by two shorter lines, forming a hat to one side of the original line. In the C-curve the hat formed is always put on the same side of the line being replaced, whereas to produce a dragon curve the hat is placed alternately on different sides of the line. The first few stages of the construction are shown on the next page.
In this program the drawing process has been speeded up by saving a table of the trig functions so that these do not have to be calculated for each line drawn. The curve is drawn using the triangle fill relative command, PLOT 81, which does not fill the curve exactly but is a reasonable approximation when the lines composing the curve are small.
DRAGON
0 REM Dragon Curve
20 MODE1
30 VDU5
40 DIM S(7),C(7)
50 A=0
60 FORI%=0TO7
70 S(I%)=SIN(A):C(I%)=COS(A)
80 A=A+PI/4
90 NEXT
100 M%=12
110 GCOL0,RND(3)
120 MOVE200,700:MOVE200,700
130 PROCC(1024,0,-1)
140 REPEATUNTIL FALSE
150 DEFPROCC(L%,I%,T%)
160 IF L%<M% THEN PLOT 81,L%*C(I%),L%*
S(I%):ENDPROC
170 L%=L%*1000/1414
180 PROCC(L%,(I%+T%)AND7,1)
190 PROCC(L%,(I%-T%)AND7,-1)
200 ENDPROC
Description of program
40 These will hold SIN(A) and COS(A) for all the values A can take in the construction. 60-90 Store sine and cosine values in arrays S and C. This makes the drawing of the curve much faster because all the trig functions can rapidly be found from the values stored in these arrays. 100 M% gives the maximum length of any line that will be drawn. 120 Select a colour at random. Set the point from which the curve will start. Two moves are required since the curve is to be filled in using PLOT 81. 130 Call PROCC. This will grow out to join a point 1024 units to the right. The first hat is to be placed below the original line. 140 Do nothing until ESCAPE is pressed (this stops the ">" appearing). 150 PROCC takes these parameters: L% is the length of the line I% is a value used to index the tables of trig functions, the value of I% corresponds to the angle of the line. T% is a value that determines on which side of the line the new lines, forming a hat, are to be placed. 160 If the length is short enough draw a line then stop. 170 Reduce the length, prior to the recursive calls of PROCDRAG. This has the same effect as L%=L%/SQR(2] or L%=L%/l.4l4, but is slightly faster than either of these more obvious methods. 180 Call PROCC. L% is the new length. The new trig table index depends on the value of T%; we either add or subtract PI/4 to the angle. AND 7 ensures that the index wraps around for angles 0 and 2*PI. Draw the next hat 'above' 190 Call PROCC for the other line in the hat. This line is at right angles to the line produced in the call above, and the first hat growing from it is on the opposite side. 200 Leave the procedure.
Recursive procedures can be used quite effectively to produce irregular patterns; here is one that draws a tree. Each branch of the tree can be thought' of as a separate tree growing out at an angle from the previous branch. The procedure takes parameters that determine the length of the branch, its angle and the number of sub-trees that grow from it. The parameter DEPTH% controls the depth of recursion.
TREE
0 REM Tree
20 MODE1
30 MOVE500,200
40 VDU19,2,2;0;
50 PROCTREE(PI/2,200,5,4)
60 END
70 DEFPROCTREE(ANGLE,HEIGHT%,BRANCHES%,DEPTH%)
80 LOCAL I%,X%,Y%
90 IF DEPTH%=0 THEN ENDPROC
100 X%=HEIGHT%*COS(ANGLE)
110 Y%=HEIGHT%*SIN(ANGLE)
120 FOR I%=1TO BRANCHES%
130 IF DEPTH%=1 THEN GCOL0,2 ELSE GCOL0,1
140 PLOT1,X%,Y%
150 PROCTREE(RAD(RND(180)),HEIGHT%/2,BRANCHES%,
DEPTH%-1)
160 PLOT0,-X%,-Y%
170 NEXT
180 ENDPROC
Description of program
30 Define the point from which the tree will grow. 40 Set logical colour 2 to appear as green, the colour of the leaves. 50 Call PROCTREE. The effect of these parameter values is as follows: PI/2 makes the trunk vertical The trunk will be of length 200. There will be 5 branches growing from each fork point. Recurse 4 times. 60 Stop. 70 PROCTREE takes these parameters: ANGLE (in radians measured anti-clockwis from 'east') determines the angle at which a branch will be drawn. HEIGHT% gives the length of the branch. BRANCHES% is the number of subtrees that grow from each fork point. DEPTH% is a measure of the depth of recursion. 80 Declare 1%, X%, Y% to be local variables, otherwise their values would be altered in recursive calls of PROCTREE at line 150. 90 Have we recursed enough? If so then stop. 100-110 The point (X%,Y%) is the tip of the current branch. 120 PROCTREE is called once each time round this loop. 130 Select the colour. 140 Draw the branch. 150 Draw a subtree from the fork point, with new parameters: RAD(RND(l80)) is a random angle between 0 and 180 degrees (RAD converts this into radians). HEIGHT%/?. halves the length of the branches. BRANCHES% makes the same number of branches grow from each fork in the subtree. DEPTH%-1 - we have recursed, so reduce DEPTH%. 160 Move back to the fork point. 180 Leave the procedure,
This tree program is very readily-modified to produce a vast number of different effects. The shape of the tree drawn depends on the values used for the initial parameters. Try altering these to get an idea how each one affects the final result. The way the parameters are altered in the recursive call of PROCTREE at line 150 is very important. See how the structure of the tree can be changed by altering this line.
More complicated tree procedures could easily produce very life-like trees. One way to do this would be to have separate procedures to draw different parts of the tree. For example the branch-drawing procedure could call PROCLEAF to draw solid leaves along the shorter branches.
Another possible improvement would be to draw solid branches using the PLOT 85 command, This could be done by introducing a parameter, WIDTH, that would determine the thickness of each branch. A 3-dimensional effect could be produced by shading these solid branches with the random dot technique.