How to predict a stack overflow? How and which memory is stored in stack?

I implemented a floodfill recursive function to check if a player will be able to reach the map exit or it'll be stacked surrounded by walls. So a simple map would look like this:

1 -> wall; 0 -> empty space; C -> collectible; P -> player; E -> exit

And my floodfill function:

void    find_accessible_elems(t_map *map, t_elems *elems, size_t i, size_t j)
{
    elems->iterations++;
    if (map->spaces[i][j] == EXIT)
        elems->exit++;
    else if (map->spaces[i][j] == COLLECTIBLE)
        elems->collectibles++;
    map->spaces[i][j] = 'A';
    if (map->spaces[i][j + 1] != 'A' && map->spaces[i][j + 1] != WALL)
        find_accessible_elems(map, elems, i, j + 1);
    if (map->spaces[i][j - 1] != 'A' && map->spaces[i][j - 1] != WALL)
        find_accessible_elems(map, elems, i, j - 1);
    if (map->spaces[i + 1][j] != 'A' && map->spaces[i + 1][j] != WALL)
        find_accessible_elems(map, elems, i + 1, j);
    if (map->spaces[i - 1][j] != 'A' && map->spaces[i - 1][j] != WALL)
        find_accessible_elems(map, elems, i - 1, j);
}

I obviously get a stack overflow when trying to validate big maps so I did exactly the same but iterative. It's working and I could only be using the iterative one, but it is much slower than recursive, which is really sad.

void    find_accessible_elems_iter(t_map *map, t_elems *elems)
{
    t_pos_stack *stack;

    stack = new_pos(map->player.pos.x, map->player.pos.y);
    while (stack)
    {
        if (map->spaces[stack->pos.y][stack->pos.x] == 'A' || map->spaces[stack->pos.y][stack->pos.x] == WALL)
        {
            shift_pos(&stack);
            continue ;
        }
        else if (map->spaces[stack->pos.y][stack->pos.x] == EXIT)
            elems->exit++;
        else if (map->spaces[stack->pos.y][stack->pos.x] == COLLECTIBLE)
            elems->collectibles++;
        map->spaces[stack->pos.y][stack->pos.x] = 'A';
        if (map->spaces[stack->pos.y][stack->pos.x + 1] != 'A'
                && map->spaces[stack->pos.y][stack->pos.x + 1] != WALL)
            push_pos(stack, stack->pos.x + 1, stack->pos.y);
        if (map->spaces[stack->pos.y][stack->pos.x - 1] != 'A'
                && map->spaces[stack->pos.y][stack->pos.x - 1] != WALL)
            push_pos(stack, stack->pos.x - 1, stack->pos.y);
        if (map->spaces[stack->pos.y + 1][stack->pos.x] != 'A'
                && map->spaces[stack->pos.y + 1][stack->pos.x] != WALL)
            push_pos(stack, stack->pos.x, stack->pos.y + 1);
        if (map->spaces[stack->pos.y - 1][stack->pos.x] != 'A'
                && map->spaces[stack->pos.y - 1][stack->pos.x] != WALL)
            push_pos(stack, stack->pos.x, stack->pos.y - 1);
        shift_pos(&stack);
        elems->iterations++;
    }
}

t_pos_stack *new_pos(size_t x, size_t y)
{
    t_pos_stack *pos;

    pos = safe_malloc(sizeof(t_pos_stack), NULL);
    pos->next = NULL;
    pos->pos.x = x;
    pos->pos.y = y;
    return (pos);
}

void    shift_pos(t_pos_stack **stack)
{
    t_pos_stack *aux;

    aux = (*stack)->next;
    free(*stack);
    *stack = aux;
}

void    push_pos(t_pos_stack *stack, size_t x, size_t y)
{
    while (stack->next)
        stack = stack->next;
    stack->next = new_pos(x, y);
}

My will is to use iterative only when necessary. To do so, I tried to calculate how many stack memory the function will use and compare it to the available stack memory using ulimit -s which is saved on macro MAX_STACK_SIZE_KB on Makefile.

int has_valid_path_map(t_map *map)
{
    t_elems elems;
    t_map   accessible_map;
    size_t  stack_call_size;
    size_t  prev_stack_size;

    copy_map(&accessible_map, map);
    elems.collectibles = 0;
    elems.exit = 0;
    elems.iterations = 0;
    stack_call_size = sizeof(&accessible_map) + sizeof(&elems) + sizeof(map->player.pos.y)
        + sizeof(map->player.pos.x);
    prev_stack_size = 500; // Don't know how to calculate this
    if ((map->max_x * map->max_y - map->walls_amount) * stack_call_size + prev_stack_size > MAX_STACK_SIZE_KB * 1024)
        find_accessible_elems_iter(&accessible_map, &elems);
    else
        find_accessible_elems(&accessible_map, &elems,
            map->player.pos.y, map->player.pos.x);
    terminate_map(&accessible_map);
    return (elems.exit &&
                elems.collectibles == ft_stroccurrences(map->elems, COLLECTIBLE));
}

The iterative function results to be called much before stack overflow would occur, meaning that the future stack memory is not well calculated.

I don't even know if that's possible but my questions are:

How and which memory is stored in stack?
How can I calculate the stack memory consumption for a function?

Solution

    if (map->spaces[stack->pos.y][stack->pos.x + 1] != 'A'
            && map->spaces[stack->pos.y][stack->pos.x + 1] != WALL)
        push_pos(stack, stack->pos.x + 1, stack->pos.y);
    if (map->spaces[stack->pos.y][stack->pos.x - 1] != 'A'
            && map->spaces[stack->pos.y][stack->pos.x - 1] != WALL)

In your iterative version, when it decides to queue to the square to the right, it calls push_pos(stack, stack->pos.x + 1, stack->pos.y), which presumably modifies the stack.

On the next line, when checking the square to the left, it uses the position now at the top of the stack, which is different coordinates than the prior check. Presumably this is a bug, probably causing it to miss a bunch of squares.

Separately, The only way I can speculate that this code would work is if push_pos and shift_pos are allocating and freeing nodes on the heap. That is the reason the iterative version is so slow. The algorithm isn't slower, it's merely the allocations and deallocations that are slower. Use a single large buffer and this'll be faster than the iterative version.