Digital root recursive function

Question

Haven't any experience writing recursive functions.(Generally tend to avoid them - not sure if that's a negative). What do you think about the following?

This is also my first time using JUnit, I'd appreciate input if I'm doing something wrong there.

Challenge: Create a digital Root Function.

Specifications:
A digital root is the recursive sum of all the digits in a number.
Given n, take the sum of the digits of n.
If the resulting value has two digits, continue reducing until a single-digit number is produced.
This is only applicable to the natural numbers.

Solution:

public static int getDigitalRoot(int num) {
        if (Integer.toString(num).length() == 1) { return num; }
        int result = 0;

        for (char c : Integer.toString(num).toCharArray()) {
            result += Character.getNumericValue(c);
        }
        
        return getDigitalRoot(result);    
    }

Tests:

@Test
    public void Tests() {
      assertEquals(6 , Utilities.getDigitalRoot(942));
      assertEquals(7, Utilities.getDigitalRoot(16));
    }

Answer 1

With a bit of knowledge of modular math then you can know that for numbers > 0 getDigitalRoot(n)== n%9 except when dividable by 9 then it is 9.

This simplifies the algorithm a bit.

public static int getDigitalRoot(int n) {
    if(n==0) 
        return 0;
    if(n%9 == 0) 
        return 9;
    return n%9;
}

If you still want the looped version you can do a variation; instead of using another variable to hold the result and retrying until smaller than 10 just do this:

while (num >= 10) {
    num = num/10 +num % 10;
}

It works for roughly the same reason as the first modulo operation.

Answer 2

Good old String processing for digit extraction.... Don't do that.

You're making this quite complicated for yourself. Instead of using your (quite well written) for loop over a String to get the digits of an integer, consider using modulo:

while (num > 1) {
    result += num % 10;   // extract least significant digit
    num = (int) num / 10; // and then remove it
}

This should give you quite some speedup compared to your string conversions

Answer 3

4 things to focus on here:

1. Naming
2. Recursion
3. Primitives
4. Validation

Naming

get* methods in Java are a signal to programmers that you are returning a property on the instance. You get a Name, a value, a property.

In your case, though, you are computing something based on an input value. A name like:

public static int computeDecimalRoot(int value)

would be much better.

Validation

It would be trivial to break your code by giving it a negative value as input.

Testing for a negative value, and throwing an exception, would be acceptable, but determining the abs value of it would also be a good start, but, note that would cause a stack-overflow for the input value Integer.MIN_VALUE because you cannot calculate the absolute-value of that.... A different trick would be needed there.

Primitives

Keeping values as primitives int instead of Integer (or worse, String) is a very important factor with performance. When Java 9 or Java 10 arrives, this may change, but it is not there yet.

Recursion

Recursion is an elegant solution to a number of problems in computing. In general though, it is important to separate the three components of all recursive structures in to discrete logic points.

All recursive structures consist of:

1. A test to see if recursion is needed
2. A recursive function call
3. A computation for the current recursive level.

Sometimes the terminal test is done to create a conditional recursive call.

Other times, the terminal test is done as a 'gating' step in the method.

In your code, you use the gating method. This is a good choice, but it should be more obvious. In part, it's hidden by the complicated condition with the String conversions and 1-liner return.

In order to accommodate odd situations with massive negative values, I would consider the terminal condition:

if (num < 10 && num > -10) {
    return Math.abs(num);
}

That satisfies the conditions of negative input values, and has no integer/string/integer conversions.

The next part of the process is naturally the summing of the digits. By using simpler logic using modulo and division (as has been shown in other answers), you can compute the sum easier:

int sum = 0;
while (num != 0) {
    // abs needed to cope with negative input values
    sum += Math.abs(num % 10);
    num /= 10;
}

That code is safe for any input value. It does extra work computing the abs of each modulo, but the problem is that, for the input Integer.MIN_VALUE you cannot calculate the abs.... so you need tricks.

Now, the third part of the recursion, is to call the recursive method with the sum:

 return computeDigitalRoot(sum);

General

I am not happy with the variable name num, it is too similar to sum which I also use.

I have the code here in Ideone too:

private static int computeDigitalRoot(int num) {

    if (num < 10 && num > -10) {
        return Math.abs(num);
    }

    int sum = 0;
    while (num != 0) {
        // abs needed to cope with negative input values
        sum += Math.abs(num % 10);
        num /= 10;
    }

    return computeDigitalRoot(sum);
}

Note how the recursion stages are obvious - the terminal check, the work, and the recursive call.

Answer 4

Rather than doing

if (Integer.toString(num).length() == 1) { return num; }

You can just check

if (num < 10) { return num; }