Number of times number appears in an array

Question

I found an exercise in a C++ book that says "Write a function that will count the number of times a number appears in an array.". Everything is fine, the program is working. But the exercise also says that the function should be recursive.

How can I make a recursive function working like this?

#include <iostream>

int count(int number, int array[], int length)
{
    int counter = 0; 
    for(int i = 0; i < length; i++)
        if(array[i] == number)
            counter++;
    return counter;
}

int main()
{
    int numbers[10] = {3,4,1,2,4,5,6,5,4,5};
    int number_to_search = 5;
    std::cout << number_to_search << " appears "
              << count(number_to_search, numbers, 10)
              << " times in the array.";
    return 0;
}

Answer 1

Use this count function:

int count(int number, int array[], int length) {
    if (length == 0) return 0;
    return (number == *array) + count(number, array+1, length-1);
}

Answer 2

Instead of the loop and counter you have now, return 0 + recursive_step or 1 + recursive_step, where recursive_step is a call to count(...) where you have increased the array pointer and decreased length. Your base case is when length == 0, at which point you just return 0.

A nice way of understanding recursion is to study how the calculation is carried out, step by step. In your example you will do something like this:

count(5, {3,4,1,2,4,5,6,5,4,5})
0+count(5, {4,1,2,4,5,6,5,4,5})
0+0+count(5, {1,2,4,5,6,5,4,5})
0+0+0+count(5, {2,4,5,6,5,4,5})
0+0+0+0+count(5, {4,5,6,5,4,5})
0+0+0+0+0+count(5, {5,6,5,4,5})
0+0+0+0+0+1+count(5, {6,5,4,5})
0+0+0+0+0+1+0+count(5, {5,4,5})
0+0+0+0+0+1+0+1+count(5, {4,5})
0+0+0+0+0+1+0+1+0+count(5, {5})
0+0+0+0+0+1+0+1+0+1+count(5,{})
0+0+0+0+0+1+0+1+0+1+0  <---The last 0 is the base case
3

---

If you are allowed to change the function specification, you can do also something cool called tail recursion. Instead of return 1 + count(...), add the accumulated number so far as a paremeter to count: int count(int number, int array[], int length, int acc)

And do return count(..., acc+1) or return count(..., acc+0). Some compilers are then able to do tail call optimization , transforming it into a loop in the compiled code. This saves memory compared to a regular recursion.

Answer 3

How about trying like this:-

int count(int num, int* arr, int length) {
    if (!length)
        return 0;
    int c = count(num, arr+1, length-1);
    return arr[0] == num? c + 1: c;
}

int main(void) {
int arr[10] = {3,4,1,2,4,5,6,5,4,5};

std::cout << count(2, arr, 10);

return 0;
}

Answer 4

Here is what you do (I wouldn't show you any code to avoid spoiling an exercise for you).

First, recall that in order to be recursive your function needs to call itself. Next, consider these two points:

• When the length parameter is equal to zero, the return value of count(...) must be zero
• When the length parameter is not zero, consider the return value of count(...) for array + 1 and length-1; let's call it prior. The return value of the current count(...) will be equal to prior+1 if array[0] is equal to number, or to prior when array[0] is not equal to number.

When you make your code out of this description, observe how you have an if at the beginning of your recursive function. This if splits your code into the base case (length == 0) and the recursive step (computing the result based on a recursive call). This is a common structure of recursive functions: you will have to reproduce this structure every time you write recursive code.

Answer 5

#include <iostream>

void count(int number, int array[], int length, int &occurence)
{
    if (*array == number) ++occurence;  

    if (length == 1)
        return;
    else    
        count(number, array+1, length-1, occurence);
}

int main()
{
    int numbers[10] = {3,4,1,2,4,5,6,5,4,5};
    int number_to_search = 5;
    int occurence = 0;
    count(number_to_search, numbers, 10,occurence);
    std::cout << number_to_search << " appears "
              << occurence
              << " times in the array.";
}

Answer 6

 #include <iostream>
 #include <ctime>
 #include <cstdlib>
 using namespace std;
 int i, j,n,c=0, k=0;
 int a[1000], b[1000];
 class Array {


    public:
        void input ()
        {
            cout<<"Enter how many values: ";
            cin>>n;
        }

        void arraySeries ()
        {
            cout<<"Array elements: ";
            srand(time(0));
            for (i=0; i<n; i++)
            {
                a[i]=rand()%100+1;
                cout<<a[i]<<" ";

            }
            cout<<endl<<endl;
            cout<<"Odd elements of array: ";
            for (i=0; i<n; i++)
            {   
                if(a[i]%2==1)
                {
                    b[i]=a[i];
                    k++;
                    cout<<b[i]<<" ";
                }

            }
        }
        // i want to find out how many times an odd number is found in b[i]
        // but i am not being able to do so. SOMEONE PLEASE HELP!!
        void OddSearch ()
        {
            cout<<endl<<endl;
            for (int k=1;k<100;k++)
            {
                c=0;
                for (i=0;i<n; i++)
                {

                    if (b[i]==k)
                    {
                        c++;
                    }
                    cout<<b[i]<<"occurs"<<c<<"times"<<endl;
                }
            }
        }
 };

 int main ()
 {
    Array obj;
    obj.input();
    obj.arraySeries();
    obj.OddSearch();

    return 0;
 }

Answer 7

#include <stdio.h>

int count(int number,int array[],int size){
   int counter=0;
   if(size == 0) return 0;
   if(array[0] == number){
      counter++;
      return counter+count(number,array+1,size-1);
   }    
   return count(number,array+1,size-1);    
 }

int main() {
 
  int array[] = {1,2,2,4,4,8,7,3,4};
  int size = sizeof(array)/sizeof(int);

  printf("%d",count(2,array,size));

  return 0;    
}