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

My question was answered, so the solution was to mark the moves variable as static.

To remove the foundExit variable, I decided to make the return value a bool. The logic is basically the same. As for the rest of the code, I changed it slightly, not keeping track of where I've been is extremely inefficient, so I created a new array visited where I just keep track of where I've been.

NOTE: After more analysis, I found that this algorithm does not always find the shortest path. The algorithm has the best performance when the shortest path is clear, only other dead-end paths come from the shortest path.

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;
    }
}

bool shortestPath(Map map, bool *visited, int r, int c, char direction) {
/* 
         (r+c) % 2 == 1:        (r+c) % 2 == 0:
                ^               _______________
              ╱   ╲             ╲      2      ╱
          0 ╱       ╲ 1         0 ╲         ╱ 1
          ╱           ╲             ╲     ╱
        ╱_______2_______╲              v
*/
    static char moves[2][3][2] = {
        {{0,-1}, {0,1}, {-1,0}},
        {{0,-1}, {0,1}, {1,0}}
    };

    r += moves[(r+c) & 1][direction][0];
    c += moves[(r+c) & 1][direction][1];

    if (visited[map.cols * r + c]) {
        return false;
    }
    
    visited[map.cols * r + c] = true;

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

    // 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 false;
    }

    // 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 wanted direction.
            if (shortestPath(map, visited, r, c, direc)) {
                printf("%d,%d\n", r+1, c+1 );
                return true;
            } 
        }         
    }
    return false;
}

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];
    }

    bool *visited = (bool *)malloc((map.rows * map.cols) * sizeof(bool));
    for (int i = 0; i < map.rows * map.cols; i++) {
        visited[i] = false;
    }

    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);
    bool foundExit = false;
    /// For any other direction
    for (char direc = 0; direc < 3; direc++) {
        // that is (available && not in inverted direction),
        if ( !(map.cells[map.cols * rows + cols] & (1 << direc)) ) {
            //we call new instance with wanted direction.
            foundExit |= (shortestPath(map, visited, rows, cols, direc));
            printf("%d,%d\n", r, c);
        }     
    }
    if (!foundExit) {
        printf("There is no exit in maze.\n");
    } 
    
    // Free allocated memory
    free(visited);
    free(map.cells);

    return 0;
}