Understanding arrays and pointers in recursive functions

Question

I have to write a recursive function that will check if two given arrays of the same size have the same elements but they could be in different order.

I thought the most elegant solution would be to sort the two arrays, and then compare each element but I don't know of a way to sort two arrays in one recursive function.

So I had another idea, using a linear search, take the last element of array1 and search for it in array2, if it's there, using a shiftback function, shift all elements in front of that element (in array2) and return true, if it isn't found return false. This would go through all levels of recursion.

But it doesn't work and I see in the debugger that the arrays are suddenly 1 element long after the stopping condition for the recursion has been met.

From what I read, passing the arrays not as pointers would be unwise, but could it solve this problem? how is it done anyway?

This is the code, it is well documented:

Note: I can't use library functions.

#include <iostream>
using namespace std;

bool sameelem(int A1[], int A2[], int len);
void shiftback(int a[], int len, int i);
bool lsearchandshift(int a[], int len, int key);

void main()
{
    int arr[7] = { 1, -2, 3, 4, -1, 6, -7 };
    int arr2[7] = { 1, -2, 3, 3, -1, 6, -7 };

    cout << sameelem(arr, arr2, 7);
}

bool sameelem(int A1[], int A2[], int len){
    ///pick an element from arr1, if it appears in arr2 cut both out using shiftback
    ///if it doesn't appear rerturn false, false should go thorugh all levels till the end
    //end: if true check last two elements, if false return false

    if (size==0)return true;
    else{
        sameelem(Arr1, Arr2, len - 1);
        return (lsearchandshift(Arr2, size, Arr1[size - 1]));//if the last element from Arr1 is in Arr2 this will be true
    }
}


//linear search function, will return 0 if key isn't found, otherwise will 'kill' that element using shiftback function and return 1
bool lsearchandshift(int a[], int len, int key){
    int i;
    bool found = false;

    for (i = 0; i < len && found==false; i++)//if found will turn true and stop searching
    {
        if (a[i] == key){
            found = true;

            shiftback(a, len, i);
        }
    }
    return found;
}

//array shifting backward function
//len has to be logical size, array's physical size has to be larger than entered logical size
void shiftback(int a[], int len, int i){
//i is the index which will be moved one place forward to i+1 along with all the other elements
    int j;
    for (j = i; j < len; j++)
    {
        a[j] = a[j+1];
    }
    //return a[len-1];
}

@ravi but what if the arrays are: A[3]={2,3,3} B[3]={3,2,2}? this method will falsely think they're the same. I can't do this either way in one recursive function — shinzou
– shinzou, Commented Dec 20, 2014 at 11:25
Surely sorting arrays is much more preferable than relying on linear search...Why don't you use std::sort to sort the array's first then pass them to your recursive function to check if they are equal...that would be much easy task. — ravi
– ravi, Commented Dec 20, 2014 at 11:29
You want to remove one element from A, search for it in in B, and if you find it then remove it from B and call the function again on the newly shortened arrays, is that right? — Beta
– Beta, Commented Dec 20, 2014 at 11:30
@ravi I have do it on my own without relying on library functions. — shinzou
– shinzou, Commented Dec 20, 2014 at 11:30
@Beta almost, I want to remove elements only from array B and go through the elements of A linearly through the recursion. — shinzou
– shinzou, Commented Dec 20, 2014 at 11:32

Beta · Accepted Answer · 2014-12-20 11:48:34Z

1

The only function that calls itself is haveSameElems:

bool haveSameElems(int Arr1[], int Arr2[], int size)
{
  ///pick an element from arr1, if it appears in arr2 cut both out using shiftback
  ///if it doesn't appear rerturn false, false should go thorugh all levels till the end
  //end: if true check last two elements, if false return false
  if (size==0)return true;
  else{
    haveSameElems(Arr1, Arr2, size - 1);
    return (lsearchandshift(Arr2, size, Arr1[size - 1]));//if the last element from Arr1 is \
in Arr2 this will be true
  }
}

Notice that is does not use the return value of the recursive call. So the recursive call could return false and the calling function would never know it.

You can fix this easily:

if(!haveSameElems(Arr1, Arr2, size - 1))
  return(false);

There is still a lot of room for improvement -- in this code and in your approach to writing it -- but this is enough to get you moving.

answered Dec 20, 2014 at 11:48

Beta

99.5k18 gold badges159 silver badges156 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

shinzou Over a year ago

Ah yes I was missing a way to return the false through all levels of recursion. Thanks for pointing that out. Though it looks like it doesn't work if the arrays are the same but sorted differently... back to drawing board.

Beta Over a year ago

@kuhaku: Yes, because you're not clear about what size actually represents. As I said, there's a lot left to do.

ravi · Accepted Answer · 2014-12-20 12:01:05Z

Take this for your reference:-

bool isSame(int *p, int *q, int n)
{
    if( n == -1 )
        return true;
    if ( *p != *q )
        return false;
    else
        isSame(++p, ++q, --n);
}

int main()
{
    int arr1[] = {1,2,3,2,4,5};
    int arr2[] = {2,1,5,2,3,4};

    //check if two arrays have different number of elements...
    //If yes then just jump past 4-5 lines...

    std::sort(arr1, arr1 + sizeof(arr1)/sizeof(arr1[0]));  <<< You can build your own
    std::sort(arr2, arr2 + sizeof(arr2)/sizeof(arr2[0]));  <<< sort.

    if( isSame(arr1, arr2, 6) )
        cout << "Arrays are same" << endl;
    else
        cout << "Arrays are different" << endl;
}

It's almost always better to sort arrays first rather than working on unsorted arrays in these algorithms. One more benefit is that moment you see a mismatch you stop moving further.

Collectives™ on Stack Overflow

Understanding arrays and pointers in recursive functions

2 Answers 2

2 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

2 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related