# 首先我们直接看一个demo以及他的结果
public class QQ {
public static void main(String[] args) throws ParseException {
// 1,1,2,3,5,8 ...
int n = 50;
Long start = System.currentTimeMillis();
System.out.println(fun(n));
System.out.println("time1 : " + (System.currentTimeMillis() - start));
start = System.currentTimeMillis();
System.out.println(fun2(n));
System.out.println("time2 : " + (System.currentTimeMillis() - start));
start = System.currentTimeMillis();
System.out.println(fun3(n));
System.out.println("time3: " + (System.currentTimeMillis() - start));
}
public static long fun(int n) {
if (n <= 2) {
return 1L;
} else {
return fun(n - 1) + fun(n - 2);
}
}
public static long fun2(int n) {
if (n <= 2) {
return 1L;
} else {
long a = 1, b = 1, c = 0;
for (int i = 3; i <= n; i++) {
c = a + b;
a = b;
b = c;
}
return c;
}
}
public static long fun3(int n) {
if (n <= 2) {
return 1L;
} else {
long[] arr = new long[n + 1];
arr[1] = 1;
arr[2] = 1;
for (int i = 3; i <= n; i++) {
arr[i] = arr[i - 1] + arr[i - 2];
}
return arr[n];
}
}
}# 上面代码的计算结果是：
12586269025
time1 : 46059
12586269025
time2 : 0
12586269025
time3: 0
# 分析：
- 可以看出使用递归计算需要的时间最长
- 我们不进行理论的分析，再用一个简单的例子去简要说明一下为什么递归需要的时间这么长
public class QQ {
private static long count = 0L;
public static void main(String[] args) throws ParseException {
// 1,1,2,3,5,8 ...
int n = 50;
Long start = System.currentTimeMillis();
System.out.println(fun(n));
System.out.println("time1 : " + (System.currentTimeMillis() - start));
System.out.println("count: " + count);
}
public static long fun(int n) {
count++;
if (n <= 2) {
return 1L;
} else {
return fun(n - 1) + fun(n - 2);
}
}
}# 上面代码的输出结果是：
12586269025
time1 : 48285
count: 25172538049
# 分析：
- 可以看出fun这个函数被调用了很多次，但是这个函数基本上只有一个逻辑，我们来看看这个比较逻辑调用 25172538049 次会发生些什么吧
public class QQ {
public static void main(String[] args) throws ParseException {
// 1,1,2,3,5,8 ...
int n = 50;
Long start = System.currentTimeMillis();
for (long i = 0; i < 25172538049L; i++) {
}
System.out.println("time1 : " + (System.currentTimeMillis() - start));
}
}# 上面代码的输出结果为：
time1 : 10358
# 分析：
- 上面的代码循环中一共包含两个调用次数较多的逻辑；第一个是比较逻辑，第二个是 自增 逻辑， 可以看出，两个很简单的逻辑调用 25172538049 次就会耗时这么多，那么递归调用加上调用函数的各种开销，一共需要这么长的时间好像也就不足为奇了