1. class demo
   
2. {
   
3. 
   
4. public static void main(String[] args) {
   
5. System.out.println(f(20));
   
6. }
   
7. private static int f(int n) {
   
8. if (n==1 || n==2) {
   
9. return 1;
   
10. }else {
    
11. return f(n-1)+f(n-2);
    
12. }
    
13. }
    
14. }

复制代码

这是怎么计算的？结果是6765。为什么啊，说说计算过程

其实这是一个递归方法，当这式子其实就是f(n)=f(n-1)+f(n-2); f(1)=f(2)=1; 其实他就是一个求Fibonacci数列的第N项

斐波那契数列，1,1,2,3,5,8,13。。。第一项和第二项都是1，从第三项开始，每一项都是前两项的和。

这个数列除了前两项f(1)=f(2)=1之外，后面的其他每一项都等于前两项之和。就比如你求f(20)就等于f(19)+f(18)，而你又需要求f(19)和f(18)的值就分别为f(19)=f(18)+f(17) ,f(18)=f(17)+f(16)....这样依次求到f(3)=f(2)+f(1),通过递归就可以把值返回来。

天凌蓝 发表于 2014-3-5 20:09
其实这是一个递归方法，当这式子其实就是f(n)=f(n-1)+f(n-2); f(1)=f(2)=1; 其实他就是一个求Fibonacci数列 ...

很赞，原来是这样啊