这是一个C++递归函数，它应该在链表中找到路径。 说明是：该函数的基本情况是它所在的当前节点是否等于用户输入的结束节点。如果是，您将输出该节点的名称并终止当前节点（此基本情况为我们提供了反向路径，这就是我们想要的）。
我的教授告诉我“有趣的是，即使你到达终点，它也会继续。它返回到前一个节点，并继续执行程序。返回并没有真正结束程序，因为仍然有节点打开”，但我还是不知道如何让它发挥作用。
这是我的输出（最后 4 行不应该出现）：
Enter starting point in CAPS: E
Enter ending point in CAPS: C
Going up to B
Going left to A
Going down to D
D ends
A ends
B ends
Going down to H
Going left to G
G ends
H ends
Going right to F
Going up to C
Destination reached!
Path was: E F C
Going down to I
I ends
F ends
E ends
Presione una tecla para continuar . . .
这是函数：
void 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;
}
current->visited = 1;
if (current->up != nullptr && current->up->visited == 0) {
cout << "Going up to " << current->up->name << endl;
recursiveFunction(current->up, ending, path + current->name + " ");
}
if (current->left != nullptr && current->left->visited == 0) {
cout << "Going left to " << current->left->name << endl;
recursiveFunction(current->left, ending, path + current->name + " ");
}
if (current->down != nullptr && current->down->visited == 0) {
cout << "Going down to " << current->down->name << endl;
recursiveFunction(current->down, ending, path + current->name + " ");
}
if (current->right != nullptr && current->right->visited == 0) {
cout << "Going right to " << current->right->name << endl;
recursiveFunction(current->right, ending, path + current->name + " ");
}
if (current->visited == 1) {
cout << current->name << " ends" << endl;
}
}
我尝试使用删除当前；返回之前；但不起作用，我还尝试对 (current->visited == 1) 的每个方向执行 else if 操作，但这也不起作用。尝试执行系统暂停，然后在返回之前退出，但这也不起作用。据我所知，这就是我所做的。
解决您强调的问题的快速解决方案是使递归函数return某物：指示是否找到（并输出）结束节点。所以这可能是一个布尔值。然后，在进行递归调用的每个地方，您应该检查其返回值。如果表明路径已经找到，则立即返回，再次表明成功。否则让代码像现在一样继续，以便探索其他可能性。
看起来是这样的：
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）并以非相反的顺序输出路径！这些说明暗示了一种算法，只有在检测到结束节点后才开始构建路径。
path作为参数：当您找到结束节点时，没有什么可知道的。只有
after才发现您应该将节点识别为路径上的节点，这应该在从递归展开时发生。 不相关，但我会尽力避免处理四个方向的代码重复。对公共代码使用辅助函数。
看起来是这样的：
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;
}
图表的输出现在是：
Going up to B
Going left to A
Going down to D
D ends
A ends
B ends
Going down to H
Going left to G
G ends
H ends
Going right to F
Going up to C
Destination reached, path was: C F E