递归与迭代（Fibonacci序列）
我有两种不同的方法，一种是使用迭代计算第n个元素的Fibonacci序列，另一种是使用递归方法做同样的事情。
程序示例如下所示：
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
我真正想知道的是为什么突然迭代变得更快并且递归变得更慢。 如果我错过了这个问题的一些明显答案，我很抱歉，但我仍然是编程的新手，我真的不明白背后会发生什么，我想知道。 请提供一个很好的解释或指出我正确的方向，以便我自己找到答案。 另外，如果这不是测试哪种方法更快的好方法，请告诉我并建议我使用不同的方法。
提前致谢！
对于简洁性，设F（x）为递归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次……依此类推
因此，对于更大的输入，树变得越来越大。
本文对递归和迭代进行了比较，并介绍了它们在生成斐波那契数字时的应用。
如文章所述，
性能不佳的原因是在每次递归调用的不良级别中寄存器的大量推送弹出。
这基本上说递归方法有更多的开销。
另外，看看Memoization
在执行fibonacci算法的递归实现时，您通过一遍又一遍地重新计算相同的值来添加冗余调用。
fib(5) = fib(4) + fib(3) fib(4) = fib(3) + fib(2) fib(3) = fib(2) + fib(1)
注意，对于fib(4)和fib(3)将对fib(2)进行冗余计算。 然而，这可以通过一种称为Memoization的技术来克服，该技术通过存储您计算过一次的值来提高递归斐波那契的效率。 对于已知值的进一步调用fib(x)可以用简单的查找替换，从而不需要进一步的递归调用。
这是迭代和递归方法之间的主要区别，如果您感兴趣，还有其他更有效的计算斐波纳契数的算法 。
为什么递归较慢？
当您再次调用函数（作为递归）时，编译器会为该新函数分配新的激活记录 （只是认为是普通的堆栈）。 该堆栈用于保存您的状态，变量和地址。 编译器为每个函数创建一个堆栈，此创建过程将继续，直到达到基本案例。 因此，当您的数据大小变大时， 编译器需要大堆栈段来计算整个过程。 在此过程中还会计算和管理这些记录。
此外，在递归中，堆栈段在运行时期间被引发 。 编译器不知道在编译期间将占用多少内存 。
这就是为什么如果您无法正确处理Base案例，您将遇到名为StackOverflow的着名错误:)。
以你的方式使用递归，时间复杂度是O(fib(n)) ，这是非常昂贵的。 迭代方法是O(n)这没有显示，因为a）你的测试非常短，代码甚至不会被编译b）你使用的是非常小的数字。
运行它们越多，两个示例都会变得越快。 一旦循环或方法被调用10,000次，它应该被编译为本机代码。
如果有人对使用数组的迭代函数感兴趣：
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]将导致索引超出范围exception。
添加一个在y=0返回0的if语句或者用y+2初始化数组，这将浪费1 int但仍然是恒定的空间而不是更改大O
我更喜欢使用黄金数字的数学解决方案。 请享用
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(); }
您使用的递归方法效率不高。 我建议你使用尾递归。 与您的方法相反，尾递归在任何时间点都只在堆栈中保留一个函数调用。
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)); } }
无论何时您正在寻找完成特定算法所需的时间，最好总是追求时间复杂性。
根据O（某事）评估论文的时间复杂度。
比较上述两种方法，迭代方法的时间复杂度为O（n），而递归方法的时间复杂度为O（2 ^ n）。
让我们试着找出fib(4)的时间复杂度fib(4)
迭代方法，循环计算4次，因此它的时间复杂度为O(n) 。
递归方法，
fib(4) fib(3) + fib(2) fib(2) + fib(1) fib(1) + fib(0) fib(1) + fib(0)
因此，当n的值很大时，fib（）被调用9次，稍微低于2 ^ n，甚至也很小（记住BigOh （O）负责upper bound ）。
结果我们可以说迭代方法是在polynomial time评估，而递归方法是在exponential time评估
我有一个递归解决方案，您可以在其中存储计算值，以避免进一步不必要的计算。 代码如下，
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 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 ); } } }