前言
? ? ? ? 最近看到好多小伙伴都在抱怨不会构造递归函数，尤其是进入了树这一章之后，变得更加蒙圈，我特意前来分享一下我关于递归函数的一些理解。如有补充、纠错，欢迎讨论。
正文
? ? ? ? 首先要知道一点，任何一个算法，你在构建之前必须要自己有能力跟着这个算法走一遍，比如我给你一组符号aaaaaaaaaaabccd，让你去构造一个哈夫曼树，你自己用纸算不出来，你就不可能写得出递归，所以要先去理解这个算法的过程才能落实到算法的实现。
? ? ? ? 在确定这个大前提的情况下，我们第一步要进行问题的分割，递归就是将一个大问题分割成无数的小问题去求解，举个简单的例子：?这样一个算式，我们可以清楚地发现，去掉2+和大根号后，剩下部分和整体是相同的，这其实就是一个分割的过程。而求前n个数的和，1+2+3+...+n，我们也可以发现，去掉+n之后，其余的数是求前n-1个数的和。递归问题的分割，无关乎分割部分的顺序，我可以从前往后割，也可以从后往前割，没有关系。
? ? ? ? 问题的分割结束之后，我们就可以进行递归输入输出变量的确定，这一步很重要。输入和输出要保持高度的一致性，那么以1+2+3+...+n为例，这个示例的特征是n，n是int型的变量，所以输入是int，那么我们分割的小问题是前n-1项的和，返回值也是int。复杂一点是示例大家可以看看二叉树实现表达式求值??????。
? ? ? ? ?在确定了输入和输出的类型之后，我们就可以对函数的主体进行一个确认。函数的主体分为条件部分（包括终止条件）和递归部分。我先前讲到，递归问题的分割，无关乎分割部分的顺序。那么怎么实现这个顺序，就需要合理分配计算内容和递归内容。
? ? ? ? 有人跟我说：“啊，递归不是从底到顶的吗？你这个怎么先操作的顶部呀。”
? ? ? ? 打个比方，构建二叉树的时候。
void CreateTree(TNode *T,char s[],int i){
if(s[i]=='0'){
T=NULL;
return;//这个return可以去掉，但是后面的所有语句要括在else里面。这么使用是为了提醒一下大家可以用return的方式把算法写的更加高级【手动狗头】
}
T=s[i];
CreateTree(T->lchild,s,++i);
CreateTree(T->rchild,s,++i);
}????????那么我的算法是先构造叶子结点吗？显然不是的，因为我操作的是T=s[i]，而不是先引用CreateTree(T->lchild,s,++i)。那我的代码不是从底到顶栈形式的吗？其实也是。因为我虽然先构造了根结点，但是根结点的代码仍没有结束，直到左子树构造完了，又回到根结点的函数体，进行构造右子树运算；直到右子树构造完了，又回到根结点的函数体，结束函数体。
? ? ? ? 那从底到顶的函数是什么样的呢？我想要输入一组字符，让你逆序输出，你就可以这么写：
void Reverse(char s[],int i){//问：这里的i是什么意思？
if(i!=s.length) Reverse(s,i+1);
cout<<s[i-1];
}
//答：i代表的是数组的逻辑地址（从1开始）? ? ? ? 发现什么不同了没有？计算内容和递归内容的位置有所不同，如果先进行运算再调用递归就是从顶到底，先递归就是从底到顶。（这是逻辑上的，机器运算的过程都是从底到顶，因为最后都必须回到最开始的函数结束函数体）
? ? ? ? 那么关系是不是只有这两种？显然不是。我们可以将计算内容和递归内容有机结合。比如求n个数阶乘：
int factorial(int n){
if(n==1) return 1;
return n*factorial(n-1);
}? ? ? ? 在进行二叉树的递归函数的时候我们也可以将计算内容和递归内容相互交叉。比如递归函数的双序遍历，在双序输出树的时候就可以采用这种方式。
void OutTree(Tree &tree){ //输出树
cout<<tree->data; //输出数据
if(tree->lchild) OutTree(tree->lchild); //输出左子树
cout<<tree->data; //回序输出数据
if(tree->rchild) OutTree(tree->rchild); //输出右子树
}?实战一下^_^
? ? ? ? 有uu说：“道理我都懂，可我就是不讲道理（bushi），不会构建呀。”那我就在这里给大家演示几个比较复杂的递归示例的编写过程吧！
示例1
? ? ? ? 迷宫问题（简化版），实验二2016题，题目和完整代码见2016迷宫问题（简化DFS算法）
? ? ? ? 递归函数的部分就在下面了：
void DFS(int been[],int a[][3],int now,int length){//输入来过的路口情况、所有路口通往的路与目前所在的路、路口个数
been[now-1]=1;
for(int i=0;i<3;i++)//如果到达的地方不属于路口、这个路口指向的地方没去过，我们就直接过去
if(now<=length&&now>=1&&been[a[now-1][i]-1]==0) DFS(been,a,a[now-1][i],length);
}? ? ? ? 那么我们是怎么构造这个代码的？首先我们得知道，迷宫问题怎么去做？一个路口可以走向三个路口，如果是0就不能走，那么我们必须要这个路口的坐标。然后拿到坐标了就需要调用这个坐标的三个可前往的地址，诶，那输入又要加一个a[][3]，如果你用全局变量也可以。那么目前，输入的值就只有int a[][3]和int now。
? ? ? ? 返回值是什么呢？如果不了解这个算法，你可能会设定返回值为一个bool类型的量，如果某个地方到达终点了，就一层层把bool类型量返回到最开始的输出函数。就好像我们要知道某人的祖先是否骄傲，这个人如果没有出息，就返回0，这个人如果有出息，就返回1，这个人的爹的几个孩子只要有出息，就返回1，这个1就会贯穿青史，让他祖上十八代都很骄傲，最终我们就可以得到他的祖先是否骄傲，和这个问题一样。
? ? ? ? 但这有个问题，你可以是你爹的儿子，但你爹不能是你的儿子。2号路口可以到3号路口，3号路口却也能回来，裂开了呀佳人们。那我们就必须记录每一个路口是否到达过，这样才能保证不出现死循环。这样2到过3,3就不能返回2。所以我们就需要构造有一个int been[]数组来存储是否到过某个地方。那么输入的值就成了int a[][3],int now,int been[]。
? ? ? ? 肯定有人很好奇，为什么我的代码还有个int length作为输入，这是题目的一个小坑，第一个输入示例中只有6个路口，却可以走到7,7是终点。我们当然可以依据这个情况把been[7]设为1，但却不能遍历been[7]的路口情况，不然就会调用无效空间。所以在进行递归的时候要在条件中标注now<=length&&now>=1。
? ? ? ? 输入、输出条件可以是先简单确定，后面慢慢加，但是一定要保持高度的一致性（每个子问题的输入输出必须是同一个含义）。那么其实输入输出决定了，对于这个问题而言函数部分也就简单了，第一步肯定是先把been数组更新一下（问：如果后更新会怎么样），然后再进行对他前往的三个路口的递归调用。
? ? ? ? 答：后更新的话还是会导致死循环，比如2路口前往3路口，我2路口此时没有标注来过，3路口也可以前往2路口，此时3路口还是没标注来过，就会死循环。
示例2
? ? ? ? 3011基于二叉树的表达式求值
总结
? ? ? ? 进行递归编写的时候，我们首先要自己有能力跑一遍整个运算过程，理解问题。随后简单地确定一下输入输出变量，要保持高度的一致性。构造递归函数的条件部分（终止条件、递归条件）、递归部分（计算内容、递归内容），在进行构造的过程中可能发现需要新的输入变量，或者修改输出变量，修改的时候仍需保持高度的一致性。