Dragon curve

A simple fractal that can be made with a piece of paper. Basically, take a nice, long piece of paper, fold it half, then fold it in half again, then fold it in half again. Unfold it so that all the folds are 90-degree angles. You now have a 3rd order dragon fractal!

Of course, you can repeat the folding process again to get higher order dragon fractals. About the most you can do is 8th order. Any more than that, and you'll have to write a computer program to draw it for you, which really isn't very hard (e.g. http://www.crosswinds.net/~kodkod/fractal/tut06.html).

Here are the first few stages of the dragon fractal, in ASCII.

 __
|       Order 1  
|

 __
|  |
|  |__  Order 2


 _
| |_
   _|   Order 3
  |_ 


 _
|_|_
 _|     Order 4
|_   _
  |_|_|
    |

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₀ = (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).
  }
}

In Jurassic Park, at each chapter heading, there is a fractal. You would find at chapter one, for instance, the following:

                 _____                                      
                      |
                      |
     _____       _____|
    |     |     |
    |     |     |
    |_____|_____|
          |
          |
     _____|
    |
    |
    |_____      *
          |     |
          |     |
          |_____|

      Iteration 1

The next one was more complex, and so on, and so forth. The astute among you would notice that this pattern is fractal in shape. This is a series known as a dragon curve, or, as the title of the node formerly suggested, the Jurassic Park Fractal, thanks to Crichton's attention given to it. Now, every fractal has a pattern of some sort, so let's look at this one.

First, I seriously doubt that this was in fact the "first iteration" of this thing. It's way too complex for that. Now, we know that the length of each line segment is the same, so that's not helping us much. So let's look at the turns. It would appear that it goes, from the start(labeled with an asterisk above):

Right, Right, Left, Right, Right, Left, Left, Right, Right, Right, Left, Left, Right, Left, Left...

Right? Anyway, let's see if we have any sort of symmetry here. We have an odd number of turns, so that means there's a dividing one, which I have bolded above. To each side of it, it appears that we have the opposite on each, right for left, and so on and so forth. So that means that the first iteration is something like this:

         *
         |
         |
    _____|

Hmm... that's just Right, it acting as its own center. Now, I'm going to cheat a little bit, and give you a freebie, but it's something you'd find if you compared Crichton's first and second iterations. It's that each iteration starts with the pattern of turns of the one before it... so iteration two starts off Right, Right, then of course, Left, balancing the sentence.

These are all the rules of the aforementioned fractal... but I'll give them to you again for simplicity's sake:

1. The center turn is always Right
2. The first half of the order is always the full order of the last iteration.
3. The second half is the exact reverse of the first. (See Right,Right,Left)

There is indeed an alternate way of determining the second half which is far more mathematical and useful for programming, say. The second half, if you notice, is the first half repeated, but with one change, that of the 2^n-2th term of the original sequence, i.e.:
Right, Right, Left, Right, Right, Left, Right

Clearly, this is useless when n=1, but hey, when n=1 the fractal is just Right, setting yourself up for a classic recursive function.