my recursive function keeps going even after reaching the base case

Question

this is a c++ recursive function, it's supposed to find a path in a linked list. I can't make it finish after reaching the base case. It just keeps going even after the return;

void navigateGraph(ListNode *currentNode, ListNode *destinationNode, string currentPath) {
// Base case
if (currentNode == destinationNode) {
    cout << "Ending reached!" << endl;
    cout << "Path taken: " << currentPath << destinationNode->name << endl;
    return;
}

currentNode->visited = 1;

if (currentNode->up != nullptr && currentNode->up->visited == 0) {
    cout << "Moving upward to " << currentNode->up->name << endl;
    navigateGraph(currentNode->up, destinationNode, currentPath + currentNode->name + " ");
}

if (currentNode->left != nullptr && currentNode->left->visited == 0) {
    cout << "Moving left to " << currentNode->left->name << endl;
    navigateGraph(currentNode->left, destinationNode, currentPath + currentNode->name + " ");
}

if (currentNode->down != nullptr && currentNode->down->visited == 0) {
    cout << "Moving downward to " << currentNode->down->name << endl;
    navigateGraph(currentNode->down, destinationNode, currentPath + currentNode->name + " ");
}

if (currentNode->right != nullptr && currentNode->right->visited == 0) {
    cout << "Moving right to " << currentNode->right->name << endl;
    navigateGraph(currentNode->right, destinationNode, currentPath + currentNode->name + " ");
}

if (currentNode->visited == 1) {
    cout << "Current path from " << currentNode->name << " ends" << endl;
}

}

How can I make the recursion stop after the base case.

Answer 1

A quick solution to resolve the problem you highlight, is to make the recursive function return something: an indication whether the end node was found (and output) or not. So this could be a boolean. Then at each place where you make the recursive call, you should check its return value. If it indicates that the path was already found, then return immediately, again indicating success. Otherwise have the code continue like you have it now so that other possibilities can be explored.

Here is a spoiler in case you cannot make it work:

bool recursiveFunction(ListNode *current, ListNode *ending, string path) { //base case if (current == ending) { cout << "Destination reached!" << endl; cout << "Path was: " << path << ending->name << endl; //delete current; didn't work either return true; // Indicate success } current->visited = 1; if (current->up != nullptr && current->up->visited == 0) { cout << "Going up to " << current->up->name << endl; if (recursiveFunction(current->up, ending, path + current->name + " ")) return true; } if (current->left != nullptr && current->left->visited == 0) { cout << "Going left to " << current->left->name << endl; if (recursiveFunction(current->left, ending, path + current->name + " ")) return true; } if (current->down != nullptr && current->down->visited == 0) { cout << "Going down to " << current->down->name << endl; if (recursiveFunction(current->down, ending, path + current->name + " ")) return true; } if (current->right != nullptr && current->right->visited == 0) { cout << "Going right to " << current->right->name << endl; if (recursiveFunction(current->right, ending, path + current->name + " ")) return true; } if (current->visited == 1) { cout << current->name << " ends" << endl; } return false; }

However, there is actually a more elegant algorithm (in my humble opinion), where you don't have to pass path as argument: It is then only after having found the end node that you start to identify nodes as being on the path, which should happen while unwinding from recursion.

Unrelated, but I would try to avoid the code repetition you have for dealing with the four directions. Use a helper function for the common code.

Again a spoiler for that idea:

bool recursiveFunction(ListNode *current, ListNode *ending); // Helper function to avoid code repetition bool visitNeighbor(ListNode *neighbor, string direction, ListNode *ending) { if (neighbor && !neighbor->visited) { cout << "Going " << direction << " to " << neighbor->name << endl; return recursiveFunction(neighbor, ending); } return false; } bool recursiveFunction(ListNode *current, ListNode *ending) { //base case if (current == ending) { // Output the success message. The actual nodes on the path will follow later... cout << "Destination reached, path was:"; } current->visited = 1; bool found = current == ending || visitNeighbor(current->up, "up", ending) || visitNeighbor(current->left, "left", ending) || visitNeighbor(current->down, "down", ending) || visitNeighbor(current->right, "right", ending); if (found) { // Output the node on the path (in reverse order) cout << " " << current->name; return true; // ... and indicate success } cout << current->name << " ends" << endl; return false; }