递归与迭代(斐波那契数列)

本文介绍了递归与迭代(斐波那契数列)的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

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

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

程序示例如下所示:

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, fibIteration(n)); System.out.printf("Time: %d ms ", 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, fibRecursion(n)); System.out.printf("Time: %d ms ", 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); } }

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

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 nth element increases recursion becomes slower and iteration becomes faster. Here are the three different results for three different 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

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

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.

提前致谢！

推荐答案

为了简洁，让 F(x) 成为递归斐波那契数列

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

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次..依此类推

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

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

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