Recursive Linear Search in an Array

Given an array of N integers and a target value X, determine the index (0-based) of the first occurrence of X in the array using a recursive function that checks one element at a time and recurses on the rest of the array. If X does not appear in the array, report that it was not found.

Input: The first line contains the integer N. The second line contains N space-separated integers, the array elements. The third line contains the integer X, the target value. Output: A single line containing the 0-based index of the first occurrence of X in the array, or -1 if X is not present.

1 <= N <= 1000, -10^9 <= array elements <= 10^9, -10^9 <= X <= 10^9.

This is a direct recursive re-expression of the simplest possible iterative algorithm (linear search) - useful for building comfort with translating familiar loop-based logic into recursive form before tackling harder, genuinely recursion-native problems.

Find a target value's first position in an array using a recursive function instead of a loop. Brute force: Use a simple iterative loop checking each element in turn - equally efficient, but this problem specifically asks for the recursive framing to practice replacing a loop's 'keep going until found' logic with a recursive call. Optimised: Recursion naturally mirrors the iterative loop's structure here: 'check this one element, then hand off the rest of the search to a smaller version of the same problem' - each recursive call simply moves the search forward by one position, exactly like a loop's index increment.

1. The BASE CASE: if the current index reaches N (running off the end of the array), the target isn't present - return -1. 2. If the element at the current index equals the target, that index IS the answer - stop recursing and return it. 3. Otherwise, recurse on index + 1 and simply pass along whatever that recursive call returns.

Time: O(n) in the worst case - checking each element once, just like an iterative linear search. Space: O(n), for the recursion call stack in the worst case (target not found, or found at the very end).

N = 1 (a single-element array). X may not be present at all, in which case the output is -1. N = 1000 is the largest array this problem is tested with.

Be ready to note that this recursive version has WORSE space complexity than the equivalent iterative loop (O(n) call stack versus O(1) for a loop) - a good example of recursion sometimes trading memory for a more elegant, declarative expression of the same logic.