如何用递归的方式解决问题？
什么是递归
Recursion is a method of solving problems that involves breaking a problem down into smaller and smaller subproblems until you get to a small enough problem that it can be solved trivially. Usually recursion involves a function calling itself. While it may not seem like much on the surface, recursion allows us to write elegant solutions to problems that may otherwise be very difficult to program.
这个定义虽然并不权威，但是把它列在这里的原因是，他提到了用递归解决问题的两个特征：
- 将原问题可逐层分解为规模较小的子问题，你会问规模小是怎样界定的呢？就是可以不费太多力气就可以解决的（例如直接返回数组的第一个元素）。
- 函数调用自己，这大概是所有教授算法课程的老师都会提到的特性吧？但是请记住，这只是算法的形式表现。
一般的教科书在提到这部分内容的时候都要从递归程序调用栈的流程开始，怎样压栈怎样出栈。看完以后感觉写书的作者好牛逼，但是碰到问题的时候又是一脸懵逼，思绪全无。
所以为了避免上面这种无效的学习方式，我们直接来分析该怎样用递归的思想来写程序。
递归程序的3要素
- 递归程序必须要有一个基本case（而且这个case还比较好解决）
- 递归程序的状态转移必须趋向这个基本case
- 递归程序必须递归地调用它自己（像是一个废话）
先不忙着进行后续的内容，我们来分析下上面这三条分别都在从什么角度来叙述。
首先一个递归程序必须要有个结束的终止条件，就是可解决的子问题。
其次是复杂问题是可以向可解决的子问题转化的。
最后这个转化的过程其实本质还是使用自己方式来解决。
用递归解决的典型问题
判断一棵二叉树是否是二叉搜索树
由于是之前已经在树的分类的话题内分析讨论过了，所以具体的解题方法请移步到下面链接👇
关于树的一些话题
注意这里的递归解法并不是直接粗暴的将原问题套用在左右子树，因为你会发现判断是不是BST的标准还并不明确，因此考虑细化这个判断条件，换句话是再次考虑basic case，什么是典型的basic case呢？ 根结点，加上左右孩子节点的结构是最容易分析的。再考虑判断条件，根结点大于所有左子树节点，小于所有右子树节点（当然，如果子树只有一个节点是比较特殊的，同时也是好判断的basic case），再考虑复杂树能否向这种basic case转化呢？ 当然可以，一层一层地向左右孩子节点判断就可以。因此第一、二、三要素都满足。
TBD ……
