[2] The recursive function g is defined as follows:
int g(int x, int y) {
if (x == y)
return x; # Line 3
else if (x < y)
return g(x, y - x); # Line 5
return g(y, x); # Line 7
}
What does g(10,6) return?
g(10,6)
return g(6, 10)
# line 7
return g(6, 4)
# Line 5
return g(4,6)
# Line 7
return g(4,2)
return g(2,4)
return g(2,2)
return
g(2,0)
return 2 # Line 3
This is Euler's algorithm to find the Greatest Common Divisor.
This is the oldest know description of an algorithm we know.
- jdp
