Problem Statement

Write a program that counts the number of occurrence of a specific element in an array using recursion. The program should prompt the user to input the size of the array, its element, and the target element to count occurrences for. Then, it should compute and print the count of occurrences of the target element in the array.

Problem Understanding

To solve this problem recursively, we need to understand that counting the occurrences of a specific element in an array involves iterating through each element of the array and comparing it with the target element. Recursion involves breaking down a problem into smaller instances until reaching a base case. In this case, the base case occurs when the array becomes empty, at which point we return 0.

Solution in C++

#include <iostream>
#include <vector>

// Recursive function to count the number of occurrences of a specific element in an array
int countOccurrences(const std::vector<int>& arr, int target, int index) {
    // Base case: If the index exceeds the size of the array
    if (index >= arr.size()) {
        return 0;
    }
    
    // If the current element matches the target element, increment the count
    int count = (arr[index] == target) ? 1 : 0;
    
    // Recursively call countOccurrences with the next index
    return count + countOccurrences(arr, target, index + 1);
}

int main() {
    int n, target;

    // Prompt the user to enter the size of the array
    std::cout << "Enter the size of the array: ";
    std::cin >> n;

    // Create an array of size n
    std::vector<int> arr(n);

    // Prompt the user to enter the elements of the array
    std::cout << "Enter the elements of the array:\n";
    for (int i = 0; i < n; ++i) {
        std::cin >> arr[i];
    }

    // Prompt the user to enter the target element
    std::cout << "Enter the target element to count occurrences: ";
    std::cin >> target;

    // Call the recursive function to count occurrences
    int occurrences = countOccurrences(arr, target, 0);

    // Print the result
    std::cout << "Number of occurrences of " << target << " in the array: " << occurrences << std::endl;

    return 0;
}

Complexity Analysis

Time Complexity:

• In each recursive call, we perform a constant amount of work (comparing elements), which can be considered O(1).
• The number of recursive calls depends on the size of the array, which is proportional to the size of the input array.
• Therefore, the overall time complexity of the solution is O(n), where n is the size of the input array.

Space Complexity:

• The space complexity of the solution is O(n) as well, considering the recursive calls create a call stack with n frames.