For further help with Coding Bat (Java), please check out my books. I am also available for tutoring.
Recursion is neat in theory and commonly leads to very clean code. Some people have a hard time understanding it, though. If you’ve ever encountered a recurrence relation in mathematics, then you already know everything there is to know about the “mind-bending” nature of recursive problems.
Otherwise, try this simple strategy. First, you may be tempted to think recursively about recursive functions. This may work with factorials, but for something more complex like, say, the Ackermann function, it’s a recipe for disaster. So, don’t do it! Instead, figure out what the base case consists of. The base case immediately returns a result. All other conditions eventually have to revert to the base case, which means that you’ll return “something” in addition to recursively calling the function, but with an input that brings you closer to the base case.
The first example, factorial, of CodingBat’s Recursion-1 section illustrates this strategy very well. All subsequent problems are rather similar.
All solutions were successfully tested on 24 March 2013.
factorial:
public int factorial(int n) {
if (n <= 1) return 1;
return n * factorial(n - 1);
}
bunnyEars:
public int bunnyEars(int bunnies) {
if (bunnies == 0) return 0;
return 2 + bunnyEars(bunnies - 1);
}
fibonacci:
public int fibonacci(int n) {
if (n <= 1) return n;
return fibonacci(n - 2) + fibonacci(n - 1);
}
bunnyEars2:
public int bunnyEars2(int bunnies) {
if (bunnies == 0) return 0;
if (bunnies % 2 == 1) return 2 + bunnyEars2(bunnies - 1);
return 3 + bunnyEars2(bunnies - 1);
}
triangle:
public int triangle(int rows) {
if (rows == 0) return 0;
return rows + triangle(rows - 1);
}
sumDigits:
public int sumDigits(int n) {
if (n == 0) return 0;
return n % 10 + sumDigits(n / 10);
}
count7:
public int count7(int n) {
if (n == 0) return 0;
if (n % 10 == 7) return 1 + count7(n / 10);
return count7(n / 10);
}
count8:
public int count8(int n) {
if (n == 0) return 0;
if (n >= 88 && n % 100 == 88) return 2 + count8(n / 10);
if (n % 10 == 8) return 1 + count8(n / 10);
return count8(n / 10);
}
powerN:
public int powerN(int base, int n) {
if (n == 0) return 1;
return base * powerN(base, n - 1);
}
countX:
public int countX(String str) {
if (str.length() == 0) return 0;
if (str.charAt(0) == 'x') return 1 + countX(str.substring(1));
return countX(str.substring(1));
}
For further help with Coding Bat (Java), please check out my books. I am also available for tutoring.