前言

在高中班群里水群的时候，大肌让我教他C++，昨天和xy聊天的时候他也间接性地“催更”了，甚至还把我的博客网址单独记录下来。呜呜呜，有点感动。

原本是计划寒假的时候再更新博客，因为我想把博客做好一点，但想了想，好像也没有哪个陌生人会关注我的博客，所以倒不如写自己想写的，学了什么就写什么，这样一来既可以督促自己重新消化所学的知识，又可以给别人提供参考。而且如果大肌都可以看明白，说明我写得还不错？哈哈哈哈，开玩笑的

递归函数

递归函数，简单来说就是函数自己调用自己。可能有点抽象，那我们直接上代码吧。

现在我们要写一个等差数列的函数，首项是1，公差是3，怎么用递归函数来实现呢？

首先，我们定义的这个函数很显然有返回值，然后再观察等差数列的性质：后一项与前一项的差等于公差。我们先写一个大概的函数框架：

1
2
3
4
5
int f(int n){
    int result;
    result = f(n-1) + 3;
    return result;
}

我们先来举个例子，要求第四项是多少，我们就要知道第三项是多少，以此类推……直到我们要知道第一项是多少。好，然后我们要怎么知道第一项是多少呢？如果你还类推那你可能不适合学递归函数。直接给他一个首项啊！

所以完整的递归函数代码如下：

1
2
3
4
5
6
7
8
9
10
int f(int n){
    int result;
    if(n == 1){
        result = 1;
    }
    else{
        result = f(n-1) + 3;
    }
    return result;
}

递归函数的缺陷

这里我们引入斐波那契数列的问题，我们知道斐波那契数列的特点是：f(n) = f(n-1) + f(n-2)，其中f(1) = 1，f(2) = 1。
用脑子思考模拟一下刚才学的递归函数，你会发现，这个函数的缺陷在于它会重复计算相同的子问题，导致效率低下。

怕你不明白，我们来看看：
假设你要求f(5),你是不是要先计算f(4)和f(3)呢？，你求f(4)的时候又要计算f(3)和f(2),OK,这里就可以看到，我们重复计算了f(4)，如果你自己用递归函数在编译器里运行，当n足够大的时候，你会发现到后面要花很长时间才会算出一项。

递推算法

那怎么办呢？我们可以用另一种方法，叫做“递推算法”，简单一点，就是我们可以用for循环计算每一项，然后把结果存入数组，这样就不用重复计算了。

1
2
3
4
5
6
7
8
9
int f(int n){
    int a[1000] = {0};
    a[1] = 1;
    a[2] = 1;
    for(int i=3;i<=n;i++){
        a[i] = a[i-1] + a[i-2];
    }
    return a[n];
}

你可能有疑问：

1.为什么要先定义数组里的元素都为0呢？

因为如果不定义的话，空数组里的元素是不知道的，是随机的的，也就是垃圾值，有时候会影响结果。

2.a[0]怎么不用？

只是为了方便计算，我们把数组的下标从1开始，所以a[0]是没有用的。

总结

递归函数主要是为了优化效率，但是也有缺陷，比如重复计算相同的子问题，导致效率低下。递推算法是另一种优化方法，通过循环计算每一项，然后把结果存入数组，避免重复计算。

怕你不懂，下一次我们找几道题目来评鉴一下。