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
Back to top