提问人：Avi Moreno 提问时间：11/16/2023 最后编辑：Avi Moreno 更新时间：11/18/2023 访问量：72
我的递归函数即使在达到基本情况后也会继续运行
my recursive function keeps going even after reaching the base case
问：
这是一个 C++ 递归函数，它应该在链表中查找路径。到达基本情况后我无法完成。即使在返回后，它也会继续前进;
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;
}
}
我怎样才能使递归在基本情况之后停止。
答：
0赞
trincot
11/17/2023
#1
解决您突出显示的问题的一个快速解决方案是使递归函数返回一些东西：指示是否找到（并输出）结束节点。所以这可能是一个布尔值。然后，在进行递归调用的每个位置，都应检查其返回值。如果表示已找到路径，则立即返回，再次表示成功。否则，让代码像现在一样继续，以便可以探索其他可能性。
这里有一个剧透，以防你无法让它工作：
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; }
然而，实际上有一种更优雅的算法（以我的拙见），你不必作为参数传递：只有在找到结束节点之后，你才开始识别节点在路径上，这应该在从递归中解脱出来时发生。path
无关紧要，但我会尽量避免您在处理四个方向时重复代码。对通用代码使用帮助程序函数。
再次剧透这个想法：
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; }
评论
0赞
Avi Moreno
11/18/2023
您的解决方案工作正常，非常感谢。在这里，当你提到**这实际上是一个更优雅的算法（以我的拙见），[...] ** 我的教授告诉我他想要这种方法，但我不断收到“（名称）结束”消息，我无法让它只显示程序末尾的节点名称。如果你能帮助我，我将不胜感激，如果没有，我完全理解。再次，非常感谢。:)
0赞
trincot
11/18/2023
当然，我想帮忙，但我不明白你说的“我不断得到......”是什么意思。和“我无法让它在程序结束时只显示节点的名称”。您的意思是，在递归执行期间发现节点时，您不需要输出节点，而只需要在递归函数完成后输出它们？“正在下降”消息和“到达目的地”呢？等。你需要它们吗？
0赞
trincot
11/18/2023
好的，我在第二个代码片段中添加了类似“H ends”的消息。是你需要的吗？
0赞
Avi Moreno
11/18/2023
是的！非常感谢，你有现金应用程序吗？
1赞
Avi Moreno
11/18/2023
完美，谢谢！
评论
else ififcurrent->visited = 1;if (current->visited == 1)truetrue