Skip to content
Physics and Astronomy
Home Our Teaching Resources C programming Common mistakes
Back to top
On this page
Contents

Common mistakes with recursion

Problems with the test

As mentioned in the lecture, nodes that can contain loops must mark the nodes as visited and check they are not revisiting already visited nodes. The correct order to do this is Check, Mark, Recurse:

Correct order: Check, Mark, Recurse

Check, Mark, Recurse
void myfun(some_args) {
  if (node_has_been_visited)
    return;                   // Check 

  mark_this_node_as_visited;  // Mark 

  // Do some stuff here...
  myfun(some_other_args);     // Recurse 
}

Incorrect order: Mark, Check, Recurse

If we mark the node as visited before checking then of course the "return" check will always be true and the code will never execute:

Wrong: Mark, Check, Recurse
void myfun(some_args) {
  mark_this_node_as_visited;  // Mark 

  if (node_has_been_visited)
    return;                   // Check - is always true! 

  // Do some stuff here...
  myfun(some_other_args);     // Recurse 
}

Incorrect order: Check, Recurse, Mark

Conversely, if we mark the node as visited after the recursive function call then of the "return" check will always be false and the code will recurse forever:

Wrong: Check, Recurse, Mark
void myfun(some_args) {
  if (node_has_been_visited)
    return;                   // Check - is always false! 

  // Do some stuff here...
  myfun(some_other_args);     // Recurse 

  mark_this_node_as_visited;  // Mark 
}

Incorrect order: Recurse first!

Wrong: Recurse first
void myfun(some_args) {
  myfun(some_other_args);     // Always Recurse!

  // It really doesn't matter what happens here...

  return;
}
                                                                                                                                                                                                                                                                       

Validate   Link-check © Copyright & disclaimer Privacy & cookies Share
Back to top