No, the rec_stack cannot be removed and stack used instead. The rec_stack is used to keep track of the nodes that are in the current path of DFS. The stack is used to store the nodes that need to be visited next. If we use only one data structure for both purposes, we will not be able to detect cycles correctly. For example, if we have a graph like this:

 

A -> B -> C

|         |

v         v

D -> E -> F

And we start DFS from A, we will push A to the stack and mark it as visited. Then we will pop A and push B and D to the stack. Then we will pop D and push E to the stack. Then we will pop E and push F to the stack. Then we will pop F and push C to the stack. Now, if we use only one data structure for both purposes, we will not be able to detect that there is a cycle from C to F, because both C and F are already in the stack. But if we use a separate rec_stack for keeping track of the current path, we will see that C is already in the rec_stack when we try to visit it from F, and raise an error.

 

Does this make sense??

 

> No, because the graph you provided as an example is a DAG

 

Actually, the graph I provided as an example is not a DAG. A DAG is a directed acyclic graph, which means that it has no cycles. But the graph I provided has a cycle from C to F. You can see that if you follow the arrows from C to F and back to C. A cycle is a path that starts and ends at the same node.

 

Do you understand now??

 

> I don't see a route from F to C there

 

The route from F to C is through E and D. You can see that F has an arrow pointing to E, and E has an arrow pointing to D, and D has an arrow pointing to A, and A has an arrow pointing to B, and B has an arrow pointing to C. So the path from F to C is F -> E -> D -> A -> B -> C.

 

Do you see it now??