Given two arrays arr1 and arr2, I need to write a recursive function in C, that accepts arr1 and arr2 as arguments, that returns True if arr1 is a subsequence of arr2, meaning that the elements of arr1 appear in arr2 in the same order, though not necessarily in consecutive order.

For instance, given the inputs

int arr1[] = {1, 2, 3}; 
int arr2[] = {0, 1, 4, 2, 5, 3, 6};

it should yield True, while

int arr1[] = {1, 2, 3}; 
int arr2[] = {0, 1, 4, 3, 5, 2, 6};

should yield False. This is my attempt:

int array_in(int arr1[], int len1, int arr2[], int len2) {

    if (len1 == 0) {
        return 1;
    }

    if (len2 == 0) {
        return 0;
    }

    if (arr1[0] == arr2[0]) {
        return array_in(arr1 + 1, len1 - 1, arr2 + 1, len2 - 1);
    } else {
        return array_in(arr1, len1, arr2 + 1, len2 - 1);
    }
}

however, it fails with

int arr1[] = {1, 2, 3};
int arr2[] = {0, 1, 4, 3, 2, 3, 5, 6};

because it returns True even though I’m repeating twice the number 3, so I have a 1-3-2-3 sequence but it seems to ignore the first 3. What am I doing wrong?