How to fix Segfault due to recursive algorithm

Question

I'm trying to code a perfect maze generator, but I have few problems in the code due to the recursion which leads to Segfault when the maze is too big. Here is the main part of the code:

t_maze      *init_maze(int w, int h)
{
  t_maze    *maze;
  int       j;
  int       i;

  if ((maze = malloc(sizeof(t_maze))) == NULL)
    return (NULL);

  maze->w = w;
  maze->h = h;

  if ((maze->cells = malloc(sizeof(char *) * maze->h)) == NULL)
    return (NULL);

  j = -1;
  while (++j < maze->h)
  {
     if ((maze->cells[j] = malloc(sizeof(char) * maze->w)) == NULL)
        return (NULL);

     i = -1;
     while (++i < maze->w)
        maze->cells[j][i] = (j % 2 == 1 || i % 2 == 1) ? (1) : (0);
  }
  return (maze);
}

void        detect_neighbours(t_maze *maze, char *neighbours, int x,
                int y)
{
  int       i;

  // I fill the array with 1 (means there is no neighbours)
  // If there is a neighours, I set the cell to 0
  // In this order: Top, right, bottom, left
  i = -1;
  while (++i < 4)
    neighbours[i] = 1;
  if (y - 2 >= 0 && x >= 0 && y - 2 < maze->h
      && x < maze->w && maze->cells[y - 2][x] == 0)
    neighbours[0] = 0;
  if (x + 2 >= 0 && x + 2 < maze->w && y >= 0 && y < maze->h
      && maze->cells[y][x + 2] == 0)
    neighbours[1] = 0;
  if (y + 2 < maze->h && y + 2 >= 0 && x >= 0
      && x < maze->w && maze->cells[y + 2][x] == 0)
    neighbours[2] = 0;
  if (x - 2 >= 0 && x - 2 < maze->w && y >= 0 && y < maze->h
      && maze->cells[y][x - 2] == 0)
    neighbours[3] = 0;
}

int     there_is_no_neighbours(char *neighbours)
{
  int       i;

  // this function returns 0 if there is at least 1 neigbours
  i = -1;
  while (++i < 4)
    if (neighbours[i] == 0)
      i = 41;
  if (i == 42)
    return (0);
  return (1);
}

void        set_maze_protected(t_maze *maze, int y, int x, int val)
{
  // To prevent segfault when I put values in the maze,
  // I check the x and y keys
  if (x >= 0 && y >= 0 && x < maze->w && y < maze->h)
    maze->cells[y][x] = val;
}

int     build_maze(t_maze *maze, int x, int y)
{
  char      neighbours[4];
  int       i;
  int       ret;

  ret = 0;
  detect_neighbours(maze, neighbours, x, y);
  if (there_is_no_neighbours(neighbours) == 1)
    return (0);
  i = rand() % 4;
  while (neighbours[i] == 1)
    i = rand() % 4;
  if (i == 0)
    {
      set_maze_protected(maze, y - 1, x, 2);
      set_maze_protected(maze, y - 2, x, 2);
      ret = build_maze(maze, x, y - 2);
    }
  if (i == 1)
    {
      set_maze_protected(maze, y, x + 1, 2);
      set_maze_protected(maze, y, x + 2, 2);
      ret = build_maze(maze, x + 2, y);
    }
  if (i == 2)
    {
      set_maze_protected(maze, y + 1, x, 2);
      set_maze_protected(maze, y + 2, x, 2);
      ret = build_maze(maze, x, y + 2);
    }
  if (i == 3)
    {
      set_maze_protected(maze, y, x - 1, 2);
      set_maze_protected(maze, y, x - 2, 2);
      ret = build_maze(maze, x - 2, y);
    }
  while (ret != 0)
    ret = build_maze(maze, x, y);
  return (1);
}
int     main()
{
  t_maze    *maze;
  int       w;
  int       h;

  w = 50;
  h = 50;
  srand(time(NULL) * getpid());
  if ((maze = init_maze(w, h)) == NULL)
    return (1);
  maze->cells[0][0] = 2;
  build_maze(maze, 0, 0);
  // display_maze shows values in the 2D array (maze->cells)
  display_maze(maze);
  return (0);
}

I call this function in main with this call:

build_maze(maze, 0, 0);

The function detects is the cell has neighbours, and if it has, the function calls one of them randomly and open the door between the two.

If the x and y args are bigger than 2500 for example, it will segfault. (If it is less than 2500, it will work great)

How to fix this ?

I learnt about tail call but I ignore how to implement that in this case,

Thank you,

Best Regards

Answer 1

You can increase the stack size.

On POSIX systems, you can use the following code.

#include<stdio.h>
#include <sys/resource.h>
#define required_stack_size 0x8000000 // change this to the stack size you need

int main (int argc, char **argv)
{
    struct rlimit rl;
    int result;

    if((result = getrlimit(RLIMIT_STACK, &rl)) < 0)
    {
        fprintf(stderr, "getrlimit returned result %d\n", result);
        return -1;
    }
    if(rl.rlim_cur<required_stack_size)
    {
        rl.rlim_cur = required_stack_size;
        if((result = setrlimit(RLIMIT_STACK, &rl)) < 0)
        {
            fprintf(stderr, "setrlimit returned result = %d\n", result);
            return -1;
        }
    }

    //the rest code
    return 0;
}