C++递归导航函数触发基准条件后仍无法终止的解决方法

我写了一个C++递归函数navigateGraph用于在链表结构中查找路径，但触发基准条件（当前节点等于目标节点）执行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;
}
}

问题根源 #

原函数是void类型，找到目标后执行的return只能退出当前这一层递归，但上层递归并不会知道已经找到目标，会继续执行后续的if分支（比如查完up方向后，还会去检查left、down、right），所以递归不会立刻终止。

修改方案 #

把函数改成带返回值的类型，用返回值告诉上层递归是否已经找到目标，一旦确认找到，就立刻向上返回，不再执行后续分支：

• 将函数返回值从void改为bool，true表示找到目标，false表示未找到
• 基准条件触发时，输出信息后返回true
• 调用递归分支时，检查返回值，如果返回true，直接向上返回true，跳过后续分支
• 所有分支都遍历完仍未找到目标时，返回false

修改后的完整代码 #

bool navigateGraph(ListNode *currentNode, ListNode *destinationNode, string currentPath) {
    // Base case
    if (currentNode == destinationNode) {
        cout << "Ending reached!" << endl;
        cout << "Path taken: " << currentPath << destinationNode->name << endl;
        return true; // 返回true表示找到目标
    }

    currentNode->visited = 1;

    // 检查up方向
    if (currentNode->up != nullptr && currentNode->up->visited == 0) {
        cout << "Moving upward to " << currentNode->up->name << endl;
        if (navigateGraph(currentNode->up, destinationNode, currentPath + currentNode->name + " ")) {
            return true; // 找到目标，立刻返回
        }
    }

    // 检查left方向
    if (currentNode->left != nullptr && currentNode->left->visited == 0) {
        cout << "Moving left to " << currentNode->left->name << endl;
        if (navigateGraph(currentNode->left, destinationNode, currentPath + currentNode->name + " ")) {
            return true; // 找到目标，立刻返回
        }
    }

    // 检查down方向
    if (currentNode->down != nullptr && currentNode->down->visited == 0) {
        cout << "Moving downward to " << currentNode->down->name << endl;
        if (navigateGraph(currentNode->down, destinationNode, currentPath + currentNode->name + " ")) {
            return true; // 找到目标，立刻返回
        }
    }

    // 检查right方向
    if (currentNode->right != nullptr && currentNode->right->visited == 0) {
        cout << "Moving right to " << currentNode->right->name << endl;
        if (navigateGraph(currentNode->right, destinationNode, currentPath + currentNode->name + " ")) {
            return true; // 找到目标，立刻返回
        }
    }

    if (currentNode->visited == 1) {
        cout << "Current path from " << currentNode->name << " ends" << endl;
    }
    return false; // 该路径未找到目标
}

内容的提问来源于stack exchange，提问作者Avi Moreno