如何检查递归或迭代是否最适合特定程序？

Question

在我的大学里,我被要求为Fibonacci系列写一个JAVA程序.我使用递归来编写该程序.

但是,助理讲师说我的算法效率不高,并要求我分析.他补充说,按照惯例,迭代适用于该程序而不是递归.

如何分析我们的算法？如何在迭代和递归中检查空间和时间复杂度？就在这时,我发现这些东西和程序的正确性一样重要.

Answer 1

作为一个thumbrule:

• 对于人类来说,递归很容易理解.但它是基于堆栈的,堆栈总是有限的资源.
• 迭代是顺序的,同时更容易调试.但有时会导致难以理解的算法,这些算法可以通过递归轻松完成.

因此,只要步数受限于可管理的小数量,您就可以进行递归.因为您将确信堆栈永远不会溢出,同时递归代码也是如此compact and elegant.

如果你想探索更多这些可能会有所帮助. 递归vs循环和 递归或迭代？

编辑 正如@MrP所指出的,一些特殊的递归可以由一些编译器进行优化.