Fibonacci数列递归超时 2021.12.06

通过这道题搞清楚了递归和递推的区别：

        首先要把词义弄清楚，真正的数学意义上的“递归”（recursive）包含了“递推”（recurrence）和“回归”（regression）的过程，在程序执行的过程中，“递归”（recursive）指的是一种方法，把大的复杂的问题分解成更小更简单的问题，逐级分解下去，直到问题的规模小到可以直接求解，然后再逐级向上回溯直到解决最初的问题，用程序来实现这种算法的时候至少包含一次以上的递推执行过程，效率当然比不上直接作一次迭代。递归的计算过程（recursive process）包含了两个阶段，先逐级扩展（expansion），构造起一个由被推迟的操作组成的链条（会被解释器保存在堆栈里），然后在收缩（contraction）阶段逐级回溯执行那些操作。随着递归计算步骤的增多，这种方法消耗的资源会越来越大，而且会包含越来越多的冗余操作，求斐波那契数列的例子（在SICP里被称作“树形递归”）在这方面问题尤其严重，因为它的计算步骤会随着参数而指数性的增长。

package introductory;
import java.util.Scanner;
public class test14 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
//System.out.println(F(n)%10007);
if(n<3){
System.out.println("1");
}else{
//递推
int m = 0, f1 = 1, f2 = 1;
for(int i=3; i<=n; i++){
m = (f1+f2)%10007;
f1 = f2;
f2 = m;
}
System.out.println(m);
}
}
//递归
public static int F(int n){
if( n== 1){
return 1;
}else if(n == 2){
return 1;
}else{
return F(n-1)+F(n-2);
}
}
}

最后

以上就是飘逸大炮最近收集整理的关于Fibonacci数列递归超时 2021.12.06的全部内容，更多相关Fibonacci数列递归超时内容请搜索靠谱客的其他文章。