# Understanding recursive solution of some algorithm

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?

• Which parameter do you consider the extra one? May 22, 2016 at 18:50
• Recursive algorithms always contain three things: 1) The terminating condition, i.e. the condition that stops the algorithm from recursing further, 2) The code that recurses, i.e. the code that calls the function again, and 3) The code that performs the required action in this recursion. May 22, 2016 at 18:50
• Don't know which parameter is extra, normally the dfs starts with the call like this `dfs(g, s)` where `g` is the graph instance and `s` is the start vertex. But now I see one extra vertex in the parameter of dfs. May 22, 2016 at 18:54
• You have to fire it up in a debugger, and observe the variables change each time a recursion occurs. Given that information, you deduce what the algorithm is doing. You don't need a Princeton degree to do that. Don't try to understand the algorithm first before you examine it; examine the algorithm first and gain understanding from the examining. May 22, 2016 at 19:10
• Unfortunately, you're always going to encounter code that is insufficiently documented and sometimes poorly written, code that you're going to have to make heads or tails of. Welcome to the world of programming. May 22, 2016 at 19:13

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.
• @CodeYogi: how I figured that out? First I looked at the link to the original code, read the comments, looked what purpose the algorithm had and how the `dfs` function gets called initially. Moreover, I mentally "abstracted away" the "return cycle result" parts, because they are not essential for the core algo. Finally, I just read the code, but I have developed and read similar kind of graph algorithms for different purposes lots of times in the past, so I guess that gives me some advantage here. May 23, 2016 at 6:12