Go to the Next or Previous section, the Detailed Contents, or the Amiga E Encyclopedia.

# 23 Recursion Example

This next example uses a pair of mutually recursive procedures to draw what is known as a dragon curve (a pretty, space-filling pattern).

```MODULE 'intuition/intuition', 'graphics/view'

/* Screen size, use SIZEY=512 for a PAL screen */
CONST SIZEX=640, SIZEY=400

/* Exception values */
ENUM WIN=1, SCRN, STK, BRK

/* Directions (DIRECTIONS gives number of directions) */
ENUM NORTH, EAST, SOUTH, WEST, DIRECTIONS

RAISE WIN  IF OpenW()=NIL,
SCRN IF OpenS()=NIL

/* Start off pointing WEST */
DEF state=WEST, x, y, t

/* Face left */
PROC left()
state:=Mod(state-1+DIRECTIONS, DIRECTIONS)
ENDPROC

/* Move right, changing the state */
PROC right()
state:=Mod(state+1, DIRECTIONS)
ENDPROC

/* Move in the direction we're facing */
PROC move()
SELECT state
CASE NORTH; draw(0,t)
CASE EAST;  draw(t,0)
CASE SOUTH; draw(0,-t)
CASE WEST;  draw(-t,0)
ENDSELECT
ENDPROC

/* Draw and move to specified relative position */
PROC draw(dx, dy)
/* Check the line will be drawn within the window bounds */
IF (x>=Abs(dx)) AND (x<=SIZEX-Abs(dx)) AND
(y>=Abs(dy)) AND (y<=SIZEY-10-Abs(dy))
Line(x, y, x+dx, y+dy, 2)
ENDIF
x:=x+dx
y:=y+dy
ENDPROC

PROC main() HANDLE
DEF sptr=NIL, wptr=NIL, i, m
/* Read arguments:        [m [t [x  [y]]]] */
/* so you can say: dragon  16              */
/*             or: dragon  16 1            */
/*             or: dragon  16 1 450        */
/*             or: dragon  16 1 450 100    */
/* m is depth of dragon, t is length of lines */
/* (x,y) is the start position */
m:=Val(arg, {i})
t:=Val(arg:=arg+i, {i})
x:=Val(arg:=arg+i, {i})
y:=Val(arg:=arg+i, {i})
/* If m or t is zero use a more sensible default */
IF m=0 THEN m:=5
IF t=0 THEN t:=5
sptr:=OpenS(SIZEX,SIZEY,4,V_HIRES OR V_LACE,'Dragon Curve Screen')
wptr:=OpenW(0,10,SIZEX,SIZEY-10,
'Dragon Curve Window',sptr,\$F,NIL)
/* Draw the dragon curve */
dragon(m)
WHILE WaitIMessage(wptr)<>IDCMP_CLOSEWINDOW
ENDWHILE
EXCEPT DO
IF wptr THEN CloseW(wptr)
IF sptr THEN CloseS(sptr)
SELECT exception
CASE 0
WriteF('Program finished successfully\n')
CASE WIN
WriteF('Could not open window\n')
CASE SCRN
WriteF('Could not open screen\n')
CASE STK
WriteF('Ran out of stack in recursion\n')
CASE BRK
WriteF('User aborted\n')
ENDSELECT
ENDPROC

/* Draw the dragon curve (with left) */
PROC dragon(m)
/* Check stack and ctrl-C before recursing */
IF FreeStack()<1000 THEN Raise(STK)
IF CtrlC() THEN Raise(BRK)
IF m>0
dragon(m-1)
left()
nogard(m-1)
ELSE
move()
ENDIF
ENDPROC

/* Draw the dragon curve (with right) */
PROC nogard(m)
IF m>0
dragon(m-1)
right()
nogard(m-1)
ELSE
move()
ENDIF
ENDPROC
```

If you write this to the file `dragon.e' and compile it to the executable `dragon' then some good things to try are:

```dragon 5 9 300 100
dragon 10 4 250 250
dragon 11 3 250 250
dragon 15 1 300 100
dragon 16 1 400 150
```

If you want to understand how the program works you need to study the recursive parts. Here's an overview of the program, outlining the important aspects:

• The constants `SIZEX` and `SIZEY` are the width and height (respectively) of the custom screen (and window). As the comment suggests, change `SIZEY` to 512 if you want a bigger screen and you have a PAL Amiga.
• The `state` variable holds the current direction (north, south, east or west).
• The `left` and `right` procedures turn the current direction to the left and right (respectively) by using some modulo arithmetic trickery.
• The `move` procedure uses the `draw` procedure to draw a line (of length `t`) in the current direction from the current point (stored in `x` and `y`).
• The `draw` procedure draws a line relative to the current point, but only if it fits within the boundaries of the window. The current point is moved to the end of the line (even if it isn't drawn).
• The `main` procedure reads the command line arguments into the variables `m`, `t`, `x` and `y`. The depth/size of the dragon is given by `m` (the first argument) and the length of each line making up the dragon is given by `t` (the second argument). The starting point is given by `x` and `y` (the final two arguments). The defaults are five for `m` and `t`, and zero for `x` and `y`.
• The `main` procedure also opens the screen and window, and sets the dragon drawing.
• The `dragon` and `nogard` procedures are very similar, and these are responsible for creating the dragon curve by calling the `left`, `right` and `move` procedures.
• The `dragon` procedure contains a couple of checks to see if the user has pressed Control-C or if the program has run out of stack space, raising an appropriate exception if necessary. These exceptions are handled by the `main` procedure.

Notice the use of `Val` and the exception handling. Also, the important base case of the recursion is when `m` reaches zero (or becomes negative, but that shouldn't happen). If you start off a big dragon and want to stop it you can press Control-C and the program tidies up nicely. If it has finished drawing you simply click the close gadget on the window.

Go to the Next or Previous section, the Detailed Contents, or the Amiga E Encyclopedia.