Validating an Armstrong number using Recursion in Java

Question

I have to check whether a number is an Armstrong number or not, using a recursive method.

public class ArmStrong {

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

    static boolean isArm(int n,int last,int sum) {
        if (n <= 0 ) {
            if (sum == n) {
                return true;
            } else {
                return false;
            }
        }
        return isArm(n / 10, n % 10,sum + last * last * last);
    }
}

When I debug, in the last call of isArm when n is 4, the base statement is skipped.

Answer 1

Your code will instantly jump to the answer (if (n <= 0)) before applying the cube of the last digit.

For example, trivially, let's try 9, which obviously isn't armstrong.

Your code will first check if 9 is 0 - it's not. So, we recurse, which will go with self(0, 9, 0+0). The next run is supposed to then recurse once more, so that the sum + last*last*last can actually get some cubing done. But it'll never get there - n is 0, so, you jump into the if.

As your variable name kinda gives away last is referring to the digit that the previous run lopped off, and yet you aren't cubing it.

The solution is to simply get the cubing in before checking if n is null:

The first thing your method should do is

sum += last*last*last;

Then, the second problem shows up: This correctly calculates your sum to be 407, but you check this against n, which is, obviously, 0 - you are 'destroying' n as you go through. One trivial way to solve that is to pass the original n, unmolested, through, as a 4th parameter. I'll leave that as an exercise for the reader.

Answer 2

Although @rzwitserloot has pointed at an issue which is rooted in the way you've designed the recursion, the problem is still not resolved.

Yes, the recursive calls go "one step ahead" the calculation of the sum of digits, which happens in the Recursive case, and the left-most digit of the given number doesn't contribute the sum, since n is zero and recursion hits the Base case. That's true, but it's not the only thing you need to fix.

Here's the definition of so-called Narcissistic numbers (aka Armstrong numbers):

In number theory, a narcissistic number (also known as a pluperfect digital invariant (PPDI), an Armstrong number (after Michael F. Armstrong)or a plus perfect number) in a given number base b b is a number that is the sum of its own digits each raised to the power of the number of digits.

Therefore, a method with hard-coded power of 3 is capable to validate only three-digit Armstrong numbers. There are only few of them, for other valid Armstrong numbers it would produce an incorrect result.

So, before calculating the sum you need to know the numbers of digits there's no workaround. If you want to address the problem only by using Recursion, the numbers of digits can be also calculated recursively. If we take this route, the solution boils down to implementing two recursive methods.

That's how it might look like:

public static boolean isArm(int n) {
    return n == getSum(n, getDigitCount(n));
}

public static int getSum(int n, int power) {
    return n == 0 ? 0 : (int) Math.pow(n % 10, power) + getSum(n / 10, power);
}

public static int getDigitCount(int n) {
    return n == 0 ? 0 : 1 + getDigitCount(n / 10);
}

main()

public static void main(String[] args) {
    System.out.println(isArm(10));  // is not an Armstrong number
    System.out.println(isArm(21));  // is not an Armstrong number
    System.out.println(isArm(407)); // is an Armstrong number
    System.out.println(isArm(153)); // is an Armstrong number
    System.out.println(isArm(9));   // is an Armstrong number
}

Output:

false // 10
false // 21
true  // 407
true  // 153
true  // 9