Segmentation fault (recursion never ending) in C

Question

I am trying to solve this problem:

Given a Maze, it desired to find a path from a given starting position to the location with cheese (target position). Maze is visualized as a rectangular grid containing walls (represented as 1) or free ways (represented as 0). The program must print a path that starts from starting location to the ending location. The target location will have value 9 stored in it. In this program, it is assumed that cyclic paths are not possible in the grid. (You need not check for cyclic paths.)

This is what I am doing:

#include<stdio.h>

typedef struct Maze
{
    int ** values;
    int size;
} Maze;

int traverse (Maze M, int n, int posi, int posj, char **path_so_far,
        int past_i, int past_j)
{
    int k;
    printf("Hello\n");
    int i=0;
    int temp;  

    if (M.values[posi][posj] == 9)
    {
        path_so_far[i][0] = posi + '0';
        path_so_far[i][1] = posj + '0';
        path_so_far[i][2] = '\0';
        printf("%s\n", path_so_far[i]); 
        i++;
        return 1;    
    }
    else if (posi - 1 >= 0 && M.values[posi - 1][posj] != 1
            && posi - 1 != past_i)
    {      
        temp = traverse(M, n, posi - 1, posj, path_so_far, past_i, past_j);
        if (temp == 1)
        {
            path_so_far[i][0] = posi + '0';
            path_so_far[i][1] = posj + '0';
            path_so_far[i][2] = '\0';      
            printf("%s\n", path_so_far[i]);               
            i++;
            return 1;
        }
    }
    else if (posi + 1 < n && M.values[posi + 1][posj] != 1 && posi + 1 != past_i)
    {
        temp = traverse(M, n, posi + 1, posj, path_so_far, past_i, past_j);
        if (temp == 1)
        {
            path_so_far[i][0]=posi+'0';
            path_so_far[i][1]=posj+'0';
            path_so_far[i][2]='\0';  
            printf("%s\n",path_so_far[i]);                    
            i++;
            return 1;
        }
    }
    else if(posj - 1 >=0 && M.values[posi][posj - 1] !=1 && posj - 1 != past_j)
    { 
        temp = traverse(M, n, posi, posj - 1, path_so_far, past_i, past_j);
        if(temp==1)
        {
            path_so_far[i][0] = posi + '0';
            path_so_far[i][1] = posj + '0';
            path_so_far[i][2] = '\0';   
            printf("%s\n", path_so_far[i]);                  
            i++;
            return 1;
        }
    }
    else if (posj + 1 < n && M.values[posi][posj + 1] != 1 && posj + 1 != past_j)
    { 
        temp = traverse(M, n, posi, posj + 1, path_so_far, past_i, past_j);
        if(temp == 1)
        {
            path_so_far[i][0] = posi + '0';
            path_so_far[i][1] = posj + '0';
            path_so_far[i][2] = '\0';     
            printf("%s\n", path_so_far[i]);                   
            i++;
            return 1;
        }
    }
    else
    {
        return 0;
    }                     
}

Maze M has been taken care of i.e. it is initialized in another function, which is not shown here. I am calling traverse with arguments (M, 0, 0, 0, path, 0, 0), but it produces a segmentation fault. I tried adding printf("Hello\n"), as shown in 10th line of my code, to see where the error occurs; it prints "Hello" large number of times, and finally gives segmentation fault. What am I doing wrong?

Answer 1

You seem to be using parameters past_i and past_j to avoid doubling back, but when you recurse, you do not pass the coordinates of the previous position as is required for such a scheme to be effective. For example, it appears that this ...

temp = traverse(M, n, posi - 1, posj, path_so_far, past_i, past_j);

... should be ...

temp = traverse(M, n, posi - 1, posj, path_so_far, posi, posj);

. Without doing this, you can (and do) get stuck going back and forth between two positions (looks like probably between 0,1 and 1,1). There are other problems with your code, such as not correctly recording the path, but the segmentation fault probably results from recursing deeply enough to exhaust your stack space.