Построение кривой Серпинского без использования рекурсии

#c_sharp #алгоритм

Доброго времени суток. 

Необходимо реализовать рекурсивную и нерекурсивную реализацию построения кривой Серпинского. 

Рекурсивное построение не составило большого труда, а вот найти конечный алгоритм
для нерекурсивной реализации (понятный для имплементации) не получилось (Только в книге
Род Стивене - "Delphi Готовые алгоритмы").

Может ли кто-нибудь скинуть материалы где можно почитать про нерекурсивную имплементацию
построения кривых Серпинского?

Реализация Рекурсивного алгоритма:

static private void Sierpinski(int depth, float dx, float dy, Graphics gr = null){
            float x = dx;
            float y = dy;
        drawA(gr, depth, ref x, ref y, dx, dy);
        drawLine(gr, ref x, ref y, dx, dy);
        drawB(gr, depth, ref x, ref y, dx, dy);
        drawLine(gr, ref x, ref y, -dx, dy);
        drawC(gr, depth, ref x, ref y, dx, dy);
        drawLine(gr, ref x, ref y, -dx, -dy);
        drawD(gr, depth, ref x, ref y, dx, dy);
        drawLine(gr, ref x, ref y, dx, -dy);
    }

    static private void drawA(Graphics gr, int depth, ref float x, ref float y, float
dx, float dy)
    {
        if (depth > 0)
        {
            --depth;
            drawA(gr, depth, ref x, ref y, dx, dy);
            drawLine(gr, ref x, ref y, dx, dy);
            drawB(gr, depth, ref x, ref y, dx, dy);
            drawLine(gr, ref x, ref y, 2 * dx, 0);
            drawD(gr, depth, ref x, ref y, dx, dy);
            drawLine(gr, ref x, ref y, dx, -dy);
            drawA(gr, depth, ref x, ref y, dx, dy);
        }
    }

    static private void drawB(Graphics gr, int depth, ref float x, ref float y, float
dx, float dy)
    {
        if (depth > 0)
        {
            --depth;
            drawB(gr, depth, ref x, ref y, dx, dy);
            drawLine(gr, ref x, ref y, -dx, dy);
            drawC(gr, depth, ref x, ref y, dx, dy);
            drawLine(gr, ref x, ref y, 0, 2 * dy);
            drawA(gr, depth, ref x, ref y, dx, dy);
            drawLine(gr, ref x, ref y, dx, dy);
            drawB(gr, depth, ref x, ref y, dx, dy);
        }
    }

    static private void drawC(Graphics gr, int depth, ref float x, ref float y, float
dx, float dy)
    {
        if (depth > 0)
        {
            --depth;
            drawC(gr, depth, ref x, ref y, dx, dy);
            drawLine(gr, ref x, ref y, -dx, -dy);
            drawD(gr, depth, ref x, ref y, dx, dy);
            drawLine(gr, ref x, ref y, -2 * dx, 0);
            drawB(gr, depth, ref x, ref y, dx, dy);
            drawLine(gr, ref x, ref y, -dx, dy);
            drawC(gr, depth, ref x, ref y, dx, dy);
        }
    }

    static private void drawD(Graphics gr, int depth, ref float x, ref float y, float
dx, float dy)
    {
        if (depth > 0)
        {
            --depth;
            drawD(gr, depth, ref x, ref y, dx, dy);
            drawLine(gr, ref x, ref y, dx, -dy);
            drawA(gr, depth, ref x, ref y, dx, dy);
            drawLine(gr, ref x, ref y, 0, -2 * dy);
            drawC(gr, depth, ref x, ref y, dx, dy);
            drawLine(gr, ref x, ref y, -dx, -dy);
            drawD(gr, depth, ref x, ref y, dx, dy);
        }
    }


Реализация функции drawLine():

static private void drawLine(Graphics gr, ref float x, ref float y, float dx, float dy)
        {
            if (gr != null)
                gr.DrawLine(Pens.Black, x, y, x + dx, y + dy);
            x += dx;
            y += dy;
        }

    

Ответы

Ответ 1

Воспользуемся стандартным подходом: перепишем функцию в виде набора заданий и управляющего
цикла, который выполняет задания по одному. Вместо рекурсивного вызова функций будем
добавлять новые задания в стек этих самых заданий. Этим самым мы как бы заменяем стек
вызовов стеком заданий.

Для нашего случая, заведём структуру данных, описывающую одно задание. Одним заданием
у нас будет вызов drawA, drawB, drawC, drawD или drawLine. Получаем следующую структуру:

struct DrawTask
{
    public DrawTask(char type, int depth, float dx = 0, float dy = 0)
    {
        Type = type;
        Depth = depth;
        Linedx = dx;
        Linedy = dy;
    }

    public char Type; // A, B, C, D или L
    public int Depth;
    public float Linedx; // эти параметры нужны лишь для задания типа L
    public float Linedy;
}


Теперь нам нужна очередь заданий и её интерпретатор:

static void Sierpinski_NR(int depth, float dx, float dy, Graphics gr = null)
{
    Stack taskStack = new Stack();
    float x = dx;
    float y = dy;

    // загружаем задания в стек в обратном порядке
    taskStack.Push(new DrawTask('L', depth, dx, -dy));
    taskStack.Push(new DrawTask('D', depth));
    taskStack.Push(new DrawTask('L', depth, -dx, -dy));
    taskStack.Push(new DrawTask('C', depth));
    taskStack.Push(new DrawTask('L', depth, -dx, dy));
    taskStack.Push(new DrawTask('B', depth));
    taskStack.Push(new DrawTask('L', depth, dx, dy));
    taskStack.Push(new DrawTask('A', depth));

    // пока есть задание, достаём его и выполняем
    // в результате выполнения в стеке могут оказаться подзадания
    while (taskStack.Count > 0)
    {
        var currentTask = taskStack.Pop();
        switch (currentTask.Type)
        {
        case 'A':
            drawA_NR(gr, currentTask.Depth, ref x, ref y, dx, dy, taskStack);
            break;
        case 'B':
            drawB_NR(gr, currentTask.Depth, ref x, ref y, dx, dy, taskStack);
            break;
        case 'C':
            drawC_NR(gr, currentTask.Depth, ref x, ref y, dx, dy, taskStack);
            break;
        case 'D':
            drawD_NR(gr, currentTask.Depth, ref x, ref y, dx, dy, taskStack);
            break;
        case 'L':
            drawLine(gr, ref x, ref y, currentTask.Linedx, currentTask.Linedy);
            break;
        }
    }
}


Процедуру A имплементируем таким же образом. Она сама не делает ничего, просто добавляет
в стек подзадания:

static void drawA_NR(Graphics gr, int depth, ref float x, ref float y, float dx,
float dy,
                     Stack taskStack)
{
    if (depth > 0)
    {
        --depth;

        // помещаем в стек в обратном порядке
        taskStack.Push(new DrawTask('A', depth));
        taskStack.Push(new DrawTask('L', depth, dx, -dy));
        taskStack.Push(new DrawTask('D', depth));
        taskStack.Push(new DrawTask('L', depth, 2 * dx, 0));
        taskStack.Push(new DrawTask('B', depth));
        taskStack.Push(new DrawTask('L', depth, dx, dy));
        taskStack.Push(new DrawTask('A', depth));
    }
}


Остальные процедуры реализуются аналогично:

static void drawB_NR(Graphics gr, int depth, ref float x, ref float y, float dx,
float dy,
                     Stack taskStack)
{
    if (depth > 0)
    {
        --depth;
        taskStack.Push(new DrawTask('B', depth));
        taskStack.Push(new DrawTask('L', depth, dx, dy));
        taskStack.Push(new DrawTask('A', depth));
        taskStack.Push(new DrawTask('L', depth, 0, 2 * dy));
        taskStack.Push(new DrawTask('C', depth));
        taskStack.Push(new DrawTask('L', depth, -dx, dy));
        taskStack.Push(new DrawTask('B', depth));
    }
}

static void drawC_NR(Graphics gr, int depth, ref float x, ref float y, float dx,
float dy,
                     Stack taskStack)
{
    if (depth > 0)
    {
        --depth;
        taskStack.Push(new DrawTask('C', depth));
        taskStack.Push(new DrawTask('L', depth, -dx, dy));
        taskStack.Push(new DrawTask('B', depth));
        taskStack.Push(new DrawTask('L', depth, -2 * dx, 0));
        taskStack.Push(new DrawTask('D', depth));
        taskStack.Push(new DrawTask('L', depth, -dx, -dy));
        taskStack.Push(new DrawTask('C', depth));
    }
}

static void drawD_NR(Graphics gr, int depth, ref float x, ref float y, float dx,
float dy,
                     Stack taskStack)
{
    if (depth > 0)
    {
        --depth;
        taskStack.Push(new DrawTask('D', depth));
        taskStack.Push(new DrawTask('L', depth, -dx, -dy));
        taskStack.Push(new DrawTask('C', depth));
        taskStack.Push(new DrawTask('L', depth, 0, -2 * dy));
        taskStack.Push(new DrawTask('A', depth));
        taskStack.Push(new DrawTask('L', depth, dx, -dy));
        taskStack.Push(new DrawTask('D', depth));
    }
}