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,
              IDCMP_CLOSEWINDOW,WFLG_CLOSEGADGET,
              '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:

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.