recursion - 递归与迭代算法

Question

我正在实现欧几里德算法来寻找两个整数的 GCD(最大公约数)。

给出了两个示例实现:递归和迭代。 http://en.wikipedia.org/wiki/Euclidean_algorithm#Implementations

我的问题:

在学校里，我记得我的教授们谈论递归函数时好像它们风靡一时，但我有一个疑问。与迭代版本相比，递归算法不会占用更多堆栈空间并因此占用更多内存吗？此外，因为调用函数需要使用一些初始化开销，递归算法不是比迭代算法更慢吗？

Answer 1

这完全取决于语言。如果你的语言有尾调用递归支持(现在很多)，那么它们将以相同的速度进行。如果没有，那么递归版本会更慢并且占用更多(宝贵的)堆栈空间。