Content deleted Content added
Undo revision 98657023 by 202.59.80.55 (talk) |
|||
Line 39:
Factorial := temp
'''end'''
Another comparison that even more clearly demonstrates the relative "elegance" of recursive functions is the [[Euclidean Algorithm]], used to compute the [[greatest common factor]] of two integers. Below is the algorithm with recursion, coded in [[C]]:
int GCF(int x, int y)
{
int r = x % y
if (r == 0)
return y
else
return GCF(y, r)
}
The above can be coded not to use a variable; however, it either requires two modulus operations per non-base case, or an extra recursive call. All three implementations are valid, only depending on what is more efficient for the language and processor.
Below is the same algorithm using an iterative approach:
int GCF(int x, int y)
{
int r
do
{
r = x % y
x = y
y = r
} while (r != 0)
return x
}
The iterative algorithm requires three assignment statements per iteration, and even given knowledge of the Euclidean Algorithm it is more difficult to understand the process by simple inspection.
===Recursion versus iteration===
In the "factorial" example the iterative implementation is likely to be slightly faster in practice than the recursive one. This is almost definite for the Euclidean Algorithm implementation. This result is typical, because iterative functions do not pay the "function-call overhead" as many times as recursive functions, and that overhead is relatively high in many languages. (Note that an even faster implementation for the factorial function on small integers is to use a [[lookup table]].)
There are other types of problems whose solutions are inherently recursive, because they need to keep track of prior state. One example is [[tree traversal]]; others include the [[Ackermann function]] and [[divide-and-conquer algorithm]]s such as [[Quicksort]]. All of these algorithms can be implemented iteratively with the help of a [[stack (data structure)|stack]], but the need for the stack arguably nullifies the advantages of the iterative solution.
| |||