Java递归Fibonacci序列

Question

请解释这个简单的代码:

public int fibonacci(int n)  {
    if(n == 0)
        return 0;
    else if(n == 1)
      return 1;
   else
      return fibonacci(n - 1) + fibonacci(n - 2);
}

我对最后一行感到困惑,特别是因为如果n = 5,那么将调用fibonacci(4)+ fibonacci(3)等等但是我不明白这个算法如何计算索引5处的值方法.请详细说明!

Answer 1

在斐波那契序列中,每个项目是前两个项目的总和.所以,你写了一个递归算法.

所以,

fibonacci(5) = fibonacci(4) + fibonacci(3)

fibonacci(3) = fibonacci(2) + fibonacci(1)

fibonacci(4) = fibonacci(3) + fibonacci(2)

fibonacci(2) = fibonacci(1) + fibonacci(0)

现在你已经知道了fibonacci(1)==1 and fibonacci(0) == 0.因此,您可以随后计算其他值.

现在,

fibonacci(2) = 1+0 = 1
fibonacci(3) = 1+1 = 2
fibonacci(4) = 2+1 = 3
fibonacci(5) = 3+2 = 5

从fibonacci序列0,1,1,2,3,5,8,13,21....我们可以看到,对于5th element斐波纳契序列返回5.

请参阅此处了解递归教程.

Answer 2

您的代码有两个问题:

1. 结果存储在int中,它只能处理前48个斐波纳契数,在此之后整数填充减去位并且结果是错误的.
2. 但你永远不能运行斐波那契(50).
   代码
   fibonacci(n - 1) + fibonacci(n - 2)
   非常错误.
   问题在于它称斐波那契不是50倍而是更多.
   起初它称为斐波那契(49)+斐波那契(48),
   下一个斐波那契(48)+斐波那契(47)和斐波那契(47)+斐波那契(46)
   每次它变得更加斐波那契(n),因此复杂性呈指数级增长.

非递归代码的方法:

 double fibbonaci(int n){
    double prev=0d, next=1d, result=0d;
    for (int i = 0; i < n; i++) {
        result=prev+next;
        prev=next;
        next=result;
    }
    return result;
}

Answer 3

在伪代码中,其中n = 5,发生以下情况:

fibonacci(4)+ fibonnacci(3)

这分解为:

(斐波那契(3)+斐波那契(2))+(斐波那契(2)+斐波那契(1))

这分解为:

(((fibonacci(2)+ fibonnacci(1))+((fibonacci(1)+ fibonnacci(0)))+(((fibonacci(1)+ fibonnacci(0))+ 1))

这分解为:

((((fibonacci(1)+ fibonnacci(0))+ 1)+((1 + 0))+((1 + 0)+ 1))

这分解为:

((((1 + 0)+ 1)+((1 + 0))+((1 + 0)+ 1))

这导致:5

鉴于fibonnacci序列是1 1 2 3 5 8 ...,第5个元素是5.您可以使用相同的方法来计算其他迭代.

Answer 4

有时递归很难掌握.只需在一张纸上评估一小部分:

fib(4)
-> fib(3) + fib(2)
-> fib(2) + fib(1) + fib(1) + fib(0)
-> fib(1) + fib(0) + fib(1) + fib(1) + fib(0)
-> 1 + 0 + 1 + 1 + 0
-> 3

我不确定Java实际上是如何评估它的,但结果将是相同的.

Answer 5

您还可以简化您的功能,如下所示:

public int fibonacci(int n)  {
    if (n < 2) return n;

    return fibonacci(n - 1) + fibonacci(n - 2);
}

Answer 6

                                F(n)
                                /    \
                            F(n-1)   F(n-2)
                            /   \     /      \
                        F(n-2) F(n-3) F(n-3)  F(n-4)
                       /    \
                     F(n-3) F(n-4)

需要注意的重要一点是该算法是指数的,因为它不存储先前计算的数字的结果.例如,F(n-3)被称为3次.

有关更多详细信息,请参阅dasgupta第0.2章的算法

Answer 7

大多数答案都很好,并解释了斐波纳契的递归是如何工作的.

以下是对包括递归在内的三种技术的分析:

1. 对于循环
2. 递归
3. 记忆化

这是我测试所有三个的代码:

public class Fibonnaci {
    // Output = 0 1 1 2 3 5 8 13

    static int fibMemo[];

    public static void main(String args[]) {
        int num = 20;

        System.out.println("By For Loop");
        Long startTimeForLoop = System.nanoTime();
        // returns the fib series
        int fibSeries[] = fib(num);
        for (int i = 0; i < fibSeries.length; i++) {
            System.out.print(" " + fibSeries[i] + " ");
        }
        Long stopTimeForLoop = System.nanoTime();
        System.out.println("");
        System.out.println("For Loop Time:" + (stopTimeForLoop - startTimeForLoop));


        System.out.println("By Using Recursion");
        Long startTimeRecursion = System.nanoTime();
        // uses recursion
        int fibSeriesRec[] = fibByRec(num);

        for (int i = 0; i < fibSeriesRec.length; i++) {
            System.out.print(" " + fibSeriesRec[i] + " ");
        }
        Long stopTimeRecursion = System.nanoTime();
        System.out.println("");
        System.out.println("Recursion Time:" + (stopTimeRecursion -startTimeRecursion));



        System.out.println("By Using Memoization Technique");
        Long startTimeMemo = System.nanoTime();
        // uses memoization
        fibMemo = new int[num];
        fibByRecMemo(num-1);
        for (int i = 0; i < fibMemo.length; i++) {
            System.out.print(" " + fibMemo[i] + " ");
        }
        Long stopTimeMemo = System.nanoTime();
        System.out.println("");
        System.out.println("Memoization Time:" + (stopTimeMemo - startTimeMemo));

    }


    //fib by memoization

    public static int fibByRecMemo(int num){

        if(num == 0){
            fibMemo[0] = 0;
            return 0;
        }

        if(num ==1 || num ==2){
          fibMemo[num] = 1;
          return 1; 
        }

        if(fibMemo[num] == 0){
            fibMemo[num] = fibByRecMemo(num-1) + fibByRecMemo(num -2);
            return fibMemo[num];
        }else{
            return fibMemo[num];
        }

    }


    public static int[] fibByRec(int num) {
        int fib[] = new int[num];

        for (int i = 0; i < num; i++) {
            fib[i] = fibRec(i);
        }

        return fib;
    }

    public static int fibRec(int num) {
        if (num == 0) {
            return 0;
        } else if (num == 1 || num == 2) {
            return 1;
        } else {
            return fibRec(num - 1) + fibRec(num - 2);
        }
    }

    public static int[] fib(int num) {
        int fibSum[] = new int[num];
        for (int i = 0; i < num; i++) {
            if (i == 0) {
                fibSum[i] = i;
                continue;
            }

            if (i == 1 || i == 2) {
                fibSum[i] = 1;
                continue;
            }

            fibSum[i] = fibSum[i - 1] + fibSum[i - 2];

        }
        return fibSum;
    }

}

结果如下:

By For Loop
 0  1  1  2  3  5  8  13  21  34  55  89  144  233  377  610  987  1597  2584  4181 
For Loop Time:347688
By Using Recursion
 0  1  1  2  3  5  8  13  21  34  55  89  144  233  377  610  987  1597  2584  4181 
Recursion Time:767004
By Using Memoization Technique
 0  1  1  2  3  5  8  13  21  34  55  89  144  233  377  610  987  1597  2584  4181 
Memoization Time:327031

因此,我们可以看到memoization是最好的时间,并且循环匹配紧密.

但递归时间最长,在现实生活中可能应该避免.此外,如果您使用递归,请确保优化解决方案.

Answer 8

这是我发现的最好的视频,它完整地解释了Java中的递归和Fibonacci序列.

http://www.youtube.com/watch?v=dsmBRUCzS7k

这是他的序列代码,他的解释比我试图输入它更好.

public static void main(String[] args)
{
    int index = 0;
    while (true)
    {
        System.out.println(fibonacci(index));
        index++;
    }
}
    public static long fibonacci (int i)
    {
        if (i == 0) return 0;
        if (i<= 2) return 1;

        long fibTerm = fibonacci(i - 1) + fibonacci(i - 2);
        return fibTerm;
    }

Answer 9

对于fibonacci递归解决方案,重要的是保存较小的斐波纳契数的输出,同时检索较大数的值.这称为"记忆".

这是一个使用memoizing较小的fibonacci值的代码,同时检索更大的fibonacci数.此代码是高效的,不会产生多个相同功能的请求.

import java.util.HashMap;

public class Fibonacci {
  private HashMap<Integer, Integer> map;
  public Fibonacci() {
    map = new HashMap<>();
  }
  public int findFibonacciValue(int number) {
    if (number == 0 || number == 1) {
      return number;
    }
    else if (map.containsKey(number)) {
      return map.get(number);
    }
    else {
      int fibonacciValue = findFibonacciValue(number - 2) + findFibonacciValue(number - 1);
      map.put(number, fibonacciValue);
      return fibonacciValue;
    }
  }
}