回溯和递归有什么区别?这个程序是如何运作的?
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 https://en.wikipedia.org/wiki/DMC_DeLorean.
在递归函数中调用自身直到达到基本情况。
在回溯中,您使用递归来探索所有可能性,直到获得问题的最佳结果。
可能有点难以理解,我附上一些文字here https://www.cis.upenn.edu/~matuszek/cit594-2012/Pages/backtracking.html:
“从概念上讲,你从一棵树的根部开始;这棵树可能有一些好的叶子和一些坏的叶子,尽管这些叶子可能都是好的或都是坏的。你想要得到一个好的叶子。在每个节点,从根开始,选择要移动到的子节点之一,并一直这样做,直到到达叶子。
假设你遇到了一片坏叶子。您可以通过撤销最近的选择并尝试该组选项中的下一个选项来回溯以继续搜索好叶子。如果您没有选择,请撤销使您到达此处的选择,并在该节点尝试另一个选择。如果你最终没有选择,就找不到好的叶子。”
这需要一个例子:
您的代码只是递归,因为如果结果不符合您的目标,您将永远无法返回。
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)