trying to prevent stack overflow with tail recursion

Question

So I have a recursive function that results in a stack overflow error. I've tried applying tail recursion and 0x optimization in visual studio 2010. Still no luck. Any help would be appreciated. I could just make a while loop, but I wanted to learn recursive functions.

#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);

}

When I read the title, my first thought went rather to stackoverflow.com then to the actual problem. ^^ — Aufwind
– Aufwind, Commented Jan 9, 2012 at 0:32
It seems to me that for some reason is not doing the tail call optimization since it should loop forever instead of giving an stack overflow error. I tried to compile and see what's going on but I am missing some parts of the code: - board - sMoveOrder - BOARD_SIZE - sMoveOrder - horizontal - vertical Please include all your code so we can try help you with the exact code that you are using instead of a code with our guesses. :) — Pedrom
– Pedrom, Commented Jan 9, 2012 at 11:59

snowCrabs · Accepted Answer · 2012-01-09 00:31:45Z

1

Your function doesn't have a stop condition.

Essentially your function is calling itself until all of the memory is used up (Stack Overflow)

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

   MyRecursiveCall(nextArguement)
}

answered Jan 9, 2012 at 0:31

snowCrabs

7856 silver badges12 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

user998797 Over a year ago

My returns are commented out because I want to program to pause, but when they were in place, it didn't help.

Collectives™ on Stack Overflow

trying to prevent stack overflow with tail recursion

1 Answer 1

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related