递归算法与迭代算法
递归算法与迭代算法
提问于 2010-04-15 06:10:18
我正在实现寻找两个整数的GCD (最大公约数)的欧几里得算法。
给出了两个示例实现:递归和迭代。http://en.wikipedia.org/wiki/Euclidean_algorithm#Implementations
我的问题是：
在学校，我记得我的教授们谈论递归函数，好像它们都很流行，但我有一个疑问。与迭代版本相比，递归算法不会占用更多的堆栈空间，从而占用更多的内存吗？此外，因为调用函数需要使用一些初始化开销，所以递归算法不是比它们的迭代对应算法更慢吗？
回答 2
Stack Overflow用户
回答已采纳
发布于 2010-04-15 06:13:50
这完全取决于语言。如果您的语言支持尾部调用递归(现在很多都是这样)，那么它们将以相同的速度运行。如果不这样做，那么递归版本将变得更慢，并占用更多(宝贵的)堆栈空间。
Stack Overflow用户
发布于 2010-04-15 06:14:00
这完全取决于语言和编译器。当前的计算机并不是真正适合高效的递归，但一些编译器可以优化某些情况下的递归，使其像循环一样高效地运行(本质上，它变成了机器代码中的循环)。然而，有些编译器不能。
递归在数学意义上可能更美，但如果你觉得迭代更舒服，那就使用它吧。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/2641414
复制相关文章
相似问题
腾讯云开发者
