# How to increase efficiency of recursion algorithm?

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?

• Welcome to Code Review! The current question title, which states your concerns about the code, applies to too many questions on this site to be useful. The site standard is for the title to simply state the task accomplished by the code. Please see How to Ask for examples, and revise the title accordingly. Also you'll get much better reviews if you post more of the code so that reviewers can see the context. Aug 22 '20 at 12:51

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

• What do you mean with "relying on how integer division works in Java"? Aug 26 '20 at 17:01
• Dividing two integers yields an integer, dividing an integer by a float or the other way round yields a float, same for double. So if you'd happen to have a float/double instead of an integer, you'd get a float/double as result. Just something to be aware of. While we're at it, n /= 10 is shorthand for n = (T)(n / 10), with "T" being that type of n. So if we'd assume n to be an int, and you'd divide by a long n /= 10l the result would be silently truncated to int. Another small detail to be aware of. Aug 27 '20 at 16:25

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.

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.

• This answer does not consider this case: "...except that an 8 with another 8 immediately to its left counts double, so 8818 yields 4." Aug 22 '20 at 18:52
• You are right, I read over that part. I will fix my answer @N.Dogac Aug 22 '20 at 22:31