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?

• Robert Harvey: Which parameter do you consider the extra one?
• Robert Harvey: 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.
• CodeYogi: 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.
• Robert Harvey: 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.
• Robert Harvey: 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.

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.

• CodeYogi: Ya, I use VIM so debugger option is out for sure. Using pencil and paper seems best for me since I can use that technique anywhere and anytime :). Its good to know that there is no magic to understand code like these and even expert programmers too get caught in such code this gives some confidence to me.
• CodeYogi: Just asking, how did you figure that out? practice, paper or debugger? :)
• CodeYogi: One more thing, this may be off topic but I am new to graph algorithm and don't have that much knowledge of advance maths but I am trying hard to learn from good resources but in that case I am stuck for several hours trying to understand algorithms by looking at just code. So, to keep going I have thought to write at least one graph algorithm a day even I don't get it properly(some cheating by looking at the solution), can I get better one day by following this strategy augmented by the suggestion of using pencil and paper while studying and tracing the code execution?
• Doc Brown: @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.