Recursion (computer science): Difference between revisions

Revision as of 18:49, 1 March 2007

Revision as of 18:52, 1 March 2007

Line 40:

'''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_(programming_language)[C]]:

int GCF(int x, int y)

Line 50:

}

The above can be coded to remove the extra modulo; however, it either requires a variable declaration for each level of recursion or an extra recursive call (the base case would be if y = 0, meaning if x mod y = 0 we would make one more call wehereaswhereas here we simply return). All three implementations are valid, only depending on what is most efficient for the language and processor (in C++, modulo is an inline operation so the above is generally fastest, but other languages require a less-efficient Mod(x,y) function call).

Below is the same algorithm using an iterative approach: