递归的三大要素：
第一大要素明确你这个函数想要干什么：搞清楚这个弄函数功能是什么，用来完成什么事。
例如，我定义了一个函数
// 算 n 的阶乘(假设n不为0)
int f(int n){
}
第二要素：寻找递归结束条件
我们必须找出递归的结束条件，不然的话会一直调用自己。我们需找出当参数为什么时，递归结束，之后直接把结果返回。
// 算 n 的阶乘(假设n不为0)
int f(int n){
if(n == 1){
return 1;
}
}
第三要素：找出函数的等价关系式
我们要不断缩小参数范围，缩小之后，可以通过一些辅助变量和唱歌操作，使原函数的结果不变
说白了就是找到一个等价关系式，f(n)的等价关系式子为n*f(n-1);
// 算 n 的阶乘(假设n不为0)
int f(int n){
if(n <= 2){
return n;
}
// 把 f(n) 的等价操作写进去
return f(n-1) * n;
}
至此，递归三要素已经都写进代码里了，所以这个 f(n) 功能的内部代码我们已经写好了。
这就是递归最重要的三要素，每次做递归的时候，你就强迫自己试着去寻找这三个要素。
实例1：裴波那契数列
斐波那契数列的是这样一个数列：1、1、2、3、5、8、13、21、34....，即第一项 f(1) = 1,第二项 f(2) = 1.....,第 n 项目为 f(n) = f(n-1) + f(n-2)。求第 n 项的值是多少。
1，第一递归函数功能
假设f(n)的功能是求第n项的值，代码如下：
int f(int n) {
}
2,找出递归结束的条件
当n=1或n=2，我们可以知道结果f(1) = f(2) = 1.所以递归条件可以为n<=2.代码如下
int f(int n) {
if(n<=2){
return 1;
}
}
第三要素：找出函数的等价关系式
题目已经把等价关系式给我们了，所以我们很容易就能够知道 f(n) = f(n-1) + f(n-2)。
最终代码如下：
int f(int n) {
//1，先写递归结束条件
if(n <= 2) {
return 1;
}
2.接着写等价关系式
return f(n-1)+f(n-2);
}
实例2：小青蛙跳台阶
一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
1、第一递归函数功能
假设 f(n) 的功能是求青蛙跳上一个n级的台阶总共有多少种跳法，代码如下：
int f(int n){
}
2、找出递归结束的条件
求递归结束的条件，你直接把 n 压缩到很小很小就行了，因为 n 越小，我们就越容易直观着算出 f(n) 的多少，所以当 n = 1时， f(1) = 1。代码如下：
int f(int n){
if(n == 1){
return 1;
}
}
第三要素：找出函数的等价关系式：
小青蛙可以跳一个台阶，也可以跳两个，也就是说有两种跳法
第一种跳法：第一次跳了一个台阶，那么还剩下n-1个台阶还没跳，剩下的n-1个台阶的跳法有f(n-1)种。
第二种跳法：第一次跳了两个台阶，那么还剩下n-2个台阶还没，剩下的n-2个台阶的跳法有f(n-2)种。
所以，小青蛙的全部跳法就是这两种跳法之和了，即 f(n) = f(n-1) + f(n-2)。
代码：int f(int n){
if(n <=2){
return n;
}
ruturn f(n-1) + f(n-2);
}
