Recursive Linear Search

Question

The code shown below works fine. It prints the position of the element found inside the if clause and exits. Whenever the element is not found, the function runs to max and returns 0 to calling function to indicate no elements has been found.

However, I was pondering about returning the position of the element found, to the calling function rather than printing it. Since returning the position would just return to earlier instance of the function and not to the calling function, I am struck. How to achieve this ?

#include <stdio.h>
#include <stdlib.h>

int RLinearSearch(int A[],int n,int key)
{
    if(n<1)
        return 0;
    else
    {
        RLinearSearch(A,n-1,key);
        if(A[n-1]==key)
        {
            printf("found %d at %d",key,n);
            exit(0);
        }
    }
    return 0;
}

int main(void) 
{
    int A[5]={23,41,22,15,32};   // Array Of 5 Elements 
    int pos,n=5;

    pos=RLinearSearch(A,n,23);

    if(pos==0)
        printf("Not found");

    return 0;
}

Answer 1

Since returning the position would just return to earlier instance of the function and not to the calling function, I am struck.

You can solve this problem by returning the result of recursive invocation from the recursive call itself:

int RLinearSearch(int A[], int n, int key) {
    if(n<0) { // Base case - not found
        return -1;
    }
    if(A[n]==key) { // Base case - found
        return n;
    }
    // Recursive case
    return RLinearSearch(A, n-1, key);
}

Since this implementation treats n as the index of the current element, the caller should pass 4, not 5, in your example.

Demo 1.

Note: you can further simplify the code by joining the base cases together:

int RLinearSearch(int A[], int n, int key) {
    return (n<0 || A[n]==key) ? n : RLinearSearch(A, n-1, key);
}

Demo 2.