CodingBat: Java. Recursion-1, Part I

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

8 thoughts on “CodingBat: Java. Recursion-1, Part I

  1. Kelly

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

    Reply
    1. Gregor Ulm Post author

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

      Reply
      1. Steven

        Those “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.

        Reply
  2. Julie Goode

    Please 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!

    Reply
    1. Anonymous

      Some 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.

      Reply
  3. Amin

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

    Reply

Leave a Reply

Your email address will not be published. Required fields are marked *

Spammer prevention; the answer is an integer: * Time limit is exhausted. Please reload CAPTCHA.