回溯和递归之间的区别？

Question

回溯和递归有什么区别？这个程序如何运作？

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.
    }

Answer 1

这个问题就像问汽车和DeLorean之间的区别。

在递归函数中调用自身直到达到基本情况。

在回溯中，您使用递归来探索所有可能性，直到您获得问题的最佳结果。

可能有点难以理解，我附上一些来自here的文字：

“从概念上讲，你从一棵树的根开始;树可能有一些好叶子和一些坏叶子，但可能是叶子都是好的或者都是坏的。你想得到一片好叶子。在每个节点，从根开始，你选择其中一个孩子移动到，你保持这个直到你到达一片叶子。

假设你遇到了坏叶子。你可以通过撤销最近的选择来回溯继续搜索好叶子，然后在该组选项中尝试下一个选项。如果您的选项用完了，请撤消此处的选择，并在该节点尝试其他选择。如果你最终没有留下任何选项，那么就没有好叶子了。“

这需要一个例子：

你的代码就是简单的递归，因为如果结果不符合你的目标，你永远不会回来。

Answer 2

递归描述了你所使用的相同函数的调用。递归函数的典型例子是阶乘，即类似

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)）

回溯是一种尝试找到给定参数的解决方案的算法。它构建了解决方案的候选者，并放弃了那些不能满足条件的候选者。要解决的任务的典型示例是Eight Queens Puzzle。回溯也常用于神经元网络。

您描述的程序使用递归。与阶乘函数类似，它将参数减1，如果n <1则结束（因为它将打印ar而不是其余部分）。

Answer 3

在我的理解中，回溯是一种算法，就像所有其他算法一样，如BFS和DFS，但递归和迭代都是方法，它们处于比算法更高的层次，例如，为了实现DFS，你可以使用递归，这是非常直观的，但您也可以使用堆栈迭代，或者您也可以认为递归和迭代只是支持您的算法的方法。

Answer 4

递归 - 没有放弃任何值;

回溯 - 放弃一些候选解决方案;

还要注意回溯在函数体中会多次调用自身，而递归通常不是这样