Add 1 to a number represented as an array of digits, using recursion

Question

Given a non-negative number represented as an array of digits, plus one to the number. The digits are stored such that the most significant digit is at the head of the list.

Explanation for using array vs ArrayList:

I could have used ArrayList and that would have been simpler while appending a 1 at the beginning but I wanted to use arrays only as the functions declarations were given and I didn't want to keep converting list to array and vice versa there by adding another O(n) operation.

Any feedback is appreciated. I know there are similar questions in other languages and using iterative approach, but I want feedback on my particular approach.

public class plusOne {

    public static void main(String args[]){
        plusOne obj = new plusOne();
        int[] digits = {0};
        int[] result = obj.plusOne(digits);
        System.out.println(Arrays.toString(result));
    }

    public int[] plusOne(int[] digits) {
        int length = digits.length-1;
        return increment(digits, length);
    }

    public int[] increment(int [] digits, int index) {
        if(digits[index]!=9)
        {
            digits[index]+=1;
            return digits;
        } else {
            if(index==0) {
                int[] newDigits = Arrays.copyOf(digits,digits.length+1);
                newDigits[digits.length] = 0;
                newDigits[index]=1;
                return newDigits;
            }
            digits[index] = 0;
            return increment(digits, index-1);
        }
    }
}

Answer 1

First of all, please be consistent: int[] digits is the norm, but you also wrote String args[] and int [] digits. Classes are normally named with an initial uppercase (PlusOne). It is also customary to put a space before and after binary operators and after each comma, as well as after the if keyword.

There isn't any point in instantiating a plusOne object, when all you want is a function. Therefore, you should have public static int[] plusOne(int[] digits). The increment function is a helper; it should be private static int[] increment(…).

It's weird that the operation usually operates on the array in place, but sometimes writes "junk" to that array then returns a new one. Perhaps that is a consequence of the nature of the problem, but it's an issue that should be clearly documented in JavaDoc.

In Java, it is usually preferable to avoid recursion (due to concerns about stack overflow and performance) if the problem can also be easily solved using iteration — as this problem can. If you do use recursion, though, I recommend structuring the code to make it more obvious that there are two base cases and one recursive case. The way the index == 0 case sets newDigits[digits.length] = 0 feels weird: it doesn't work locally the way recursion should. If you're going to make the assumption that it's OK to plop a 0 at the end, you might as well assume that you want a 1 followed by 0s everywhere else, in which case you could just do new int[digits.length + 1].

public class PlusOne {

    private PlusOne() {}  // Suppress the default constructor

    /**
     * Adds one to an integer that is represented as an array of digits
     * (most-significant digit first).
     *
     * @return The returned array may or may not be the same array
     *         as the input.  In either case, the contents of the
     *         input array will be overwritten.
     */
    public static int[] plusOne(int[] digits) {
        return increment(digits, digits.length - 1);
    }

    private static int[] increment(int[] digits, int index) {
        if (digits[index] != 9) {
            digits[index] += 1;
            return digits;
        } else {
            digits[index] = 0;
            if (index > 0) {
                return increment(digits, index - 1);
            } else {
                int[] newDigits = new int[digits.length + 1];
                newDigits[0] = 1;
                return newDigits;
            }
        }
    }
}