递归与迭代（Fibonacci序列） [英] Recursion vs. Iteration (Fibonacci sequence)
问题描述
我有两种不同的方法，一种是使用迭代计算Fibonacci序列到 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", 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);
}
}
我试图找出哪种方法更快。我得出的结论是，对于较小的数字，递归更快，但随着 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.
提前致谢！
Thanks in advance!
推荐答案
对于简洁性，设F（x）为递归Fibonacci
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.
这篇关于递归与迭代（Fibonacci序列）的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
