递归与迭代算法
我正在实现欧几里德算法来查找两个整数的 GCD（最大公约数）。
给出了两个示例实现：递归和迭代。 http://en.wikipedia.org/wiki/Euclidean_algorithm#Implementations
我的问题：
在学校里，我记得我的教授们谈论递归函数，就像它们风靡一时一样，但我有一个疑问。与迭代版本相比，递归算法不会占用更多的堆栈空间，从而占用更多的内存吗？另外，由于调用函数需要使用一些初始化开销，因此递归算法是否比迭代算法更慢？
I'm implementing the Euclidian algorithm for finding the GCD (Greatest Common Divisor) of two integers.
Two sample implementations are given: Recursive and Iterative.
http://en.wikipedia.org/wiki/Euclidean_algorithm#Implementations
My Question:
In school I remember my professors talking about recursive functions like they were all the rage, but I have one doubt. Compared to an iterative version don't recursive algorithms take up more stack space and therefore much more memory? Also, because calling a function requires uses some overhead for initialization, aren't recursive algorithms more slower than their iterative counterpart?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
这完全取决于语言。如果您的语言具有尾部调用递归支持（现在很多人都这样做），那么它们将以相同的速度进行。如果没有，那么递归版本会更慢并且占用更多（宝贵的）堆栈空间。
It depends entirely on the language. If your language has tail-call recursion support(a lot do now days) then they will go at an equal speed. If it does not, then the recursive version will be slower and take more (precious) stack space.
这一切都取决于语言和编译器。当前的计算机并未真正面向高效递归，但某些编译器可以优化某些递归情况，使其与循环一样高效地运行（本质上，它成为机器代码中的循环）。但话又说回来，有些编译器不能。
从数学意义上来说，递归也许更漂亮，但如果您对迭代感觉更舒服，就使用它吧。
It all depends on the language and compiler. Current computers aren't really geared towards efficient recursion, but some compilers can optimize some cases of recursion to run just as efficiently as a loop (essentially, it becomes a loop in the machine code). Then again, some compilers can't.
Recursion is perhaps more beautiful in a mathematical sense, but if you feel more comfortable with iteration, just use it.