回溯和递归之间的区别？

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之间的区别.

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

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

可能有点难以理解,我从这里附上一些文字:

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

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

这需要一个例子:

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

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

递归 - 不放弃任何值；

回溯——放弃一些候选解决方案；

另请注意，回溯将在函数体内多次调用自身，而递归通常情况下并非如此

Answer 4

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