How do I convert my depth-first traversal code using recursion to the one using stack?

Question

My data structures and stack operations are defined like this.

typedef struct AdjListNode{
    int dest;
    struct AdjListNode* next;
    int visited;
}AdjListNode;

typedef struct AdjList{
    struct AdjListNode* head;
}AdjList;

typedef struct Graph{
    int V;
    struct AdjList* array;
}Graph;

typedef struct Stack{
    int top;
    char items[MAX];
}Stack;

void Push(struct Stack *s,float val){
    if(s->top == MAX-1){
        printf("Error: Stack overflow.");
        exit(1);
    }else{
        s->items[++(s->top)]=val;
    }
}

float Pop(struct Stack *s){
    if(s->top == -1){
        printf("Error: Stack underflow");
        exit(1);
    }else{
        return(s->items[(s->top)--]);
    }
}

int isFull(struct Stack* s){   
    return s->top == MAX-1;
}

int isEmpty(struct Stack* s){   
    return s->top == -1;  
}

And this function checks if there is a path from p to q

void FindPath_DepthFirstSearch(Graph* graph, int p, int q) {
    AdjListNode* node = graph->array[p].head;
    node->visited = 1;
    // printf("%d\n", p);
    if(p == q){
        printf("Path found!\n");
        exit(1);
    }
    while(node){
        if (!graph->array[node->dest].head->visited)
            FindPath_DepthFirstSearch(graph, node->dest, q);
        node = node->next;
    }
    printf("Path not found!\n");
    exit(1);
}

I'm fairly new to learning data strctures. The code works perfectly when I use recursion but I got stuck for a long time when I tried to implement this using stack. Can anyone help me with this? Thanks!

Answer 1

The basic idea when converting from a recursive definition to a loop-based one is that you store the data that you normally store in local variables on a stack (LIFO) container. Instead of recursing, you push additional elements on the stack. The code then looks like this:

function algorithm(args):
    stack = new FIFO
    # push initial state (e.g. root node for DFS)
    stack.push(args)
    # process all elements
    while stack.has_elements():
        # retrieve topmost element from stack
        e = stack.pop()
        # do something with the current element
        e.frobnicate()
        # push additional elements onto the stack
        if e.condition1():
            stack.push(e.derived1())
        if e.condition2():
            stack.push(e.derived2())