Understanding recursive solution of some algorithm

Question

Most of the time we need to understand someone else' code for example I am studying Graph Algorithms from Sedgewick's online resources, the particular code example is taken from cycle detection algorithm here:

 private void dfs(Graph G, int u, int v) {
        marked[v] = true;
        for (int w : G.adj(v)) {

            // short circuit if cycle already found
            if (cycle != null) return;

            if (!marked[w]) {
                edgeTo[w] = v;
                dfs(G, v, w);
            }

            // check for cycle (but disregard reverse of edge leading to v)
            else if (w != u) {
                cycle = new Stack<Integer>();
                for (int x = v; x != w; x = edgeTo[x]) {
                    cycle.push(x);
                }
                cycle.push(w);
                cycle.push(v);
            }
        }
    }

Although I know the basic gist of the algorithm(finding the back edge) and I can tell from looking at the code that its trying to store the generated cycle as well but I am not able to trace how would the algorithm would execute and why the author has takes one extra parameter in the dfs code. Generally how should I proceed to understand such recursive algorithms?

Answer 1

This dfs algorithm looks for a cycle in the graph G starting at v. The "extra parameter" u is the "previous" or "parent" node of v in the search tree, it is passed here because it enables the algorithm to avoid to take a sequence like "u - v - u" for a cycle.

Understanding code is sometimes not easy, it takes practice, especially recursive code. There are several techniques, like adding comments, "scratch refactoring", running the code in a debugger (as suggested by Robert Harvey), add logging statements to the code and run it, or drawing an example on a piece of paper and "execute it" by using a pencil. Only you can find out which technique works best for you and your specific case.