Java-用递归的思想求斐波那契数列第n项的值

一、思想-多路递归

多路递归multi recursion就是在每次递归时包含多次（大于一次）的自身调用。也就是一个问题会被拆分成多个子问题。多路递归比单路递归在分析时间复杂度上比较复杂一些。

二、斐波那契数列

三、例子

以 n = 4 为例，当我们用下面（第四部分）的代码实现时，这个多路递归的求解过程如下图所示。

我们可以看到，

四、Java代码实现

1.求斐波那契数列的第n项

/*递归函数*/
    public static int f(int n){
			//写两个递归出口
        if(n == 0){
            return 0;
        }
        if(n ==1){
            return 1;
        }
			//调用两次自身的函数
        int x = f(n - 1);//要先走完这一步才能继续下面的代码
        int y = f(n - 2);
        return x + y;
    }

2.完整代码 

用 n = 8来测试，结果为21.

public class E06Fibonacci {

    public static void main(String[] args) {
        int f = f(8);
        System.out.println(f);
    }

    /*递归函数*/
    public static int f(int n){

        if(n == 0){
            return 0;
        }
        if(n ==1){
            return 1;
        }

        int x = f(n - 1);
        int y = f(n - 2);
        return x + y;
    }
}