"There is a subtle difference between implementing recursively and recursive implementation". If you couldn't comprehend this quote, try reading my article on this topic.

We are going to see the implementations of the various ways of performing linear search via recursion. The slight modifications in the code will enable you to think deeper and understand recursion in depth.

1. First Occurrence of the Key value

The problem statement is as follows:
Given an array, find the first occurrence of the key value in the array using recursion. The function should return the index of the first occurrence.

There are 2 ways to move forward in an array. You can either maintain an explicit variable for storing the index of the array element or you can increment the array base address by 1.

Note: Arrays are passed by reference to the functions but the address of the array is passed by value. So incrementing the address of the array during the function call won't lead to any error or modifications in the original input array.

a) Using explicit index variable

// i is the index of the current element
int linearSearch(int *arr, int i, int n, int key) {
    // base case
    if(i == n)
        return -1;

    // recursive calls
    if(arr[i] == key)
        return i;

    return linearSearch(arr, i + 1, n, key);
}

This implementation is the exact replication of the iterative implementation.
Since we are using recursion, we would like to hit the base case by reducing the size of the problem as opposed to using recursion for iterating over the next element via an extra function call.

b) Incrementing array's base address

int firstOccur(int *arr, int n, int key) {
    // base case
    if(n == 0) 
        return -1;
    // recursive calls
    if(arr[0] == key)
        return 0;

    int index = firstOccur(arr + 1, n - 1, key);
    if(index == -1)
        return -1;
    else    
        return index + 1;
}

This code int index = firstOccur(arr + 1, n - 1, key); simply makes a function call by incrementing the array address and thereby decreasing the size of the array.

Since we are looking for the first occurrence, as soon as we encounter an index value not equal to -1, we return the index from their to the previous function call.

Finally, we are able to get the index of the element wrt the original address of the array.

2. Last Occurrence of the Key value

int lastOccur(int *arr, int n, int key) {
    // base case
    if(n == 0)
        return -1;

    // recursive calls
    // first make a call and then check
    int index = lastOccur(arr + 1, n - 1, key);
    if(index == -1) {
        if(arr[0] == key)
            return 0;
        else
            return -1;
    }
    else 
        return index + 1;
}

The only difference between the above discussed method for the first occurrence and this approach is the positioning of the check condition and the recursive function calls.

Here, we first make all the recursive calls and then check for the condition.

Let us dry run the above code.

if n = 5 and the array is {5, 4, 3, 2, 1}. 
Due to the recursive calls the array will keep reducing, one n becomes 0, we return the value `-1`. Now for the array of size 1, we check if that element is the key element to be searched. If the answer is `yes`, then we simply return 0 ie. index wrt to the current base address of the array. 

By returning `index + 1`, we could obtain the last occurrence index wrt to the original base address of the array.

3. All Occurrences of the Key value

a) Using explicit index variable

void allOccur(int *arr, int i, int n, int key) {
    // base case
    if(i == n)
        return;

    if(arr[i] == key) 
        cout << i << " ";

    // recursive calls
    allOccur(arr, i + 1, n, key);
}
Instead of simply printing the values, you can store them in an array.

b) Incrementing array's base address

// returns the size of the output array/ count of total occurrences / frequency of the key
int storeOccur(int *arr, int i, int n, int key, int *indices, int j) {
    // base case 
    if(i == n)
        return j;

    // recursive calls
    if(arr[i] == key) {
        indices[j] = i;
        // increment j to accomodate the current occurence.
        return storeOccur(arr, i + 1, n, key, indices, j + 1);
    }
    else 
        // j remains unchanged
        return storeOccur(arr, i + 1, n, key, indices, j);
}

The above function returns the size of the index array ie. the number of occurrences of the key element.

Hope, it strengthened your concepts of recursion. It is a crucial step to think of the base cases and the order in which the statements are written.

A statement return after the recursive function calls simply mean you are trying to process the last element.

The significance of ordering of statements leads to different traversals in tree data structures.

Hope you enjoyed this article and feel free to connect with me on LinkedIn and github.