本系列文章为作者原创，未经作者书面同意，不得转载！
简单递归分析及优化
递归算法在求解一些问题时，代码实现非常简单，但在求解某些问题时递归算法的效率并不高，递归求解过程中会产生大量的重复计算，这种情况下怎么进行优化，需要重点考虑。
本文拿一个简单的案例来介绍一种优化的方法，抛砖引玉！
1 问题提出
我们先来看一道题：NOIP2001 数的计数（洛谷P1028）
这是一道比较典型的可以采用递归求解的题，当然你也可以用其它办法求解，本文既然讲递归，那我们就用递归来解一解。
1.1 题目描述
我们要求找出具有下列性质数的个数(包含输入的自然数n):
先输入一个自然数nnn(n≤1000n \le 1000n≤1000),然后对此自然数按照如下方法进行处理:
- 不作任何处理;
- 在它的左边加上一个自然数,但该自然数不能超过原数的一半;
- 加上数后,继续按此规则进行处理,直到不能再加自然数为止.
1.2 输入输出格式
输入格式：
1个自然数n(n≤1000)
输出格式：
1个整数，表示具有该性质数的个数。
1.3 输入输出样例
输入样例#1：
6
输出样例#1：
6
1.4 说明
满足条件的数为：
6，16，26，126，36，136
这个题目的描叙本身很简单，但我咋一看没看明白，以为每次处理后，自然数是加上左边自然数后形成的新数，其实不是，这里有个也算是小经验吧，大家看题如果没看明白，可以看一看测试用例，分析一下它的计算过程，然后再看题，基本上就没问题了。
好，我们还是回到题目本身，其实明白题意后，题目非常简单，我就不分析了，我们直接看解题过程。
2 普通递归
2.1 代码
问题比较简单，我就不多分析了，直接上代码：
#include <bits/stdc++.h>
using namespace std;
int n;
long ans;
void calc(int k){
ans++;
if(k == 1) return;
for(int i=1;i<=k/2;i++){
calc(i);
}
}
int main(){
cin >> n;
calc(n);
cout << ans;
return 0;
}
这个代码的正确性没有问题，不过如果你直接提交的话，很不幸，你只能得到25分。
为什么？
2.2 过程分析
我们来分析一下，比方说你输入的n是10，这个过程会是怎样，我画了一张图，我们来看一看递归的调用过程：
这张图描叙了递归函数的调用过程。
2.3 问题所在
我们来分析一下上面的计算过程，在这个过程中，计算机内存中实际上建立了多个函数副本，并且我们从函数的参数就能看出，这里有很多的重复计算，calc(2)和calc(1)被多次调用，其实每次调用计算机都需要在内存中新建栈帧，然后进行计算。
分析到这里，想必你已经知道了，这里计算机其实做了很多重复工作，如果calc(2)多次重复计算。
这就是算法效率低下的原因，所以只能给你25分。
3 算法优化
3.1 不想做重复的工作
我们现在知道了普通递归算法在计算的过程中做了很多无用功，为什么？计算机傻？赫赫，计算机其实是挺傻的，它只会按照我们人类的指令（代码）进行工作，所以关键还是要看我们，所以人工智能也没那么可怕，计算机想要真正的聪明，还差的远着呢！
这里为什么会进行重复计算，就是因为我们没有把每一次函数调用的结果保存起来，当遇到同样的问题时，我们又做了一次无用功。
那好，有没有办法避免做无用功呢？当然有，要不我就不会在这里敲键盘了🙂
我们可以用一个数组（记忆数组，这下子计算机有了记忆了，比刚才要稍微多了一点点智能，也算是进化了2000000年吧，计算机的进化比人类要快得多）来保存每次递归调用的结果，在递归调用计算时，我们先去查一下这个数组，是不是同样的问题，我们已经计算过了，如果计算过了，就不要重复计算了，这样是不是要省去很多无用功，算法的效率是不是大大的提高了？
不多说，写代码吧！
2.2 代码实现
#include <bits/stdc++.h>
using namespace std;
int n;
long m[1001]; //记忆数组
long calc(int k){
long res = 0;
if(k == 1) return m[1] = res = 1; //返回结果的同时，别忘了讲结果记忆
for(int i=1;i<=k/2;i++){
if(m[i]==0) //如果不为0，说明计算过，不需要再递归
res += calc(i); //没有计算过，递归计算
res += m[i];
}
return m[k] = res; //返回结果的同时，别忘了讲结果记忆
}
int main(){
cin >> n;
calc(n);
cout << m[n];
return 0;
}
提交代码，AC，恭喜你，通过了！
4 总结
这只是一个简单的栗子，希望分析过程能够对大家有所启发！
