回溯和递归有什么区别？这个程序是如何工作的？
void generate_all(int n)
{
if(n<1) printf("%s\n", ar);
else{
ar[n-1]='0'; //fix (n)th bit as '0'
generate_all(n-1); //generate all combinations for other n-1 positions.
ar[n-1]='1'; //fix (n)th bit as '1'
generate_all(n-1); //generate all combinations for other n-1 positions.
}
}
那个问题就像问汽车和DeLorean之间的区别。
在递归中，函数调用自身直到达到基本情况。
在回溯中，您使用递归以便探索所有可能性，直到获得问题的最佳结果。
有点难理解，我附上了这里的一些文本:
“概念上，你从树的根开始;树可能有一些好叶子和一些坏叶子，尽管可能是所有叶子都是好的或所有叶子都是坏的。您想要到达一个好的叶子。在每个节点上，从根开始，您选择其中一个子节点移动，并继续保持这种情况，直到到达一个叶子。
假设你到达了一个坏的叶子。您可以通过撤销最近的选择并尝试在该选项集中尝试下一个选项来回溯以继续搜索好叶子。如果选项用完，则撤销使您到达此处的选择，并在该节点尝试另一个选择。如果您在没有剩余选项的情况下最终到达根，则无法找到好的叶子。
这需要一个例子:
您的代码片段只是递归，因为如果结果不符合目标，您永远不会返回。
ar[n-1]='0';后会回退，并将其恢复为ar[n-1]='1';，然后再次前进，选择一个新的选项。至于你的图片，在树中可能有多个好的叶子，特别是每个叶子都可以是好的。回溯通过枚举和测试所有节点/叶子来列举出所有好的叶子，如果每个节点/叶子都是好的，则最终将报告/收集/生成所有叶子。这正是OP代码的情况。 - Will Ness递归是指调用当前函数本身的行为。典型的例子是阶乘函数，即类似于：
int fact(int n) {
int result;
if(n==1) return 1;
result = fact(n-1) * n;
return result;
}
您在这里看到的是事实自身调用。这就是所谓的递归。您总是需要一个使递归停止的条件。这里是if(n==1)，结合每次调用时n都会减少（fact(n-1)）的事实。
回溯是一种算法，它尝试在给定参数的情况下找到解决方案。它为解决方案构建候选项，并放弃无法满足条件的候选项。典型的解决任务的例子是八皇后问题。回溯也常用于神经网络中。
您描述的程序使用递归。类似于阶乘函数，它将参数减少1，并在n<1时结束（因为那样它将打印ar而不是执行其余部分）。
ar[n-1]更改为'1'，再次使用相同的(n-1)值前进。 - Will Ness递归 - 不放弃任何值；
回溯 - 放弃一些解决方案候选；
同时注意，回溯在函数体内可能会多次调用自身，而递归通常不会如此。
在我看来，回溯是一种算法，就像其他算法（如BFS和DFS）一样，但递归和迭代都是方法，它们处于比算法更高的层次。例如，要实现DFS，你可以使用相当直观的递归，也可以使用带有堆栈的迭代，或者你也可以认为递归和迭代只是支持算法的方法。
递归 就像一种自下而上的过程。你可以通过使用子问题的结果来解决问题。
例如，使用递归反转链表只需要在已反转的子列表上添加头节点。https://leetcode.com/problems/reverse-linked-list/discuss/386764/Java-recursive
回溯 仍然像一种自上而下的过程。有时候，你不能仅通过使用子问题的结果来解决问题，你需要传递你已经得到的信息给子问题。这个问题的答案将在最底层计算，然后这些答案将带着你沿途获取的信息返回到问题中。
递归 -
回溯 -
#define NLEVEL 20
int ia[NLEVEL];
int na[NLEVEL];
int iLevel = 0;
int choose(int n){
if (ilevel >= ns){ na[ns]=n; ia[ns]=0; ns++; }
return ia[ilevel++];
}
void step(){
while (ns > 0){
if (++ia[ns-1] >= na[ns-1]) ns--;
else break;
}
}
bool search(int iLevel){
iLevel++;
switch(choose(2)){
break; case 0:;
// see if 0 is a win. if not, fail by returning false
break; case 1:
// choose move 1 and recur
return search(iLevel);
}
return true;
}
// this is the "top level" routine
void running(){
ns = 0;
// repeat for stabs into choice tree until success
do {
bool bSuccess = search(0);
if (bSuccess){
// Yay!
break;
}
step(); // this advances the stack of choices
} while(ns > 0); // stop when success or there are no more choices
}
我使用这段代码来构建一个自制的定理证明器，取代了search函数。
ar甚至没有被定义。 - Asherah