Should I use global variables in recursion

Question

I created a function in C to find the shortest path out of a triangle maze using recursion. I use 2 global variables in the function, which I want to get rid of because I know that global variables should not be used.

The variable moves, I could pass as an argument, but I don't know if it's bad memory management to overwhelm the stack like that. The other global variable foundExit would not work as an argument, so I don't know how to get rid of it.

So my question is whether I should use global variables in case of recursion.

Note that every number in our array is some 3-bit number, where 1 represents wall and 0 empty wall. 001 is left wall, 010 is right wall, 100 is bottom/upper wall. So for example 111 represents triangle with all his walls.

Picture of our maze saved in cells:

Simplified code:

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

typedef struct {
    int rows;
    int cols;
    unsigned char *cells;
} Map;

void NegateEntraceBit(Map *map, unsigned char r, unsigned char c) {
    char whichWall;
    if (c == 0) { // From left.
        whichWall = 0;
    }
    else if (c == map->cols - 1) { // From right.
        whichWall = 1;
    }
    else if (r == 0) { // From up.
        whichWall = 2;
    }
    else if (r == map->rows - 1) { // From down.
        whichWall = 2;
    }

    //Inverting entrace bit.
    map->cells[map->cols * r + c] ^= (1 << whichWall); 
}

char InvertDirection(char direction) {
    if (direction == 0) {
        return 1;
    }
    else if (direction == 1) {
        return 0;
    } else {
        return 2;
    }
}

char moves[2][3][2] = {
    {{0,-1}, {0,1}, {-1,0}},
    {{0,-1}, {0,1}, {1,0}}
};

bool foundExit = false;

void shortestPath(Map map, int r, int c, char direction) {
/* 
         (r+c) % 2 == 1:        (r+c) % 2 == 0:
                ^               _________
              ╱   ╲             ╲   2   ╱
           0 ╱     ╲ 1         0 ╲     ╱ 1
            ╱_______╲             ╲   ╱
                2                   v
*/
    
    // Going in the direction if its the only way (triangle has value 0b100).
    while (map.cells[map.cols * r + c] == 3) {
        r += moves[(r+c) & 1][direction][0];
        c += moves[(r+c) & 1][direction][1];

        // This validating is performed when we go in 1 line to the exit.
        if (r < 0 || r >= map.rows || c < 0 || c >= map.cols) { // Outside position
            foundExit = true;
            return;
        }
    }

    // This validating is performed when a new instance is called.
    if (r < 0 || r >= map.rows || c < 0 || c >= map.cols) { // Outside position
        foundExit = true;
        return;
    }

    // This validating is performed when the only other way is in inverted direction.
    if ((map.cells[map.cols * r + c] ^ (1 << InvertDirection(direction))) == 0b111) {
        return;
    }

    printf("%d,%d\n", r+1, c+1);

    // For any other direction
    for (char direc = 0; direc < 3; direc++) {
        // that is (available && not in inverted direction),
        if ( !(map.cells[map.cols * r + c] & (1 << direc)) && (direc != InvertDirection(direction))) {
            // we call new instance with new coordinates.
            shortestPath(map,
                         r + moves[(r+c) & 1][direc][0], 
                         c + moves[(r+c) & 1][direc][1], 
                         direc);
        } 
        // Stopping any other instance that would be called even when the exit is found.
        if (foundExit) {
            break;
        }            
    }
}

int main() {
    Map map;
    map.rows = 6;
    map.cols = 7; // Set to the number of columns in your data

    // Allocate memory for 1D array
    map.cells = malloc(sizeof(unsigned char) * (map.rows * map.cols));

    // Initialize the 1D array directly
    unsigned char initialData[] = {
        1, 4, 4, 2, 5, 0, 6,
        1, 4, 4, 0, 4, 0, 2,
        1, 0, 4, 0, 4, 6, 1,
        1, 2, 7, 1, 0, 4, 2,
        3, 1, 4, 2, 3, 1, 2,
        4, 2, 5, 0, 4, 2, 5
    };

    for (int i = 0; i < map.rows * map.cols; i++) {
        map.cells[i] = initialData[i];
    }
    int r = 6;
    int c = 1;

    int rows = r-1;
    int cols = c-1;

    // Closing entrace bit so its not the shortest path out.
    NegateEntraceBit(&map, rows, cols);
    //For every direction
    for (char direc = 0; direc < 3; direc++) {
        // That is available (0).
        if ( !(map.cells[map.cols * rows + cols] & (1 << direc)) ) {
            shortestPath(map, rows, cols, direc);
        }     
    }

    // Free allocated memory
    free(map.cells);

    return 0;
}

Answer 1

Both globals are accessed in a single function shortestPath() so they can be declared as static within that function.

void shortestPath(Map map, int r, int c, char direction) 
{
    static char moves[2][3][2] = {
        {{0,-1}, {0,1}, {-1,0}},
        {{0,-1}, {0,1}, {1,0}}
    };

    static bool foundExit = false;

    ...

In other cases where a variable is shared amongst several functions, place all those functions and variables in a separately compiled source file and declare the variables and any functions that are not externally referenced static which in this case is a linkage specifier rather than storage class specifier as above, and restricts the scope to that translation unit (so no longer global).

Note that this is a general solution to the issue if global variables. It is not specific to recursion which is often also ill-advised. There are other techniques. It is possible to write code of any size with no global variables at all, ever.