I am writing a method that counts the number of duplicates in an array. I understand how to write it using a for loop, but I need to write it recursively.

public static int countDuplicates(String[] input) {
    //needs to be recursive
    int count = 0;
    if (input == null) {
        return 0;
    } 
    for (int i = 0; i < input.length - 1; i  ) {
        if (input[i] == input[i   1]) {
            count  ;
        } else {
            count  =0;
        }
    }
    
    return count; 
} 

The input is assumed to be in lexicographic order.

input : {"A", "A", "B", "C", "C", "C", "D"}

output : 3

How do I convert this for loop to a recursion?

CodePudding user response：

I believe someone have missed to call Arrays.sort(input); and comparison input[i] == input[i 1] is not correct in case of java.lang.String.

correct iterative:

    public static int countDuplicatesIterative(String[] input) {
        if (input == null) {
            return 0;
        }
        Arrays.sort(input);
        int count = 0;
        for (int i = 0; i < input.length - 1; i  ) {
            if (input[i].equals(input[i   1])) {
                count  ;
            }
        }
        return count;
    }

recursive (assuming that request to turn loop into recursion actually assumes tail recursion):

    public static int countDuplicatesRecursive(String[] input) {
        if (input == null) {
            return 0;
        }
        Arrays.sort(input);
        return doCountDuplicatesRecursive(input, 0, 0);
    }

    public static int doCountDuplicatesRecursive(String[] input, int position, int cnt) {
        if (position == input.length - 1) {
            return cnt;
        }
        if (input[position].equals(input[position   1])) {
            cnt  ;
        }
        return doCountDuplicatesRecursive(input, position   1, cnt);
    }

CodePudding user response：

1. You can't use == to compare String type or Java reference types.

2. Resursion solution

    public class CountDuplicatesApp {
   
        public static int countDuplicates(String[] input) {
            if (input == null)
                throw new IllegalArgumentException("input must be provided");
   
            return countDuplicates(input, input.length);
        }
   
        static int countDuplicates(String[] input, int len) {
            if (len < 2)
                return 0;
   
            if (len == 2) {
                return Objects.equals(input[0], input[1]) ? 1 : 0;
            }
   
            // Recursion formula:
   
            // countDuplicates(input, len) = countDuplicates(input, len - 1)  
            // input[len-2] == input[len-1] ? 1 : 0
   
            return countDuplicates(input, len - 1) 
                (Objects.equals(input[len - 2], input[len - 1]) ? 1 : 0);
        }
   
        public static void main(String[] args) {
   
            String[] inputs = new String[] { "A", "A", "B", "C", "C", "C", "D" };
            System.out.println(countDuplicates(inputs)); // Output 3
        }   
    }
   

CodePudding user response：

As the question states the assumption that the input is already in the lexicographical order, the sorting is not necessary. However, the question does not provide the precise definition of the lexicographical order itself, so my assumption is that it is cease insensitive and that it does not take Unicode variants into account, so the equalsIgnoreCase() String method would be more appropriate then plain equals(). Also, the assumptions are that input is nicely defined in the sense that nulls are not allowed anywhere:

public static void main(String[] args)
  {
    String[] inputs = { "A", "A", "B", "C", "C", "C", "D" };

    System.out.println(countDuplicates(inputs, 0));
  }

private static int countDuplicates(String[] inputs, int start)
  {
    /*  Assumption #1 : input list is well defined
     if(inputs==null)
       return 0;
     */
    if(start<inputs.length-1)
      {
        /* Assumption #2 : elements of the list are well defined 
        if(inputs[start]==null)
          return 0;
        */
        /* Assumption #3 : Upper vs Lower Case as well as Unicode versions do not matter 
        if(inputs[start].equals(inputs[start 1]))
        */
        if(inputs[start].equalsIgnoreCase(inputs[start 1]))
          return 1 countDuplicates(inputs, start 1);
        else
          return countDuplicates(inputs, start 1);
      }
    else
      return 0;
  }

p.s. countDuplicates(String[], int) can be wrapped inside the countDuplicates(String[]) method if user should not be exposed/overtaxed in providing a 0 as a starting point ;-)