Dragon Curve

The dragon curve or Heighway Dragon is a beautiful self-similar fractal first investigated by NASA physicists John Heighway, Bruce Banks, and William Harter.

Jack [Heighway] came into my office (actually cubicle) and said that if you folded a one dollar bill repeatedly he thought it would make a random walk or something like that. (We’d been arguing about something in Feller’s book on return chances.) I was dubious but said “Let’s check it out with a big piece of paper.” (Those were the days when NASA could easily afford more than one dollar’s worth of paper.) Well, it made a funny pattern alright but we couldn’t really see it too clearly. So one of us thought to use tracing paper and “unfold” it indefinitely so we could record (tediously) as big a pattern as we wanted. But each time we made the next order, it just begged us to make one more!

As they folded, and unfolded, a pattern emerged:

When you made a single fold you get a single right turn:

Right

After a second fold, you would get:

Right Right Left

And the third:

Right Right Left Right Right Left Left

Fourth:

Right Right Left Right Right Left Left Right Right Right Left Left Right Left Left

The sequence of turns are actually following a specific pattern:

$$S_{n+1} = S_n R \bar{S_n}$$

where $\bar{S}$ is the same sequence but reversed in direction and you replace L's with R's and vice-versa. The $n+1$'th fold appends the $R$ then the subsequent folds are the same sequence but reversed in order and direction.

The animation on the sidebar uses this sequence to iteratively trace out the curve:

function dragonCurveIter(seq,iterations) {
    // 0 - L , 1 - R
    for(var i = 0; i < iterations; i++) {
        var a = seq.reverse().map(function(x){return Number(!x)})
        seq.reverse().push(1);
        seq = seq.concat(a);
    }
    return seq
}

Interestingly enough, this recursive definition can also be interpreted geometrically. Appending $R\bar{S_n}$ is equivalent to having the original curve rotated by 90 degrees about the endpoint of the curve.