Problem Statement
Given an array of numbers, we need to find a specific index of a number using recursion.
Example Inputs
- Array: [3, 8, 15, 10, 21]
- Target Number: 10
- Expected Output: 3
Approach - Use Recursion
Approach
Recursion is a technique where a function calls itself to break down a problem into smaller subproblems. For this problem, the idea is to check each element of the array one by one, starting from the first element, and recursively check if the current element matches the target number.
Steps
- Start by checking the first element in the array.
- If it’s the target number, return it.
- If it’s not, call the function recursively on the rest of the array (i.e., pass a subarray starting from the next element).
- If the target number is not found, return a message indicating that the number is not in the array.
Time & Space Complexity
- Time Complexity: O(n), where n is the number of elements in the array. In the worst case, we check each element once.
- Space Complexity: O(n) due to the recursion stack (each recursive call takes up space on the stack).
Code Snippet
Dry Run
Let’s dry run the code with the array [3, 8, 15, 10, 21] and the target number 10.
- findNumber([3, 8, 15, 10, 21], 10, 0): Check index 0 (value = 3) → it's not the target, call recursively on the rest of the array.
- findNumber([3, 8, 15, 10, 21], 10, 1): Check index 1 (value = 8) → it's not the target, call recursively on the rest of the array.
- findNumber([3, 8, 15, 10, 21], 10, 2): Check index 2 (value = 15) → it's not the target, call recursively on the rest of the array.
- findNumber([3, 8, 15, 10, 21], 10, 3): Check index 3 (value = 10) → it's the target, return 3.
- The function returns
3, indicating that the target number 10 is found at index 3.
Complexity Analysis
Time and Space Complexity
- Time Complexity: O(n) because in the worst case, we need to check every element in the array.
- Space Complexity: O(n) because of the recursive calls, each of which takes up space on the call stack.
Conclusion
Recursion is a powerful technique for solving problems, especially when the problem can be broken down into smaller subproblems. While it provides an elegant solution, it can lead to higher memory usage due to the call stack. For very large arrays, iterative solutions may be more efficient, but for smaller inputs or when recursion fits naturally, it’s a good approach.
In this guide, we’ve demonstrated how recursion can be used to search for a number in an array, as well as analyzed the time and space complexities associated with the recursive approach.