递归是几乎一些算法的基础。实际上我认为算法题大致可以分为两类：递归和其他。

实际上计算机能解的唯二问题：

1. 足够简单的问题：比如 x * x, x^0 = 1.
2. 把复杂问题约简到简单问题：比如 x^n = x^(n/2) * x^(n/2)

分治、树、深度优先搜索等等实际上都是递归。

递归的核心思想：明白每个函数能做的事，并相信它们能够完成，千万不要试图跳进细节。

在面试的时候，如果允许写递归（一般是允许的），那一定要写递归解。

解题思路

对一个给定的问题：

1. 确定哪些情形是基础情形，不需要再做递归。比如说：高度为 0 的树，或者 null 根节点，空字符串等。
2. 把问题转化为规模更小的问题。

def fact(a, n):
    if n == 1:
        return a
    return a * fact(a, n-1)  # or n/2 or whatever...

def fact(a, n):
    if n == 1:
        return a
    h = fact(a, n/2)
    return h * h

好多时候，需要编写一个私有的 helper 方法，更改一下函数的签名。对于 Python 或者 JavaScript 的话，直接写一个闭包函数是最好的，也避免了全局变量。

Algorithme by Jeff Erickson

最后推荐一本神书：Algorithms by Jeff Erickson. 这本书全书都是在按照递归的思路讲解。

其它的书和文章的问题在于每个知识点似乎都是孤立的，比如说动态规划就在重点讲解状态转移方程和状态矩阵，而分治就在讲解如何用递归树计算时间复杂度等等。这种讲解方式下，每个知识点之间看不到有什么关联，往往熟悉了这个又忘了那个。实际上这些知识点都是有联系的，所谓的动态规划不过是状态空间搜索的一个巧妙转换，本质上和回溯是一致的，都是递归而已。每个技巧的内核都是一致的，只不过特异化之后有不同的表现，如果你不去抓住内核，通过一个主干把所有知识串联起来，而只看表面现象，那么永远也记不住的。

其他的书就好比盲人摸象，而这本书则是讲解的大象的骨骼结构和肌肉构造。分治和动归这些算法好比是大象的耳朵、尾巴等等部位，可以在外部摸到，而递归则是大象的骨架，虽然摸不到，但是只有画出了骨骼，才能把大象画好。

参考

1. https://stackoverflow.com/questions/25367781/tips-on-solving-binary-tree-binary-search-tree-problems-using-recursion-java
2. https://mp.weixin.qq.com/s/YFe9Z35CE4QWPDmPNitd4w