递归与迭代（斐波那契数列）

Question

我有两种不同的方法，一种是使用迭代计算斐波纳契数列到第n个元素，另一种使用递归方法做同样的事情。

---

程序示例如下：

import java.util.Scanner; 

public class recursionVsIteration { 

    public static void main(String[] args) { 

     Scanner sc = new Scanner(System.in); 

     //nth element input 
     System.out.print("Enter the last element of Fibonacci sequence: "); 
     int n = sc.nextInt(); 

     //Print out iteration method 
     System.out.println("Fibonacci iteration:"); 
     long start = System.currentTimeMillis(); 
     System.out.printf("Fibonacci sequence(element at index %d) = %d \n", n, fibIteration(n)); 
     System.out.printf("Time: %d ms\n", System.currentTimeMillis() - start); 

     //Print out recursive method 
     System.out.println("Fibonacci recursion:"); 
     start = System.currentTimeMillis(); 
     System.out.printf("Fibonacci sequence(element at index %d) = %d \n", n, fibRecursion(n)); 
     System.out.printf("Time: %d ms\n", System.currentTimeMillis() - start); 
    } 

    //Iteration method 
    static int fibIteration(int n) { 
     int x = 0, y = 1, z = 1; 
     for (int i = 0; i < n; i++) { 
      x = y; 
      y = z; 
      z = x + y; 
     } 
     return x; 
    } 

    //Recursive method 
    static int fibRecursion(int n) { 
     if ((n == 1) || (n == 0)) { 
      return n; 
     } 
     return fibRecursion(n - 1) + fibRecursion(n - 2); 
    } 
} 

---

我试图找出哪一种方法更快。我得出这样的结论：对于较小数量的数量，递归更快，但随着第n个元素的值增加，递归递减变慢并且迭代变得更快。以下是三个不同的Ñ三个不同的结果：

---

实施例＃1（N = 10）

Enter the last element of Fibonacci sequence: 10 
Fibonacci iteration: 
Fibonacci sequence(element at index 10) = 55 
Time: 5 ms 
Fibonacci recursion: 
Fibonacci sequence(element at index 10) = 55 
Time: 0 ms 

---

实施例＃2（N = 20）

Enter the last element of Fibonacci sequence: 20 
Fibonacci iteration: 
Fibonacci sequence(element at index 20) = 6765 
Time: 4 ms 
Fibonacci recursion: 
Fibonacci sequence(element at index 20) = 6765 
Time: 2 ms 

---

例3（N = 30）

Enter the last element of Fibonacci sequence: 30 
Fibonacci iteration: 
Fibonacci sequence(element at index 30) = 832040 
Time: 4 ms 
Fibonacci recursion: 
Fibonacci sequence(element at index 30) = 832040 
Time: 15 ms 

---

我真正想知道的是，为什么突然迭代变得越来越快和递归越来越慢。我很抱歉，如果我错过了这个问题的一些明显的答案，但我仍然对编程不熟悉，我真的不明白背后发生了什么，我想知道。请提供一个好的解释或指引我正确的方向，以便我可以自己找出答案。此外，如果这不是一个好方法来测试哪种方法更快，让我知道并建议我不同的方法。

在此先感谢！

Answer 1

对于简洁，设F（x）为递归斐波

F(10) = F(9)      + F(8) 
F(10) = F(8)  + F(7)  + F(7) + F(6) 
F(10) = F(7) + F(6) + F(6) + F(5) + 4 more calls. 
.... 

所以你的呼吁F（8）的两倍， F（7）3倍，F（6）5倍，F（ 5）7次..等

因此，随着更大的输入，树越来越大。

Answer 2

This article在递归和迭代之间做了比较，并涵盖了它们在生成斐波那契数字时的应用。

正如文章指出，

的原因表现不佳在每次递归调用的不良水平的寄存器重推抵扣。

基本上说递归方法中有更多的开销。

而且，看看Memoization

Answer 3

当进行递归实现斐波那契数的算法，要添加的一遍又一遍的计算相同值的多余调用。

fib(5) = fib(4) + fib(3) 
fib(4) = fib(3) + fib(2) 
fib(3) = fib(2) + fib(1) 

通知书的，fib(2)将冗余既为fib(4)和fib(3)计算。 但是，这可以通过一种称为Memoization的技术来克服，该技术通过存储这些值来提高斐波那契递归的效率，您只计算一次。对已知值进一步调用fib(x)可能会被简单的查找所替代，从而无需进一步的递归调用。

这是迭代和递归方法的主要区别，如果您有兴趣，还有其他更多的计算斐波那契数的efficient algorithms。

Answer 4

使用递归方式，时间复杂度为O(fib(n))，这非常昂贵。迭代方法是O(n)这不会显示，因为a）您的测试非常短，代码甚至不会编译b）您使用的数字非常小。

这两个示例运行得越多，它们的速度越快。一旦循环或方法被调用了10,000次，它应该被编译为本地代码。

Answer 5

如果任何人是具有感兴趣的阵列以迭代的功能：

public static void fibonacci(int y) 
{ 
    int[] a = new int[y+1]; 
    a[0] = 0; 
    a[1] = 1; 
    System.out.println("Step 0: 0"); 
    System.out.println("Step 1: 1"); 
    for(int i=2; i<=y; i++){ 
     a[i] = a[i-1] + a[i-2]; 
     System.out.println("Step "+i+": "+a[i]); 
    } 
    System.out.println("Array size --> "+a.length); 
} 

将该溶液崩溃为输入值0。

原因：数组a将被初始化为0+1=1但连续赋值a[1]将导致索引超出范围异常。

要么添加一个声明，如果在y=0返回0或y+2初始化数组，这将浪费1 INT，但仍然是不变的空间，不会改变大O。

Answer 6

为什么递归比较慢？

当您再次调用自身的功能（如递归）编译器分配新激活记录（试想作为一个普通的堆栈）的新功能。该堆栈用于保存状态，变量和地址。编译器为每个函数创建一个堆栈，并且这个创建过程一直持续到达到基本情况。所以当你的数据量变大时编译器需要大的堆栈段来计算整个过程。在这个过程中，计算和管理这些记录也被计算在内。

此外，在递归中，堆栈段正在运行期间引发的。编译器不知道将占用多少内存。

这就是为什么如果你不能正确处理您的基本情况你将接受一个名为StackOverflow的 :)著名的错误。

Answer 7

我更喜欢使用黄金数字的数学解决方案。享受

private static final double GOLDEN_NUMBER = 1.618d; 

public long fibonacci(int n) { 
    double sqrt = Math.sqrt(5); 

    double result = Math.pow(GOLDEN_NUMBER, n); 

    result = result - Math.pow(1d - GOLDEN_NUMBER, n); 

    result = Math.round(result/sqrt); 

    return Double.valueOf(result).longValue(); 
} 

Answer 8

无论何时您需要花费时间完成特定算法，最好总是考虑时间复杂性。

根据O（某物）评估论文的时间复杂度。

比较上述两种方法，迭代方法的时间复杂度为O（n），而递归方法的时间复杂度为O（2^n）。

让我们试着找到fib(4)

迭代方法的时间复杂度，环路评估的4倍，所以它的时间复杂度为O(n)。

递归方法，

       fib(4) 

      fib(3)    +    fib(2) 

     fib(2) + fib(1)   fib(1)  +  fib(0) 

fib(1) + fib(0) 

所以撒谎（）被调用9倍，比2略低^ N时，n的值是大的，即使是小也（记住BigOh（O）负责upper bound）。

因此，我们可以说，迭代方法在polynomial time评估，而递归一个在exponential time

Answer 9

评估您使用效率不高的递归方法。我建议你使用尾递归。与您的方法相比，尾随递归在任何时间点只保留堆栈中的一个函数调用。

public static int tailFib(int n) { 
    if (n <= 1) { 
     return n; 
    } 
    return tailFib(0, 1, n); 
} 

private static int tailFib(int a, int b, int count) { 
    if(count <= 0) { 
     return a; 
    } 
    return tailFib(b, a+b, count-1); 
} 

public static void main(String[] args) throws Exception{ 
    for (int i = 0; i <10; i++){ 
     System.out.println(tailFib(i)); 
    } 
} 

Answer 10

我有一个递归解决方案，您可以在其中存储计算值以避免进一步不必要的计算。代码在下面提供，

public static int fibonacci(int n) { 

     if(n <= 0) return 0; 
     if(n == 1) return 1; 

     int[] arr = new int[n+1]; 

     // this is faster than using Array 
     // List<Integer> lis = new ArrayList<>(Collections.nCopies(n+1, 0)); 

     arr[0] = 0; 
     arr[1] = 1; 

     return fiboHelper(n, arr); 
    } 

    public static int fiboHelper(int n, int[] arr){ 

     if(n <= 0) { 
      return arr[0]; 
     } 

     else if(n == 1) { 
      return arr[1]; 
     } 

     else { 

      if(arr[n-1] != 0 && (arr[n-2] != 0 || (arr[n-2] == 0 && n-2 == 0))){  
       return arr[n] = arr[n-1] + arr[n-2]; 
      } 

      else if (arr[n-1] == 0 && arr[n-2] != 0){ 
       return arr[n] = fiboHelper(n-1, arr) + arr[n-2]; 
      } 

      else { 
       return arr[n] = fiboHelper(n-2, arr) + fiboHelper(n-1, arr); 
      } 

     }    
    }