n==10 20 30 40 50 46 体验一下，感受一下，运行时间
#include <stdio.h>
int fib(int n)
{
if (n<=1) return 1;
else return fib(n-1)+fib(n-2);
}
int main( )
{
int n;
scanf("%d",&n);
printf("%d
" ,fib(n) );
}
先 n==10 20 30 40 50 46 体验一下，感受一下，运行时间
再 提交一下zjut 1029 超时
// Time Limited Exceeded
#include <stdio.h>
int fib(int n)
{
if (n<=1) return 1;
else return fib(n-1)+fib(n-2);
}
int main( )
{
int n;
while(scanf("%d",&n))
printf("%d
" ,fib(n) );
}
普通递归
由上向下，，由大的 算小的
纯递推
//Accept
#include <stdio.h>
int fib[50]={0,1}; //使用打表
void init()
{
int i;
for(i=2;i<50;i++) //纯递推 for循环
fib[i]=fib[i-1]+fib[i-2]; // 由上到下 因为大的 算小的
}
int main( )
{
int n;
init();
while(scanf("%d",&n))
printf("%d
" ,fib[n] );
}
记忆式搜索
递归计算之前，判断前面是否计算过
有小的（数组---保存起来）推大的
//Accept
#include <stdio.h> // 记忆式搜索
int a[50]={0,1};
int fib(int n)
{
if(n<=2) return a[n]=1; // 1赋值给 a[n] //return 1;
else if(a[n]==0) return a[n]=fib(n-1)+fib(n-2); //没有算 先算 右边fib(n-1)+fib(n-2) ，，在保存 a[n]
else return a[n]; // 否则就 算过了，，，直接用它a[n]
}
int main( )
{
int n;
while(scanf("%d",&n)!=EOF)
printf("%d
" ,fib(n) );
}