递归有时候会出现重复计算的情况（如下例题），因此为了提高代码效率，就需要进记忆性递归——即只对第一次出现的新数据进行计算并进行保存，而对于已经计算过的结果，只需将结果取出即可。（它可以提高效率，避免计算机进行重复已做过的完全相同的工作而降低效率）

例1：
我们要求找出具有下列性质数的个数(包含输入的自然数n):
先输入一个自然数n(n≤1000),然后对此自然数按照如下方法进行处理:
不作任何处理;
在它的左边加上一个自然数,但该自然数不能超过原数的一半;
加上数后,继续按此规则进行处理,直到不能再加自然数为止.
输入格式
1个自然数n(n≤1000)
输出格式
1个整数，表示具有该性质数的个数。
样例：
输入 #1
6
输出 #1
6

#include<stdio.h>
int f[1002]={0};
int num(int n)
{f[1]=1;int i,sum=1; if(n==1){return f[n];}else{if(f[n]==0){//如果没做这个数的计算，就进行新计算，并进行保存 for(i=1;i<=n/2;i++){sum+=num(i);}return f[n]=sum;}else{//对于求解过的n，直接取保存的结果即可return f[n]; }}} int main(){int n;scanf("%d",&n);printf("%d",num(n));return 0;}

例2：
斐波那契数列：

#include<stdio.h>
int f[100]={0}; 
int Fibonacci(int n)
{
if(n==1||n==2)
return f[n]=1;
else{
if(f[n]==0)  //没求解过return f[n]=Fibonacci(n-1)+Fibonacci(n-2);else   //求解过，直接取保存的结果值return f[n];}
}int main(){printf("%d\n",Fibonacci(1000)); return 0;}

再来看看递归的斐波那契数列写法：（当然还有数组循环的写法也比递归更有效率）

#include<stdio.h>
int Fibonacci(int n)
{if(n==1||n==2)return 1;elsereturn Fibonacci(n-1)+Fibonacci(n-2);
} 
int main()
{for(int i=1;i<100;i++){printf("%d ",Fibonacci(i));}printf("\n");return 0;}

总结：递归不一定提高效率。它优点在于，将复杂问题简单化，“大事化小，小事易做”。