[回溯法] 0 回溯法介绍-回溯与递归的区别

【回溯法】有至关一类求一组解、或求所有解或求最优解的问题，例如读者熟悉的八皇后问题等，不是根据某种肯定的计算法则，而是利用试探的回溯（Backtrcking）的搜索技术求解web

【实质】它的求解过程实质上是一个先序遍历一棵“状态树”的过程，只是这棵树不是遍历前预先创建的，而是隐含在遍历过程当中，但若是认识到这点，不少问题的递归过程设计也就迎刃而解了。算法

【回溯与递归的区别】svg

1. 递归是一种算法结构，递归会出如今子程序中本身调用本身或间接地本身调用本身。最直接的递归应用就是计算连续数的阶乘，计算规律：n!=(n-1)!*n。
2. 回溯是一种算法思想，能够用递归实现。通俗点讲回溯就是一种试探，相似于穷举，但回溯有“剪枝”功能，好比求和问题。给定7个数字，1 2 3 4 5 6 7求和等于7的组合，从小到大搜索，选择1+2+3+4 =10>7，已经超过了7，以后的5 6 7就不必在继续了，这就是一种搜索过程的优化。若是还有不清楚的能够看一下8皇后问题。

博客：https://blog.csdn.net/u014772862/article/details/51789015优化