The dragon

fractal is a

path that doubles in length, and the distance from start to finish grows by a multiple of 2^.5 for every new iteration.

**Some interesting facts about this fractal**
No edges overlap.

Appears several times in the book "

Jurassic Park".

Virtually no application in real life.

**How to draw it**
Step 1: Draw the previous

iteration from start to finish.

Step 2: Starting at the finishing point of that image, draw a copy of that image
so that the copy is a 90° rotation of the first image, rotated about the finish point of the previous image.
(
The rotation can be either clockwise or counter-clockwise, as long as it is consistant throughout all other iterations.
)

**The first few iterations**
Iteration 0 Iteration 1 Iteration 2 Iteration 3
_ _ _
| | _| | _| |
|_
_|
Iteration 4 Iteration 5 Iteration 6
_ _ _ _
_| | _| | _ |_|_| |_
|_ |_ _| | _ _| _|
_|_ _|_ _ _ |_ |_|_|_
|_| |_ |_| |_|_|_| |_ _|_ _ _|_|_|
_| _|_| _| |_| |_|_|_| |_|_
|_| _|_| _|_|
|_| |_|
Iteration 7 Iteration 8
_ _ _ _
|_|_| |_ |_|_| |_
_ _| _| _ _| _|
|_|_|_ |_|_|_
|_|_| |_|_|
|_ _ |_ _ _ _
_ _|_|_| _ _|_|_| _|_| _|_|
|_|_|_|_|_ _ |_|_|_|_|_ _|_|_ _|_|_ _
|_|_|_|_|_|_| |_| |_| |_|_|_|_|_|_|_|_|_|_|
_ |_|_| |_|_ |_|_|_|_|_|_| |_|_
_| | _ _| _|_| _ _|_|_|_|_| _|_|
|_ |_|_|_ |_| |_|_|_|_|_|_|_ |_|
_|_ _ _|_|_| |_| |_| |_|_|
|_| |_|_|_| |_|_ |_ _
_|_| _|_| _ _|_|_|
|_| |_| |_|_|_|_|_ _
|_|_|_|_|_|_|
_ |_|_| |_|_
_| | _ _| _|_|
|_ |_|_|_ |_|
_|_ _ _|_|_|
|_| |_|_|_| |_|_
_|_| _|_|
|_| |_|
Iteration 9
_ _
_|_| _|_|
|_|_ _|_|_ _
_ _ _|_|_|_|_|_|_|_|
|_|_| |_ _ |_|_|_|_|_| |_|_
_ _| _| _|_| _|_|_|_| _|_|
|_|_|_ |_|_ _|_|_|_|_ |_|
|_|_| _|_|_|_|_|_|_|_|
|_ _ _ |_|_|_|_|_|_|_|_ _ _ _
_ _|_|_| _|_| _|_|_|_|_|_|_|_|_|_| _|_| _|_|
|_|_|_|_|_ _|_|_ _|_|_|_|_|_|_|_|_|_|_ _|_|_ _|_|_ _
|_| |_| |_|_|_|_|_| |_| |_|_|_|_|_| |_| |_|_|_|_|_|_|_|_|_|_|
|_|_|_|_ |_|_|_|_ |_|_|_|_|_|_| |_|_
_ _|_| |_| _ _|_| |_| _ _|_|_|_|_| _|_|
|_|_|_|_ |_|_|_|_ |_|_|_|_|_|_|_ |_|
|_| |_| |_| |_| |_| |_| |_|_|
|_ _
_ _|_|_|
|_|_|_|_|_ _
|_|_|_|_|_|_|
_ |_|_| |_|_
_| | _ _| _|_|
|_ |_|_|_ |_|
_|_ _ _|_|_|
|_| |_|_|_| |_|_
_|_| _|_|
|_| |_|

**The recurrence relation**
Fold

_{0} = (no turns)

Fold

_{n} = First

_{n} + "L" + Last

_{n}
First

_{n} = Fold

_{n-1}
Last

_{n} = (Fold

_{n-1})'

(apostrophe means traverse the path backwards.)

Basically what these equations mean is that A) the first iteration is just a straight path with no turning, and
B) in further iterations, drawing the image involves drawing the first half, making a 90° rotation (a left turn in this case), and then drawing the second half.
The first half involves drawing the previous iteration, the second half involves drawing the first image

*backwards*,
i.e.
the path is traversed in reverse order,
and every right turn becomes a left turn and vice versa.

**The computer program**
If a computer program was to draw this as described above, drawing the second half would be expensive because the
program has to create a

stack of turns before it can draw a path backwards.
A cheaper way of calculating the second part can be derived from further expanding the equation:

Last

_{n} = (First

_{n-1} + "L" + Last

_{n-1})'

Last

_{n} = (Last

_{n-1})' + ("L")' + (First

_{n-1})' // switch order

Last

_{n} = First

_{n-1} + "R" + Last

_{n-1} // Left turn becomes right turn, etc.

Now the first part and the last part of the iteration differs only by one turn.

Thus the cheaper

algorithm in

pseudo-code follows:

void Fold (int turn, int n) {
if (n == 0) {
drawSegment();
}
else {
Fold (LEFT, n - 1); // same as First(n).
Turn (turn);
Fold (RIGHT, n - 1); // same as Last(n).
}
}