【斐波那契数列】递归调用在ACM上为什么会运作超时
【斐波那契数列】递归调用在ACM上为什么会运行超时？
------解决方案--------------------
尾递归只有特定语言可以，需要编译器进行优化，C#、Java这种语言没有提供这类功能
简单的说就是把上一个计算结果传递给下一层，那么下一层就不需要等待返回值了。
但是根据函数原理，还是要等待返回（哪里调用，返回哪里），所以如果没有编译器的支持，还是会因递归深度过深而超时。
举个例子，你可以这样写：
应该没问题
迭代比如普通的循环就是：
公式法就是利用斐波那契数列数列的通项，直接带入公式计算，效率最高。但一般公式法需要计算，比较麻烦。
效率上:公式>迭代>递归，递归使用时要求很高，限制多，但高度抽象。
------解决方案--------------------
lz的代码是不是有问题啊？运行后得不出正确结果
------解决方案--------------------
传说中的记忆化问题……
当你计算F（10）的时候，你告诉他需要先计算F(9)和F（8），当你计算F(8)的时候需要计算F(7)和F(6)……假设这边算完了，然后你算F（9），F(9)要算F(8)和F（7），关键在于你没告诉他你已经在刚才把F(8)算完了，所以他又会去算F(8)，于是又会去算F(7)和F(6)………… 造成了几何级数级别的重复计算，这就是你超时的原因。
解决方法就是用一个数组，比如flag[100]，一开始初始化成-1（斐波那契数列里没有-1），然后每算出一个F(X)就把flag[X]改成F[X]，当你要计算F（x）时，首先看看flag[X]是否为-1，如果是，说明还没算过，继续算，如果已经不是-1了，说明已经算过了，就可以直接return flag[X]了。这个方法就叫做“记忆化”，意思就是把你算过的结果记住，以后就不要再重复算了。
大学老师特别喜欢用这个例子说明“递归比循环慢”，这从逻辑上是说不通的。递归确实比循环慢，那也是因为它需要不断进行压栈、出栈的操作，而这个操作比循环根本慢不到哪儿去。不加记忆化就说递归比循环慢，只能说明他不会写递归…………
#include<iostream>
using namespace std;
int Fibonacci(int n)
{
if(n==0)
return 0;
if(n==1)
return 1;
return Fibonacci(n-1)+Fibonacci(n-2);
}
int main()
{
int n,i;
cin>>n;
cout<<Fibonacci(n);
return 0;
}
------解决方案--------------------
尾递归只有特定语言可以，需要编译器进行优化，C#、Java这种语言没有提供这类功能
简单的说就是把上一个计算结果传递给下一层，那么下一层就不需要等待返回值了。
但是根据函数原理，还是要等待返回（哪里调用，返回哪里），所以如果没有编译器的支持，还是会因递归深度过深而超时。
举个例子，你可以这样写：
#include <stdio.h>
int f(int n,int f1,int f2){
if(n<2){
return f1;
}else{
return f(n-1,f1,f2+f1);
}
}
int main ()
{
int n = 50;
int rs = f(n,1,1);
printf("%d",rs);
}
应该没问题
迭代比如普通的循环就是：
int current;
f0=f1=1;
for(i = 1;i < n;i++)
{
current = f0 + f1;
f0 = f1;
f1 = currentFib;
}
公式法就是利用斐波那契数列数列的通项，直接带入公式计算，效率最高。但一般公式法需要计算，比较麻烦。
效率上:公式>迭代>递归，递归使用时要求很高，限制多，但高度抽象。
------解决方案--------------------
# include <stdio.h>
int main(void)
{
int n;
int f1, f2, f3;
int i;
f1 = 1;
f2 = 2;
printf("请输入您需要求的数的序列：");
scanf("%d", &n);
if (1 == n)
f3 = 1;
else if (2 == n)
f3 = 2;
else
{
for (i=3; i<=n; ++i)
{
f3 = f1 + f2;
f1 = f2;
f2 = f3;
}
}
printf("%d\n",f3);
return 0;
}
lz的代码是不是有问题啊？运行后得不出正确结果
------解决方案--------------------
传说中的记忆化问题……
当你计算F（10）的时候，你告诉他需要先计算F(9)和F（8），当你计算F(8)的时候需要计算F(7)和F(6)……假设这边算完了，然后你算F（9），F(9)要算F(8)和F（7），关键在于你没告诉他你已经在刚才把F(8)算完了，所以他又会去算F(8)，于是又会去算F(7)和F(6)………… 造成了几何级数级别的重复计算，这就是你超时的原因。
解决方法就是用一个数组，比如flag[100]，一开始初始化成-1（斐波那契数列里没有-1），然后每算出一个F(X)就把flag[X]改成F[X]，当你要计算F（x）时，首先看看flag[X]是否为-1，如果是，说明还没算过，继续算，如果已经不是-1了，说明已经算过了，就可以直接return flag[X]了。这个方法就叫做“记忆化”，意思就是把你算过的结果记住，以后就不要再重复算了。
大学老师特别喜欢用这个例子说明“递归比循环慢”，这从逻辑上是说不通的。递归确实比循环慢，那也是因为它需要不断进行压栈、出栈的操作，而这个操作比循环根本慢不到哪儿去。不加记忆化就说递归比循环慢，只能说明他不会写递归…………