CSE143 More Recursion Examples handout #14
// pre : y >= 0
// post: returns x to the y power
public int pow(int x, int y) {
if (y < 0)
throw new IllegalArgumentException("negative power");
else if (y == 0)
return 1;
else
return x * pow(x, y - 1);
}
// pre : y >= 0
// post: returns x to the y power (this version is O(log y))
public int pow2(int x, int y) {
if (y < 0)
throw new IllegalArgumentException("negative power");
else if (y == 0)
return 1;
else if (y % 2 == 0)
return pow2(x * x, y / 2);
else
return x * pow2(x, y - 1);
}
// pre : x >= 0, y >= 0
// post: returns the Greatest Common Divisor of x and y
public int gcd(int x, int y) {
if (x < 0 || y < 0)
throw new IllegalArgumentException();
else if (y == 0)
return x;
else
return gcd(y, x % y);
}
// pre : n >= 0, 0 <= m <= n
// post: returns "n choose m" (number of ways to choose m items from n)
public int combin(int n, int m) {
if (n < 0 || m < 0 || m > n)
throw new IllegalArgumentException();
else if (m == 0 || n == m)
return 1;
else
return combin(n - 1, m) + combin(n - 1, m - 1);
}
// pre : n >= 0, 0 <= m <= n
// post: returns the number of m-permutations of n items (number of ways
// to order m items chosen from n)
public int permut(int n, int m) {
if (n < 0 || m < 0 || m > n)
throw new IllegalArgumentException();
else if (m == 0)
return 1;
else
return n * permut(n - 1, m - 1);
}
The following method "fills" a region of something called a BufferedImage with
the color RED.
public void fill(BufferedImage image, int x, int y) {
if (image.getRGB(x, y) == 0) {
image.setRGB(x, y, Color.RED.getRGB());
fill(image, x - 1, y);
fill(image, x + 1, y);
fill(image, x, y - 1);
fill(image, x, y + 1);
}
}