回溯和递归之间的区别? [英] Difference between backtracking and recursion?

问题描述

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

What is the difference between backtracking and recursion? How is this program working?

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 .

That question is like asking what's the difference between a car and a DeLorean.

在递归中，函数会自行调用，直到达到基本情况为止.

In recursion function calls itself until reaches a base case.

在回溯中，您使用递归来探究所有可能性，直到获得解决问题的最佳结果为止.

In backtracking you use recursion in order to explore all the possibilities until you get the best result for the problem.

可能有点难以理解，我附上

Can be a bit hard to understand, I attach some text from here:

从概念上讲，您从树的根部开始；树可能有一些好叶子和一些坏叶子，尽管可能叶子全好或全坏.您想得到一棵好叶子.从根开始，在每个节点上，选择要移动的子节点之一，并一直保持到到达叶子为止.

"Conceptually, you start at the root of a tree; the tree probably has some good leaves and some bad leaves, though it may be that the leaves are all good or all bad. You want to get to a good leaf. At each node, beginning with the root, you choose one of its children to move to, and you keep this up until you get to a leaf.

假设您到了一片烂叶子.您可以通过撤消最近的选择并尝试使用该选项集中的下一个选项来回溯以继续寻找好叶子.如果您用完所有选项，请撤消使您进入此处的选择，然后在该节点尝试另一个选择.如果您最后没有任何选择，那么根本找不到好的叶子."

Suppose you get to a bad leaf. You can backtrack to continue the search for a good leaf by revoking your most recent choice, and trying out the next option in that set of options. If you run out of options, revoke the choice that got you here, and try another choice at that node. If you end up at the root with no options left, there are no good leaves to be found."

这需要一个例子:

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

Your piece of code is simply recursion, as you never get back if the result doesn't fit your goal.

这篇关于回溯和递归之间的区别?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！