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

Recursion vs. Iteration (Fibonacci sequence)

提问by msmolcic

I've got two different methods, one is calculating Fibonacci sequence to the nthelement by using iteration and the other one is doing the same thing using recursive method.

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

---

---

Program example looks like this:

程序示例如下所示：

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);
    }
}

---

---

I was trying to find out which method is faster. I came to the conclusion that recursion is faster for the smaller amount of numbers, but as the value of nthelement increases recursion becomes slower and iteration becomes faster. Here are the three different results for three different n:

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

---

---

Example #1 (n = 10)

示例 #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

---

---

Example #2 (n = 20)

示例 #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

---

---

Example #3 (n = 30)

示例 #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

---

---

What I really want to know is why all of a sudden iteration became faster and recursion became slower. I'm sorry if I missed some obvious answer to this question, but I'm still new to the programming, I really don't understand what's going on behind that and I would like to know. Please provide a good explanation or point me in the right direction so I can find out the answer myself. Also, if this is not a good way to test which method is faster let me know and suggest me different method.

我真正想知道的是为什么突然迭代变得更快而递归变得更慢。如果我错过了这个问题的一些明显答案，我很抱歉，但我还是编程新手，我真的不明白背后发生了什么，我想知道。请提供一个很好的解释或为我指明正确的方向，以便我自己找到答案。另外，如果这不是测试哪种方法更快的好方法，请告诉我并建议我使用不同的方法。

Thanks in advance!

提前致谢！

采纳答案by Chris Cudmore

For terseness, Let F(x) be the recursive Fibonacci

为简洁起见，令 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.
....

So your are calling F(8) twice, F(7) 3 times, F(6) 5 times, F(5) 7 times.. and so on

所以你打电话给 F(8) 两次，F(7) 3 次，F(6) 5 次，F(5) 7 次......等等

So with larger inputs, the tree gets bigger and bigger.

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

回答by Nima Vaziri

This articledoes a comparison between recursion and iteration and covers their application on generating fibonacci numbers.

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

As noted in the article,

正如文章中所指出的，

The reason for the poor performance is heavy push-pop of the registers in the ill level of each recursive call.

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

which basically says there is more overhead in the recursive method.

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

Also, take a look at Memoization

另外，看看Memoization

回答by Warlord

When doing the recursive implementation of fibonacci algorithm, you are adding redundant calls by recomputing the same values over and over again.

在进行斐波那契算法的递归实现时，您通过一遍又一遍地重新计算相同的值来添加冗余调用。

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

Notice, that fib(2)will be redundantly calculated both for fib(4)and for fib(3). However this can be overcome by a technique called Memoization, that improves the efficiency of recursive fibonacci by storing the values, you have calculated once. Further calls of fib(x)for known values may be replaced by a simple lookup, eliminating the need for further recursive calls.

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

This is the main difference between the iterative and recursive approaches, if you are interested, there are also other, more efficient algorithmsof calculating fibonacci numbers.

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

回答by Peter Lawrey

Using recursion the way you have, the time complexity is O(fib(n))which is very expensive. The iterative method is O(n)This doesn't show because a) your tests are very short, the code won't even be compiled b) you used very small numbers.

以您拥有的方式使用递归，时间复杂度O(fib(n))非常昂贵。迭代方法是O(n)This does not show 因为 a) 你的测试很短，代码甚至不会被编译 b) 你使用了非常小的数字。

Both examples will become faster the more you run them. Once a loop or method has been called 10,000 times, it should be compiled to native code.

这两个示例运行得越多，它们就会变得越快。一旦循环或方法被调用 10,000 次，就应该将其编译为本机代码。

回答by Alan Meile

If anyone is interested in an iterative Function with array:

如果有人对带数组的迭代函数感兴趣：

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);
}

This solution crashes for input value 0.

此解决方案因输入值而崩溃0。

Reason: The array a will be initialized 0+1=1but the consecutive assignment of a[1]will result in an index out of bounds exception.

原因：数组a会被初始化，0+1=1但是连续赋值a[1]会导致索引越界异常。

Either add an if statement that returns 0on y=0or initialize the array by y+2, which will waste 1int but still be of constant space and not change big O.

添加一个 if 语句返回0ony=0或初始化数组 by y+2，这将浪费1int 但仍然是恒定空间并且不会改变 big O。

回答by Saiful Azad

Why is Recursion slower?

为什么递归比较慢？

When you call your function again itself (as recursion) the compiler allocates new Activation Record(Just think as an ordinary Stack) for that new function. That stack is used to keep your states, variables, and addresses. Compiler creates a stack for each function and this creation process continues until the base case is reached. So, when the data size becomes larger, compilerneeds large stack segment to calculate the whole process. Calculating and managing those Records is also counted during this process.

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

Also, in recursion, the stack segment is being raised during run-time. Compiler does not know how much memory will be occupied during compile time.

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

That is why if you don't handle your Base caseproperly, you will get StackOverflowexception :).

这就是为什么如果您没有正确处理Base case，您将收到StackOverflow异常 :)。

回答by Aldo Infanzon

I prefer using a mathematical solution using the golden number. enjoy

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

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();
}

回答by Varunnuevothoughts

Whenever you are looking for time taken to complete a particular algorithm, it's best you always go for time complexity.

每当您寻找完成特定算法所需的时间时，最好始终选择时间复杂度。

Evaluate the time complexity on the paper in terms of O(something).

根据 O(something) 评估论文的时间复杂度。

Comparing the above two approaches, time complexity of iterative approach is O(n) whereas that of recursive approach is O(2^n).

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

Let's try to find the time complexity of fib(4)

让我们试着找出时间复杂度 fib(4)

Iterative approach, the loop evaluates 4 times, so it's time complexity is O(n).

迭代方法，循环评估 4 次，所以它的时间复杂度是O(n)。

Recursive approach,

递归方法，

                               fib(4)

             fib(3)              +               fib(2)

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

fib(1)  +  fib(0)

so fib() is called 9 times which is slightly lower than 2^n when the value of n is large, even small also(remember that BigOh(O) takes care of upper bound) .

所以 fib() 被调用 9 次，当 n 的值很大，甚至很小时，这比 2^n 略低（记住BigOh(O) 负责upper bound）。

As a result we can say that the iterative approach is evaluating in polynomial time, whereas recursive one is evaluating in exponential time

因此，我们可以说迭代方法正在评估 in polynomial time，而递归方法正在评估 inexponential time

回答by gorros

The recursive approach that you use is not efficient. I would suggest you use tail recursion. In contrast to your approach tail recursion keeps only one function call in the stack at any point in time.

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

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));
    }
}

回答by Chaklader Asfak Arefe

I have a recursive solution that you where the computed values are stored to avoid the further unnecessary computations. The code is provided below,

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

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 );
            } 

        }             
    }