How to increase efficiency of recursion algorithm?

Question

The question is:

Given a non-negative int n, compute recursively (no loops) the count of the occurrences of 8 as a digit, except that an 8 with another 8 immediately to its left counts double, so 8818 yields 4. Note that mod (%) by 10 yields the rightmost digit (126 % 10 is 6), while divide (/) by 10 removes the rightmost digit (126 / 10 is 12).

count8(8) → 1 count8(818) → 2 count8(8818) → 4

My solution looked something like this:

public int count8(int n) {
  if(n == 0)  return 0;
  
  int faith = count8(n/10);
  int c = 0;
  if(n%10 == 8){
    n /= 10;
    if(n%10 == 8){
      c++;
    }
    c++;
  }
  return c + faith;
}

Is there any way I can remove the multiple if conditions and make this cleaner and more efficient?

Answer 1

Variable names. Name your variables after what they do, no exceptions.

---

As a sidenote, note that that you're relying on how integer division works in Java.

---

Having said that, you can improve the code by being explicit.

// As I've said, always name your variables and functions after
// what they are doing. Don't be afraid to use longer names,
// longer names which tell you what the class does are a good
// thing, even if they sound "funny".
public int countEights(int value) {
    // Early exit conditions are a good thing.
    if(value == 0) {
        return 0;
    }
    
    // We could also skip the declaration and instead return
    // the right count together with the function call. From
    // the viewpoint of the JVM it doesn't make a difference,
    // but here in the code it means that we have the logic
    // for stripping the last digit only once.
    int countedEights = 0;
    
    // We are testing explicitly for the mentioned "double eights",
    // this has the upside that the intent is clearly visible
    // when reading the code.
    if ((value % 100) == 88) {
        countedEights = 2;
    } else if ((value % 10) == 8) {
        countedEights = 1;
    }
    
    // And finally we call the function again in the return
    // statement, as it is easier to follow the recursion when
    // it is being called at the end of the function.
    return countedEights + countEights(value / 10);
}

As you can see, we can completely get rid of the nested if by being explicit about our intent.

Answer 2

When dealing with recursion, its important to note down what your base and recursive cases are and go from there. These different cases will essentially become the structure of your function.

You've already figured out the different cases for your problem:

1. If n == 0
2. If 8 is in the ones digit place (n % 10 == 8)
3. If 8 isn't in the ones digit place (n % 10 != 8)

If n == 0, then we just return 0.

If n % 10 == 8, then we know we have one 8, but we need to call count8 again with n / 10 as our input parameter to count8. When we return out of this call, we add 1 to our result before returning it since we had already found one 8. Now add 1 (the 8 we already found) to the result of the count8 call.

• In this case, you will want to check if the next digit is an 8 as well. If it is, then you will want to increment your result by 1 before you return. You can do this before or after the first recursive call. Just make sure to pass in n / 10 after you've "removed" the back-to-back 8's.

If n % 10 != 8, then we simply call count8 with n / 10 as our input parameter and return the result from this call.

Hopefully this paints a picture in how you can structure your function in a clearer way.