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)); }

KellyAlso working

count8:

public int count8(int n) {

if (n == 0) {

return 0;

}

if ((n/10%10 ==8) && (n % 10 == 8)) {

return 2 + count8(n / 10);

}

if (n%10 == 8){

return 1 + count8(n/10);

}

return count8(n/10);

}

Gregor UlmPost authorThat’s just a more verbose version of the exact same code I posted, with redundant parentheses and curly braces.

StevenThose “redundant parentheses and curly braces” are actually helpful to some students’ understanding of how the code works. To them, these are visual distinctions are helpful in actually understanding a line’s purpose.

Yes, in terms of practicality they aren’t necessary, but if it were a student trying to check to the solution, it is Kelly’s solution that will be more useful. You have to keep in mind that Coding Bat is designed for beginners.

Julie GoodePlease don’t post all these answers. Can you just post a hint or just one solution? This is so frustrating …

It really defeats the purpose set out by coding bat. They already offer hints and they give whole solutions in some sections! Please remove!

AnonymousSome of us were not fortunate enough to take AP CS in high school and appreciate that Mr. Ulm has provided answer when we are stuck. Please keep these posted. Thanks.

brenNobody is forcing you to look at these solutions

AminThanks for your effort 🙂

but i guess you can solve count8 like this

public int count8(int n) {

if(n == 0) return 0;

if(n % 100 == 88) return 2 + count8(n / 10); // NO NEED TO CHECK N >= 88

if(n % 10 == 8) return 1 + count8(n / 10);

return count8(n / 10);

}

Alanon sumDigits you can also set up the basic case as

if (n<10) return n;