|★ APPLICATIONS ★ CREATION GRAPHIQUE ★ MIKE COOK'S DRAGON|COMPUTING WITH THE AMSTRAD) ★|
|Mike Cook's Dragon (Computing with the Amstrad)||Applications Creation Graphique|
IAN SHARPE illustrates recursion and fractals in dragon curves
RECURSION and fractals are two fairly common topics these days, and Program 1 is a short routine that illustrates them both. It draws a dragon's curve which is the name given to a particular class of curve and produces some complex graphics for a minimum of typing.
It was originally written in BBC Basic by my colleague Mike Cook for Electron User. The Electron version used procedures and local variables neither of which are implemented on the Amstrad.
A procedure is very like a subroutine but it is referred to by name, such as PROCprint, rather than by a line number. When you want to call it you simply use the name like another Basic command.
Local variables differ from globals in that although both are accessible from any part of the program, whatever you do to a local the original value is re-
It follows that if a procedure uses a local variable, say x, then if the procedure calls itself - that's recursion - there are two variables called x in operation.
However as they are both local, whatever happens to x at this second level of recursion will leave the variable x at the first level unaffected when it returns. So the two x variables are totally independent even though they have the same name.
Recursive programs really need local variables for this reason. Program II is an example of this in BBC Basic - a routine that calculates factorials. Trace it through and you will realise that this would be impossible in Locomotive Basic.
Replacing the procedures with subroutines on the Amstrad is easy enough, but local variables are more of a problem.
In fact there is no way to get a true local variable, but we can simulate one using an array.
We need to know in advance how many levels of recursion the program will use and dimension an array with this number of elements. In the main program I have called it stack.
We then get the subroutine at recursion depth n to use the nth element of the array as the "local" variable. In this way the subroutine will not intefere with a variable that does not belong to it.
The depth of recursion is held in sp (short for stack pointer) and is limited by the number of times Basic will let you nest subroutines. In this program it works out at 75. If you exceed this limit the computer will stop with a Memory full error. The variable sp is incremented by one every time the subroutine is called and when it returns sp is decremented.
The curve drawn by the program is one of a class known as fractals, a feature of which is that the more closely you examine a section, the more you see similar patterns repeating themselves on a smaller scale. This is where recursion comes in and the greater the depth it goes to the more detailed is the curve.
The curve is drawn by the routine between lines 150 and 210 and it uses two parameters - sz, which is global, and stack(sp) which is local. The first sets the length of line and the second tells the program whether to draw a section of curve or not.
To prevent your Amstrad carrying on for ever (or rather until an error occurs), each time the subroutine calls itself, the local variable is reduced by one. So it will eventually reach zero, a line will be drawn and the subroutine will then return.
If you want to see what's happening, try printing the value of sp at the start of the subroutine. Use a LOCATE command so that it is always printed in the same position and include a short delay loop to allow you 'to read it.
Fractals mirror the way some natural events behave and this has been observed in phenomena as diverse as the flood levels of the Nile and magnetic activity on the sun. Fractals are interesting, yet the recursion technique makes them easy to program.
Have fun experimenting. If you want to take the subject further, consult The Fractal Geometry of Nature by B.B. Mandelbrot (W.H. Freeman, 1982).