这是一个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;
}字符串
}
我怎样才能使递归在基本情况之后停止。
1条答案
按热度按时间fae0ux8s1#
解决你强调的问题的一个快速解决方案是让递归函数 * 返回 * 一些东西：是否找到结束节点的指示（和输出）或不。所以这可能是一个布尔值。然后在你进行递归调用的每个地方，你应该检查它的返回值。如果它表明路径已经找到，那么立即返回，再次表示成功。否则让代码像现在一样继续，以便可以探索其他可能性。
这里是一个扰流板的情况下，你不能使它工作：
第一个月
然而，实际上有一个更优雅的算法（以我的拙见），在那里你不必传递
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; }个