递归的三大要素：

第一大要素明确你这个函数想要干什么：搞清楚这个弄函数功能是什么，用来完成什么事。

例如，我定义了一个函数

// 算 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);

}