Bottom     Previous     Contents

5 Recursion

Recursive patterns

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.

Recursive procedures

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:

  1. A test for an end condition that will terminate the recursion
  2. An action that the procedure printing out N%
  3. A recursive call that alters the parameters in some way

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

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.

Advantages and limitations of recursion

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:

  1. Recursion can be slow
  2. Recursion requires a lot of memory

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.

Replacement patterns

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.

Recursive diamonds

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%.

Recursive squares

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.

Intelligent parameters

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,

Circles

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.

Recursive calls within a loop

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.

Koch flake

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.

Line replacement patterns

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.

C-Curve

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.

C-CURVE

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.

Dragon Curve

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.

Tree

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,

Ideas that have grown from PROCTREE

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.


Next     Top