Common mistakes with recursion
Comments and questions to John Rowe.
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;
}
|
