CODEWITHSUNDEEP
c++arrayspointersrecursion
shinzou
shinzou

Reputation: 6222

Understanding arrays and pointers in recursive functions

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];
}

Upvotes: 2

Views: 2366

Answers (2)

ravi
ravi

Reputation: 10733

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.

Upvotes: 1

Beta
Beta

Reputation: 99144

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.

Upvotes: 1

Related Questions