回溯和递归的区别

一、概念

递归：程序调用自身的编程技巧称为递归(recursion )。 回溯：回溯算法实际上一个类似枚举的搜索尝试过程，主要是在搜索尝试过程中寻找问题的解，当发现已不满足求解条件时，就回溯返回，尝试别的路径。

二、回溯和递归的区别

递归是一种算法结构，递归会出现在子程序中形式上表现为直接或间接的自己调用自己；而回溯是一种算法思想，它是用递归实现的，回溯的过程类似于穷举法，但回溯有“剪枝”功能，即自我判断过程。

举个通俗的例子就是： 我们在路上走着，前面是一个多岔路口，因为我们并不知道应该走哪条路，所以我们需要尝试。尝试的过程就是一个函数。 如果我们选择了一个方向，后来发现又有一个多岔路口，这时候又需要进行一次选择。所以我们需要在上一次尝试结果的基础上，再做一次尝试，即在函数内部再调用一次函数，这就是递归的过程。 这样重复了若干次之后，发现这次选择的这条路走不通，这时候我们知道我们上一个路口选错了，所以我们要回到上一个路口重新选择其他路，这就是回溯的思想。

回溯法，也称为“试探法”

我们观察到，在很多情况下是没有必要再往下试探了的，因为在排完之前，就已经不满足上述的判断条件了，这个时候，我们可以停止向下搜索，并进行下一次的搜索，这种思路被称为回溯思想，这样可以大大的减少了可能的情况。

使用剪枝函数的深度优先生成状态空间树中结点的求解方法，称为回溯法（backtracking）； 广度优先生成结点，并使用剪枝函数的方法，称为分支限界法（branch-and-bound） 解决一个回溯问题，实际上就是一个决策树的遍历过程。

总结 回溯法是在问题的解空间树中，按深度优先策略，从根节点出发搜索解空间树。算法搜索至解空间树的任意一点时，先判断该结点是否包含问题的解。如果肯定不包含，则跳过对以该结点为根子树的搜索，逐层向其祖先结点 回溯，否则，进入该子树，继续按深度优先策略搜索。回溯法实际上是状态空间搜索中，深度优先搜索的一种改进，是更实用的一种搜索求解方法。

求问题所有解：要回溯到根，且根节点的所有子树均已被搜索遍才结束。 求问题某一解：只要搜索到一个解即可结束搜索。

由上述的问题，我们可以总结出回溯递归法的一般模板，模板如下：

—— 本文来自火龙信奥（义乌睿码科技）：义乌青少年信息学奥赛与编程教育平台，专注 CSP-J/S、NOIP、GESP 竞赛培训，线上线下融合教学，助力编程升学。网址：hlcoding.com