用最基本的 Fibonacci 數(shù)列就可以說明白了
Java Solution of Fibonacci Number
import java.util.*;
public class Solution {
//recusive
/* public static int fibonacci(int n) {
if (n == 0)
return 0;
else if (n == 1)
return 1;
else
return fibonacci(n-1) + fibonacci(n-2);
// Complete the function.
}
*/
// non-recusive
public static int fibonacci(int n){
int tmp1,tmp2,summary;
summary = 1;
tmp1 = 0;
tmp2 = 1;
if(n<=1)
return n;
for(int i = 2; i < n; i++ ){
tmp1 = tmp2;
tmp2 = summary;
summary = tmp1 + tmp2;
}
return summary;
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
scanner.close();
System.out.println(fibonacci(n));
}
}
需要注意的是時間復雜度状植， 遞歸的時間復雜度遠遠大于非遞歸的時間復雜度诚纸。遞歸的時間復雜度是 O(n^1.618)丈钙，空間復雜度是 O(1)剪芥。 而非遞歸的時間復雜度是 O(n)，空間復雜度是 O(1)剃幌。
