RECUR09 - Editorial

editorial
, ,
1

Problem Link - Linear Search using Recursion in Recursion

Problem Statement:

You are given an array Arr and an integer X. You have to search the array Arr and check if X exists in Arr or not, if yes print the first position of X else print −1.

Approach

  • Base Case: If index is greater than or equal to n (the size of the array), it means we have checked all elements without finding X. Therefore, we return -1 to indicate that the target value is not present in the array.
  • Check Current Element: If the current element at arr[index] matches X Return index because we have found the target value.
  • Recursive Call: If the current element does not match X, make a recursive call to function with the next index (index + 1). This means we will check the next element in the array.
  • Start the Search: In the main() function, we initialize the search by calling the function with index set to 0 (the first element of the array).

Complexity:

  • Time Complexity: O(N) We might need to check every element in the array once if X is either the last element or not present at all.

  • Space Complexity: O(N) if the array length is N and X is not found, we will have N recursive calls stacked on the call stack.