递归与迭代算法 [英] Recursive vs. Iterative algorithms

问题描述

我正在实施Euclidian算法以查找两个整数的GCD(最大公约数).

I'm implementing the Euclidian algorithm for finding the GCD (Greatest Common Divisor) of two integers.

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

Two sample implementations are given: Recursive and Iterative. http://en.wikipedia.org/wiki/Euclidean_algorithm#Implementations

我的问题:

我记得在学校里，我的教授们都在谈论递归函数，就像它们在风行一时一样，但是我有一个疑问.与迭代版本相比，递归算法是否不占用更多堆栈空间并因此占用更多内存?另外，因为调用函数需要使用一些初始化开销，所以递归算法难道不比其迭代方法慢吗?

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?

推荐答案

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

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屋！