Is it possible to generate an $M$-order Hilbert Curve without consuming $O(M^2)$ memory?

Question

This question is admittedly very programming related, but I felt that it is better suited to the Mathematics crowd than Stack Overflow.

---

I would like to generate Hlibert walks through the pixels in an image (or really, any 2d coordinate space), but I would like to consume as little memory as possible. However, given how the Hilbert curve is defined, I would be required to generate the moves (N, S, E, or W) all at once, consuming much more memory that I would like.

Is it even possible to generate a Hilbert curve in an "online" fashion, with sub-linear memory space with respect to the order of the curve?

---

For reference, this is the definition of the Hilbert curve that I'm using, giving relative directions:

$$\begin{align} hilbert(order) &= A_{order+1} \\ A_0 &= [\,] \\ B_0 &= [\,] \\ C_0 &= [\,] \\ D_0 &= [\,] \\ A_n &= [B_{n-1}, N, A_{n-1}, E, A_{n-1}, S, C_{n-1}] \\ B_n &= [A_{n-1}, E, B_{n-1}, N, B_{n-1}, W, D_{n-1}] \\ C_n &= [D_{n-1}, W, C_{n-1}, S, C_{n-1}, E, A_{n-1}] \\ D_n &= [C_{n-1}, S, D_{n-1}, W, D_{n-1}, N, B_{n-1}] \end{align}$$

An ideal implementation would be implementable as a "iterator" (C#, etc) or "sequence" (Haskel, etc)

Answer 1

I believe that I have found a solution, but I need help verifying its memory complexity. I believe it to be O(n) with respect to the order of the curve, since the stack never grows beyond order elements, and each element is a constant size.

private static Dictionary<char, string> replacements = new Dictionary<char, string>
{
    { 'A', "BNAEASC" },
    { 'B', "AEBNBWD" },
    { 'C', "DWCSCEA" },
    { 'D', "CSDWDNB" },
};

private static IEnumerable<char> Hilbert(int order)
{
    if (order <= 0)
    {
        throw new ArgumentOutOfRangeException("order", "Must be a natural number.");
    }

    // Initialize the stack with A
    var stack = new Stack<string>(order);
    stack.Push(replacements['A']);

    while (true)
    {
        // Find the first non-empty string, clearing the stack of empty ones and terminating if none are found.
        var element = "";
        while (element == "")
        {
            if (stack.Count == 0)
            {
                yield break;
            }

            element = stack.Pop();
        }

        // Read the next command, c, from the found element and push the rest of the commands back on the stack.
        var c = element[0];
        stack.Push(element.Substring(1));

        switch (c)
        {
            // If the command is a movement, yield it.
            case 'N':
            case 'S':
            case 'E':
            case 'W':
                yield return c;
                break;

            // Otherwise, the command is a replacement.  Push the replacement onto the stack, unless the replacement should be empty.
            default:
                if (stack.Count < order)
                {
                    stack.Push(replacements[c]);
                }

                break;
        }
    }
}