Java - Recursive solving with check number

Question

I'm stuck with an exercise involving recursion

The question:

Write a recursive function which returns an integer, the "check digit". This check digit is computed by calculating the sum of all digits from the passed-in integer. However, if the result is greater than or equal to 10 (i.e., more than a single digit), then the calculation should be performed again using the result as input. And thus until the final number returned will be a single digit; this digit is the "check digit".

An Example:

With the number 869419 ----> 8+6+9+4+1+9 = 37 --> 3+7 = 10 -> 1.

*The Closest Solution I've reached : *

public static int Bik (int n) {
    int sum=0;
    if (n/10 == 1 || n==1) {
        return 1;
    }
    else {
        if (n%10 != 0) {
            return Bik((n/10) + (n%10));
        }
        return (n);
    }
}

public static void main(String[] args) {
    System.out.println(Bik(1892));
}

Answer 1

You have one problem on line 1 of your Bik Method:

Every time you call it the variable sum is defined to 0 so it never changes. Also in your code you never actually sum the value from the previous iteration. The solution I can come with is to pass another parameter with the sum of the previous iteration:

public static int Bik (int n, int sum) {
    // You get the value of the last digit and sum it to your total
    sum += n%10;
    // This validation is to know if there is only 1 digit left  
    if (n>9) 
        // The required recursion
        return Bik(n/10, sum); 
    //In case the sum is higher than 9 the recursion is called again, otherwise it returns the sum
    return sum>9 ? Bik(sum, 0) : sum;
}

public static void main(String[] args) {
    System.out.println(Bik(1892, 0));
}

Please note this solution also works for numbers in which the recursion has to run more than once like 189235. Also I used a ternary operator. You can learn more about it here but if you don't like it you can use a regular if statement as well

Answer 2

First you need to check if the input is bigger than 10 otherwise just return the input.

if(input < 10) { //no computation required return input
     return input;
}

Then if input is bigger than 10. You need to obtain every digits composing the input. To obtain a digit just make a modulo 10 input%10. This will give you the last digit. Then divide the input by 10 and redo the operation to obtain the next digit. Repeat this until input is lower than 10. Here you've obtain all the digit

while(input > 9) { // until input is lower than 10
    int newDigit = input % 10; //find a digit
    digits.add(Integer.valueOf(newDigit);  //ass it to a list
    input /= 10;  //reduce input
}
digits.add(Integer.valueOf(input)); //add the last input digit

After you have to sum all the element in the list to obtain your result

for(Integer i : digits) { //sum all digits
    result += i;
}

Finally return the computation of this result. By doing this you use recursivity, if result is lower than 10 it will be return, if it's greater it will be computed again.

return compute(result); // return the computed result

The total of these steps should give you something like :

public int compute(int input) {
    if(input < 10) { //no computation required return input
         return input;
    } else {
        List<Integer> digits = new ArrayList<Interger>(); //will contains the digit composing input
        int inComputationInt = input; //a copy of input that will be modified
        int result = 0; //the resulting sum of digit

        while(inComputationInt > 9) { //obtain every digit in input
            int newDigit = inComputation % 10;
            digits.add(Integer.valueOf(newDigit));
            inComputation /= 10;
        }
        digits.add(Integer.valueOf(inComputation);

        for(Integer i : digits) { //sum all digits
            result += i;
        }

        return compute(result); // return the computation of result
    }
}

Answer 3

After your edit - now much clearer.

int checkDigit(int n) {
    // Any single-digit is the check digit.
    if (n < 10) return n;
    // More than one digit - add them up.
    String digits = Integer.toString(n);
    int sum = 0;
    for (int i = 0; i < digits.length(); i++) {
        sum += digits.charAt(i) - '0';
    }
    // Check that sum.
    return checkDigit(sum);
}

private void test(int n) {
    System.out.println("Check difgit for "+n+" = "+checkDigit(n));
}

public void test(String[] args) {
    int[] tests = {86941,869419,189,1892};
    for(int n: tests) {
        test(n);
    }
}

Answer 4

public int digitSum(int n) {
 if(n < 10) return n;
 return n % 10 + digitSum(n / 10);
}

First of all you need a base case and in this case it's the number you provide and if it's less than 10 just return the given number.

The second return statement takes the rightmost digit (modulo calculation n % 10) and saves it to its stack, and then call the method again but with (n / 10) and this calculation removes the rightmost digit because you already used it in the modulo calculation so you don´t need it anymore. Pass the new number into the method and repeat this process until your number is less than 10.

Hopes this clarifies a little bit.

Answer 5

include this method to your code, pass the digit to digitSum

static int digitSum(int n)
{
    int sum = 0;

    // Loop to do sum while
    // sum is not less than
    // or equal to 9
    while (n > 0 || sum > 9) 
    {
        if (n == 0) {
            n = sum;
            sum = 0;
        }
        sum += n % 10;
        n /= 10;
    }
    return sum;
}