Recursive Call - Recursive Programs - Recursive Procedures - Greatest Common Divisor

Greatest Common Divisor

The Euclidean algorithm, which computes the greatest common divisor of two integers, can be written recursively.

Function definition:

\gcd(x,y) = \begin{cases} x & \mbox{if } y = 0 \\ \gcd(y, \operatorname{remainder}(x,y)) & \mbox{if } y > 0 \\ \end{cases}
Pseudocode (recursive):
function gcd is: input: integer x, integer y such that x >= y and y >= 0
1. if y is 0, return x 2. otherwise, return
end gcd

Recurrence relation for greatest common divisor, where expresses the remainder of :

Computing the recurrence relation for x = 27 and y = 9:
gcd(27, 9) = gcd(9, 27% 9) = gcd(9, 0) = 9
Computing the recurrence relation for x = 259 and y = 111:
gcd(259, 111) = gcd(111, 259% 111) = gcd(111, 37) = gcd(37, 0) = 37

The recursive program above is tail-recursive; it is equivalent to an iterative algorithm, and the computation shown above shows the steps of evaluation that would be performed by a language that eliminates tail calls. Below is a version of the same algorithm using explicit iteration, suitable for a language that does not eliminate tail calls. By maintaining its state entirely in the variables x and y and using a looping construct, the program avoids making recursive calls and growing the call stack.

Pseudocode (iterative):
function gcd is:
input: integer x, integer y such that x >= y and y >= 0
1. create new variable called remainder
2. begin loop 1. if y is zero, exit loop 2. set remainder to the remainder of x/y 3. set x to y 4. set y to remainder 5. repeat loop
3. return x
end gcd

The iterative algorithm requires a temporary variable, and even given knowledge of the Euclidean algorithm it is more difficult to understand the process by simple inspection, although the two algorithms are very similar in their steps.

Read more about this topic:  Recursive Call, Recursive Programs, Recursive Procedures

Famous quotes containing the words greatest and/or common:

    “Everybody gets pinched but you did it right. You told them nothing and they got nothing. You learned the two greatest things in life: Never rat on your friends and always keep your mouth shut.”
    —Nicholas Pileggi, U.S. screenwriter, and Martin Scorsese. Jimmy Conway (Robert DeNiro)

    “Why does not the kitten betray some of the attributes common to the adult puss? A puppy is but a dog, plus high spirits, and minus common sense. We never hear our friends say they love puppies, but cannot bear dogs. A kitten is a thing apart; and many people who lack the discriminating enthusiasm for cats, who regard these beautiful beasts with aversion and mistrust, are won over easily, and cajoled out of their prejudices, by the deceitful wiles of kittenhood.”
    —Agnes Repplier (1858–1950)