回溯和递归的区别？

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

这个问题就像问一辆车和一辆德洛尔有什么区别。

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

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

可能有点难以理解，我在这里附上一些文本：

“从概念上来说，你从一棵树的根开始；这棵树可能有一些好的叶子和一些坏的叶子，尽管叶子可能都是好的或坏的。你想找到一片好的叶子。在每个节点上，从根开始，你选择它的一个孩子，直到你找到一片叶子。

假设你碰到一片坏树叶。您可以通过撤消最近的选择并尝试该选项集中的下一个选项来返回以继续搜索好的叶子。如果您的选项用完了，请撤消使您在这里的选择，并在该节点尝试另一个选择。如果你最终在根部别无选择，就找不到好叶子了。“

这需要一个例子：

您的代码段只是递归，因为如果结果不符合您的目标，您将永远不会返回。