递归算法 vs 迭代算法

Question

3

我正在实现欧几里得算法，用于找到两个整数的最大公约数（Greatest Common Divisor）。

提供了两个示例实现：递归和迭代。 http://en.wikipedia.org/wiki/Euclidean_algorithm#Implementations 我的问题：

在学校里，我记得我的教授们谈论递归函数时总是很兴奋，但我有一个疑问。与迭代版本相比，递归算法是否占用更多堆栈空间，因此需要更多内存？此外，由于调用函数需要一些初始化开销，递归算法是否比迭代算法更慢？

- Martin Konecny

2

https://dev59.com/FHRB5IYBdhLWcg3w4bKv - N 1.1

2个回答

0

这完全取决于编程语言和编译器。目前的计算机并不是真正针对高效递归而设计的，但有些编译器可以优化某些递归情况，使其运行效率与循环一样高（实际上，在机器代码中它变成了一个循环）。然而，有些编译器则不能。

递归在数学意义上可能更加美丽，但如果你觉得迭代更舒适，那就使用它吧。

- Matti Virkkunen

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Earlz · Accepted Answer

这完全取决于编程语言。如果您的语言支持尾递归(现在许多语言都支持)，那么它们将以相同的速度运行。如果不支持，则递归版本会更慢，并且需要更多(宝贵的)堆栈空间。