Recursive vs. Iterative algorithms

Question

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?

Answer 1

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.

Answer 2

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.