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

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个元素的值增加，递归速度变慢，迭代速度变快。以下是三个不同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

在执行斐波那契算法的递归实现时，通过反复重新计算相同的值来添加冗余调用。

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

请注意，fib（2）对于fib（4）和fib（3）都将进行冗余计算。然而，这可以通过一种称为记忆的技术来克服，该技术通过存储已经计算过一次的值来提高递归斐波那契的效率。对于已知值的进一步调用fib（x）可以用简单的查找来代替，从而消除了进一步递归调用的需要。

这是迭代和递归方法之间的主要区别，如果你感兴趣，还有其他更有效的斐波那契数计算算法。

Answer 2

本文对递归和迭代进行了比较，并介绍了它们在生成斐波那契数方面的应用。

如文章所述，

性能不佳的原因是每次递归调用的错误级别中寄存器的大量推送弹出。

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

另外，看看记忆化

Answer 3

为了简洁起见，设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次。。等等

因此，随着投入的增加，树变得越来越大。