递推与递归

· · 个人记录

最初我对递归和递推的认识只停留在实现形式上，即认为只用循环的求解就是递推，自己调用自己的就是递归。没有认识到它们本质的相似与不同，它们作为两种相似又不同的算法，却被那时的我简单地理解为解题形式。

而事实上，递推和递归都是一种将大问题变小的求解方式。而区别在于，递推是在已知“问题边界”的情况下，即我们可以从“问题边界”（也可以是某个小问题）开始，然后向后推算，直到整个问题求解。
递归是不断缩小问题空间，到达“问题边界”后再“回溯”。我们可能从问题边界得到答案或者子问题的答案.

总结：递归和递推是方式，或者说是“手段”，是我们用来分解和求解问题的。也可以说是在“搜索”中遍历状态空间的基本方法。（这里“搜索”指一种问题.）

这里顺便讲一下分治思想（最近在研究）。
分治就是一种将大问题不断分解成相似的子问题的思想，对于结构整齐严密的数学问题特别适用，可以不断“分治”成一个个小问题求解。

分治思想可以使用递归来实现。为什么呢？因为递归就是在只知道原问题的情况下，“不断缩小问题空间”求解的手段。而我们可以用递推来分治。
（区分，递推需要知道从问题边界推到原问题的规则，并且尽量不重不漏。递归因为本身就存在“回溯”，所以在加清除痕迹的操作后，重复也一般不影响正确性。递归需要枚举所有情况,甚至重复枚举。这也是递归相对较慢的原因了。）