пытаясь предотвратить переполнение стека с помощью хвостовой рекурсии - PullRequest
Новая
       28

пытаясь предотвратить переполнение стека с помощью хвостовой рекурсии

1 голос
/ 09 января 2012

Итак, у меня есть рекурсивная функция, которая приводит к ошибке переполнения стека. Я пытался применить хвостовую рекурсию и 0x оптимизацию в visual studio 2010. Все еще не повезло. Любая помощь будет оценена. Я мог просто сделать цикл while, но я хотел изучить рекурсивные функции. 

#include <cstdio>
#include <cstdlib>
#include <stdio.h>
#include <string.h>
#include <Windows.h>

#define BOARD_SIZE 64

int horizontal[8];
int vertical[8];

bool board[BOARD_SIZE];

typedef struct _MoveOrder
{
int row;
int col;
int move;
} MoveOrder;

MoveOrder sMoveOrder[BOARD_SIZE];

void MoveHelper();
void Move(int currentMove);


void main()
{
horizontal[0] = 2;
horizontal[1] = 1;
horizontal[2] = -1;
horizontal[3] = -2;
horizontal[4] = -2;
horizontal[5] = -1;
horizontal[6] = 1;
horizontal[7] = 2;

vertical[0] = -1;
vertical[1] = -2;
vertical[2] = -2;
vertical[3] = -1;
vertical[4] = 1;
vertical[5] = 2;
vertical[6] = 2;
vertical[7] = 1;

memset(sMoveOrder, 0, sizeof(MoveOrder) * BOARD_SIZE);

for(int i = 0; i < BOARD_SIZE; i++)
{
    sMoveOrder[i].move = -1;
}

for(int i = 0; i < BOARD_SIZE; i++)
{
    board[i] = false;
}

sMoveOrder[0].col = 0;
sMoveOrder[0].row = 0;

MoveHelper();

system("pause");

return;
}

void MoveHelper()
{
return Move(0);
}

static void Move(int currentMove)
{
int tempRow = 0;
int tempCol = 0;
int tempMove = sMoveOrder[currentMove].move;
bool bChangeRoute = true;

if(tempMove == -1)
{
    tempMove = 0;
}
else
{
    ++tempMove;
}

for(int i = tempMove; i < 8; i++)
{
    tempCol = sMoveOrder[currentMove].col + horizontal[i];
    tempRow = sMoveOrder[currentMove].row + vertical[i];

    if(tempRow >= 0 && tempRow <= 7)
    {
        if(tempCol >= 0 && tempCol <= 7)
        {
            if(!board[tempCol + (tempRow * 8)])
            {
                board[tempCol + (tempRow * 8)] = true;

                sMoveOrder[currentMove].move = i;

                ++currentMove;
                sMoveOrder[currentMove].col = tempCol;
                sMoveOrder[currentMove].row = tempRow;

                bChangeRoute = false;

                if(currentMove >= BOARD_SIZE - 1)
                {
                    printf("full\n");
                    for(int i = 0; i < BOARD_SIZE; i++)
                    {
                        if(!board[i])
                        {
                            printf("%d\n", i);
                        }
                    }
                    printf("full complete\n");

                    system("pause");
                    return;
                }

                break;
            }
        }
    }
}

if(bChangeRoute)
{
    board[sMoveOrder[currentMove].col + (sMoveOrder[currentMove].row * 8)] = false;
    sMoveOrder[currentMove].move = -1;

    --currentMove;
    if(currentMove <= 0)
    {
        currentMove = 0;

        sMoveOrder[currentMove].col += 1;

        if(sMoveOrder[currentMove].col >= 8)
        {
            sMoveOrder[currentMove].col = 0;
            sMoveOrder[currentMove].row += 1;

            if(sMoveOrder[currentMove].row >= 8)
            {
                printf("broken: %d\n", currentMove);

                system("pause");
                return;
            }
        }
    }
}


return Move(currentMove);

}

1 Ответ

1 голос
/ 09 января 2012

Ваша функция не имеет условия остановки.

По сути, ваша функция вызывает себя до тех пор, пока не израсходуется вся память (переполнение стека) 

void MyRecursiveCall(argument)
{
   Check Stop condition //return
   ..
   ..Doing stuff
   ..          

   MyRecursiveCall(nextArguement)
}
...