代码之家 › 专栏 › 技术社区 › Martin Konecny

递归与迭代算法

iteration recursion

2

Martin Konecny · 技术社区 · 15 年前

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

我的问题:

在学校里,我记得我的教授们谈论递归函数的时候都很愤怒,但我有一个疑问。与迭代版本相比,递归算法不会占用更多的堆栈空间,从而占用更多的内存吗?另外,由于调用函数需要一些初始化开销,递归算法是否比迭代算法慢?

2 回复 | 直到 15 年前

1

3

Earlz 15 年前

这完全取决于语言。如果您的语言有尾调用递归支持(现在很多时候都有),那么它们将以相同的速度运行。如果不这样做,那么递归版本将变慢并占用更多(宝贵)堆栈空间。

2

0

Matti Virkkunen 15 年前

这完全取决于语言和编译器。当前的计算机并没有真正面向高效递归,但是一些编译器可以优化某些递归情况,使其像循环一样高效地运行(本质上,它成为机器代码中的循环)。同样,有些编译器不能。

在数学意义上,递归可能更漂亮,但是如果你觉得迭代更舒服,就用它吧。