在 java 中生成斐波那契数的低效递归代码

Question

以下递归方法旨在为给定整数（写在Java中）生成斐波那契数

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

但我发现在第 48 位或更高位置生成斐波那契数需要 20 多秒。你能帮忙解释一下为什么这个 Fib 生产者效率如此低下吗？

比如我这里附上一个简单的测试客户端：

  public static void main(String[] args)
   {
       int hi = 50;

       System.out.println("Sequance, elapsed time, number");

       for (int n = 0; n<= hi; n++)
       {
            long start = System.currentTimeMillis();
            long fib_num = fib(n);
            long end = System.currentTimeMillis();
            long elapse = (end-start)/1000;  
            System.out.printf("%d, %d, %d%n", n, elapse, fib_num);
       }
   }

它的输出是（运行在 i7、4 核 MacBook Pro 2017 型号上）：

Sequance, elapsed time, number
0, 0, 0
1, 0, 1
2, 0, 1
3, 0, 2
4, 0, 3
5, 0, 5
6, 0, 8
7, 0, 13
8, 0, 21
9, 0, 34
10, 0, 55
11, 0, 89
12, 0, 144
13, 0, 233
14, 0, 377
15, 0, 610
16, 0, 987
17, 0, 1597
18, 0, 2584
19, 0, 4181
20, 0, 6765
21, 0, 10946
22, 0, 17711
23, 0, 28657
24, 0, 46368
25, 0, 75025
26, 0, 121393
27, 0, 196418
28, 0, 317811
29, 0, 514229
30, 0, 832040
31, 0, 1346269
32, 0, 2178309
33, 0, 3524578
34, 0, 5702887
35, 0, 9227465
36, 0, 14930352
37, 0, 24157817
38, 0, 39088169
39, 0, 63245986
40, 0, 102334155
41, 0, 165580141
42, 1, 267914296
43, 2, 433494437
44, 3, 701408733
45, 5, 1134903170
46, 8, 1836311903
47, 14, 2971215073
48, 22, 4807526976
49, 34, 7778742049
50, 58, 12586269025

Answer 1

这是一个经典的递归问题，动态规划派上了用场。

实际发生的是您的代码进行了一些已经完成的重新计算，因此导致额外的机器周期和较长的处理时间。

上图描述了您的程序如何计算第 5 个斐波那契数。我们可以看到函数f(3)被调用了2次 fib(2) 3次 fib(1) 5次，而不是计算一次。

解决方案

如果我们存储了 f(3)、f(2)、f(1) 的值，那么我们可以重用旧的存储值，而不是再次计算它。从这里您可以进行研究并阅读 here

Answer 2

这是一个典型的例子，你应该使用记忆。您需要记住已经计算出的数字。简而言之，您需要维护一个数据结构，在这种情况下可以是一个数组，它将保存该索引的斐波那契数。

示例数组如下所示（从索引 0 开始）

0,1,1,2,3,5,8,13

因此，每当您需要计算斐波那契数时，请先检查数组是否已计算斐波那契数。如果是，则 return 它来自数组。如果不是，则计算并存入数组。

Answer 3

这主要是因为这种生成斐波那契数的实现效率极低。

这个特定的算法呈指数增长，而不是线性增长，因为斐波那契的每次调用都会分支成另外两个调用，并在这条轨道上继续。因此，增加 N 的大小会大大增加完成所需的时间。

更好的方法是跟踪先前的值以计算下一个值。

long fibbonaci(int n) {
    long c = 0, k = 1;
    for (int i = 0; i < n; i++) {
        k += c;
        c = k - c;
    }
    return c;
}

在 java 中生成斐波那契数的低效递归代码

inefficient recursive code to produce Fibonacci number in java

java

recursion

fibonacci

解决方案