Java递归基础案例-斐波纳契数列

斐波纳契数列
/**
* Title: 斐波纳契数列
*
* Description: 斐波纳契数列，又称黄金分割数列，指的是这样一个数列：1、1、2、3、5、8、13、21、……
* 在数学上，斐波纳契数列以如下被以递归的方法定义：F0=0，F1=1，Fn=F(n-1)+F(n-2)（n>=2，n∈N*）。
*
* 两种递归解法：经典解法和优化解法
* 两种非递归解法：递推法和数组法
*/

  

   

    

     

    
    

     

      package Action;
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      public class test {
     
    
   

    

     

    
    

     
	public static void main(String[] args) {
     
    
   

    

     

    
    

     
		//循环可以很多次，但是最终只有一个返回值
     
    
   

    

     

    
    

     

      		System.out.println(f(10));
     
    
   

    

     

    
    

     

      	}
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
	public static int f(int n) {
     
    
   

    

     

    
    

     
		if (n == 1 || n == 2) { // 递归终止条件
     
    
   

    

     

    
    

     
			//1 1 2 3 5所以前两个数字都是1
     
    
   

    

     

    
    

     
			return 1; //是2或1就结束了，0不计算
     
    
   

    

     

    
    

     

      		}
     
    
   

    

     

    
    

     
		//倒着计算
     
    
   

    

     

    
    

     

      		System.out.println("此次递归数字到："+n+"，n-1:"+(n-1)+",n-2:"+(n-2));
     
    
   

    

     

    
    

     
		return f(n - 1) + f(n - 2); // 相同重复逻辑，缩小问题的规模
     
    
   

    

     

    
    

     

      	}
     
    
   

    

     

    
    

     

      }
     
    
  
 

计算结果：【55】

此次递归数字到：10，n-1:9,n-2:8
此次递归数字到：9，n-1:8,n-2:7
此次递归数字到：8，n-1:7,n-2:6
此次递归数字到：7，n-1:6,n-2:5
此次递归数字到：6，n-1:5,n-2:4
此次递归数字到：5，n-1:4,n-2:3
此次递归数字到：4，n-1:3,n-2:2
此次递归数字到：3，n-1:2,n-2:1
此次递归数字到：3，n-1:2,n-2:1
此次递归数字到：4，n-1:3,n-2:2
此次递归数字到：3，n-1:2,n-2:1
此次递归数字到：5，n-1:4,n-2:3
此次递归数字到：4，n-1:3,n-2:2
此次递归数字到：3，n-1:2,n-2:1
此次递归数字到：3，n-1:2,n-2:1
此次递归数字到：6，n-1:5,n-2:4
此次递归数字到：5，n-1:4,n-2:3
此次递归数字到：4，n-1:3,n-2:2
此次递归数字到：3，n-1:2,n-2:1
此次递归数字到：3，n-1:2,n-2:1
此次递归数字到：4，n-1:3,n-2:2
此次递归数字到：3，n-1:2,n-2:1
此次递归数字到：7，n-1:6,n-2:5
此次递归数字到：6，n-1:5,n-2:4
此次递归数字到：5，n-1:4,n-2:3
此次递归数字到：4，n-1:3,n-2:2
此次递归数字到：3，n-1:2,n-2:1
此次递归数字到：3，n-1:2,n-2:1
此次递归数字到：4，n-1:3,n-2:2
此次递归数字到：3，n-1:2,n-2:1
此次递归数字到：5，n-1:4,n-2:3
此次递归数字到：4，n-1:3,n-2:2
此次递归数字到：3，n-1:2,n-2:1
此次递归数字到：3，n-1:2,n-2:1
此次递归数字到：8，n-1:7,n-2:6
此次递归数字到：7，n-1:6,n-2:5
此次递归数字到：6，n-1:5,n-2:4
此次递归数字到：5，n-1:4,n-2:3
此次递归数字到：4，n-1:3,n-2:2
此次递归数字到：3，n-1:2,n-2:1
此次递归数字到：3，n-1:2,n-2:1
此次递归数字到：4，n-1:3,n-2:2
此次递归数字到：3，n-1:2,n-2:1
此次递归数字到：5，n-1:4,n-2:3
此次递归数字到：4，n-1:3,n-2:2
此次递归数字到：3，n-1:2,n-2:1
此次递归数字到：3，n-1:2,n-2:1
此次递归数字到：6，n-1:5,n-2:4
此次递归数字到：5，n-1:4,n-2:3
此次递归数字到：4，n-1:3,n-2:2
此次递归数字到：3，n-1:2,n-2:1
此次递归数字到：3，n-1:2,n-2:1
此次递归数字到：4，n-1:3,n-2:2
此次递归数字到：3，n-1:2,n-2:1
55

这个就开始有点难了啊，希望大家好好理解理解。 

文章来源: laoshifu.blog.csdn.net，作者：红目香薰，版权归原作者所有，如需转载，请联系作者。

原文链接：laoshifu.blog.csdn.net/article/details/122793800