c++ - Find common element using recursive and return as vector

Question

I am trying to find common elements of two arrays but I am getting false results.

Where is my mistake? It seems like everything is normal.

template<class T>
bool contains(T arr,int size, int num){
    for(int i=0; i<size;++i)
        if(arr[i] == num)
            return true;
    return false;
}

I am trying to use tail recursion:

template <class T>
vector<T> cElemet(T ar1[], int s1, T ar2[], int s2){

    vector<T> v;


    if(s1 > 0) 
        v = cElemet(ar1,s1-1,ar2,s2);


    if(contains(ar2,s2,ar1[s1-1])){
        cout << "+" << ar1[s1-1] ; 
        v.push_back(ar1[s1-1]);
    }

    return v;
}
int main(){
    
    int ar1[6] = {1,5,6,7,2,4};
    int ar2[6] = {6,3,9,4,5,8};

    std::vector<int> v = cElemet(ar1,6,ar2,6);

    cout <<endl;
    for(auto a : v)
        cout << a << " ";
    return 0;
}

question from:https://stackoverflow.com/questions/65922852/find-common-element-using-recursive-and-return-as-vector

Answer 1

Your 'recursion end' condition is "off-by-one" – it should be if (s1 > 1) instead of if (s1 > 0).

As it stands, you end up calling cElemet with a value of 0 (froms1 - 1) and then, in that recursion, you attempt to access ar1[s1 - 1] when s1 is zero, which causes undefined behaviour.

Changing your function to the following fixes the problem – for your sample arrays (even when I tested by jumbling up the data values). However, there may be issues for arrays of size 1.

template <class T>
vector<T> cElemet(T ar1[], int s1, T ar2[], int s2)
{
    vector<T> v;
    if (s1 > 1) // Don't call recursively when s1 is 1 ...
        v = cElemet(ar1, s1 - 1, ar2, s2);

    if (contains(ar2, s2, ar1[s1 - 1])) { // ... or we have UB here.
        cout << "+" << ar1[s1 - 1];
        v.push_back(ar1[s1 - 1]);
    }
    return v;
}