用最基本的 Fibonacci 数列就可以说明白了
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)。
