Check if 2 arrays have (exactly) the same elements recursively

Question

I've been given a homework assignment to make a function to check whether 2 given arrays with the same given size have exactly the same set of elements.

My function seems to be working but I feel like I don't use the principles of recursion properly in my function.

I'm not allowed to use dictionary like data structures or sorts of all kinds.

Could you think of a simpler recursive approach to this problem?

bool sameElements(int Arr1[], int Arr2[], int size) {
 bool found; // flag to indicate whether element from Arr1 has been found in Arr2 
 found = false;
 //base case
 if (size == 1) {
 if (Arr1[0] == Arr2[0]) 
 return true;
 else
 return false;
 }//if
 else { //size != 1
 int i; //index for loop
 for (i = size - 1; i >= 0 && !found ; i--) {
 if (Arr2[i] == Arr1[size-1]) { // check existence of element in Arr1
 swapInArray(Arr2, i, (size - 1)); // swap elements
 found = true; 
 }//if
 }//for
 if (found)
 sameElements(Arr1, Arr2, size - 1); // send to recursion with size-1
 else
 return false;
 }//else
}//sameElements
void swapInArray(int arr[], int i, int j) {
 int temp; // temp value to hold arr[i]
 temp = arr[i];
 arr[i] = arr[j];
 arr[j] = temp;
 }//swapInArray

• nwp: Why does your function swap elements? When checking if 2 arrays have the same elements the arrays should not change.
• lex82: The arrays are considered as multi sets
• RippeR: Are you sure exactly the same elements doesn't mean they are in same order too? It would have made much more sense as recursion practice to just check 1st element of both if its same, and if so then check rest (and if not, return false). If you are sure, then it's pretty good solution.
• Klaymen: @RippeR Yes, the order of the elements in the arrays does not matter.

Answer 1

I think the general approach is good. The function is a bit simpler when you take size == 0 as the base case. I also reformatted your code a bit and removed unnecessary comments:

bool sameElements(int Arr1[], int Arr2[], int size) {
 if (size == 0) {
 return true;
 }
 for (int i = size - 1; i >= 0; i--) {
 if (Arr2[i] == Arr1[size-1]) { 
 swapInArray(Arr2, i, (size - 1)); 
 return sameElements(Arr1, Arr2, size - 1) 
 }
 }
 return false;
}
void swapInArray(int arr[], int i, int j) {
 int temp = arr[i];
 arr[i] = arr[j];
 arr[j] = temp;
}

Some things I recommend to make your code easier to read:

• Use comments only if they are really needed. Usually a comment is and indicator that something can be expressed more clearly in the code itself.

• Join declarations and assignments. E.g. int temp = arr[i] instead of two separate lines.

• Declare variables where they are used. In your original code bool found = false could be moved inside the block containing the for loop.

• Make use of the ternary if-operator, [boolean expression] ? [true part] : [false part] to compact your code where appropriate. This is of course also a matter of personal taste, but I think in this particular case it improved readability of the code.

• Klaymen: Actually, this format of commenting is encouraged by my instructor. I will follow your advice on everything else. Thanks.
• lex82: Ok, I see, then you will have to do it. However, I think I can say that this is generally considered bad practice nowadays. Instead your methods and blocks should be short enough to see how brackets match.

Answer 2

Boolean return anti-pattern

It is a very common over-complication beginner make to write:

if (cond) {
 return true;
else {
 return false;
}

When all you need is:

return cond;

So the block:

if (Arr1[0] == Arr2[0]) 
 return true;
else
 return false;

becomes:

return Arr1[0] == Arr2[0];

Never comment when a block closes

Things like:

}//else

are not ok. If you need them to keep track of the code, your code has overly long blocks, and the problem must be fixed at its source.

Answer 3

Swapping

I suspect the problem is more the same elements in the same order? That lends itself naturally to a recursion which I will discuss in a minute. Regardless, your sameElements function should not modify the input arrays! That would be very surprising to your users. In fact, you should explicitly forbid yourself from modifying the input arrays by taking them as const:

bool sameElements(const int* Arr1, const int* Arr2, int size);

Note that taking an argument as an array is the same as taking an argument as a pointer - prefer the pointer.

Base case

The base case isn't size 1 - the base case is size zero. This is much more natural, since there isn't anything particularly special about 1 vs 2 but there is with 0 vs 1:

bool sameElements(const int* Arr1, const int* Arr2, int size) {
 if (size == 0) {
 return true;
 }
 else {
 ...
 }
}

Recursive case

Doing something like if (expr) return true; else return false; is an anti-pattern. expr already gives you a bool, so that could just be used directly. The same can be said for your recursive case: you need to check that the first elements match and that the rest match:

return Arr1[0] == Arr2[0] && // this case &&
 sameElements(Arr1 + 1, Arr2 + 1, size - 1); // recurse down

Advance both arrays as you go and alter the size. It makes the whole function flow much more naturally.

Really different orders?

I don't understand the requirement that both (a) the elements can be in arbitrary order and (b) you can't sort or use another data structure and (c) recursively. Because not modifying the input seems a pretty important convention, and it's quite difficult to not modify the input while also doing both (a) and (b), recursively (iteratively, much easier).

• lex82: If we assume the given code works, it's not the same elements in the same order but the same elements regardless of their order.
• Barry: @lex82 But then OP is modifying the input array - that's bad design. But then OP is disallowing a sort of any other data structure. So I'm skeptical.
• lex82: It is bad design, but in my opinion the question makes no sense otherwise. It would be so simple that no one would consider using dictionaries or sort the arrays. And again, the given code would be wrong. It would yield true for some arrays that are not identical.
• Barry: @lex82 Asking to write an array-in-order-equality function recursively makes perfect sense. Just because it's easy for an experienced programmer doesn't mean it doesn't make sense.
• lex82: It makes sense but the code in the question as it is makes no sense if it was asked to compare the elements in order. The solution is actually very reasonable for the set case so I assume this is what is wanted. Let's just wait what DG6 says.