How to count the number of 0's in array using recursion?-CodePudding

Below is the code I've used . Its returning 0 as the count .What is the cause of error here?Is the base condition not adequate ?

#include<bits/stdc  .h>
using namespace std;

int CountZeros(int a[], int n, int count) {
int i = 0;

  //base condition
  if (n == 0) return 0;
  if (a[0] == 0) {
    count  = 1;
  }

  int SmallAns = CountZeros(a   1, n - 1, count);
}
int main() {
  int count = 0;
  int a[5] = {
    1,
    0,
    3,
    0,
    5
  };
  CountZeros(a, 5, count);
  cout << count;

  return 0;
}

CodePudding user response：

Your function doesn't return anything in the recursive case, leading to undefined behaviour.
(Recursive functions work exactly like non-recursive functions – if you don't return a value, no value is returned.)

You appear to be aiming for tail recursion, in which case the base case should return the accumulation argument (count), not a base value, and you make the initial call with the base value (zero):

int CountZeros(int a[], int n, int count) {

  if (n == 0) 
    return count;
  else 
    return CountZeros(a   1, n - 1, a[0] == 0 ? count   1 : count);
}

Using non-tail recursion, you would not pass count as an argument, but add to the recursive result:

int CountZeros(int a[], int n) {

  if (n == 0) 
    return 0;
  int SmallAns = CountZeros(a   1, n - 1);
  return a[0] == 0 ? SmallAns   1 : SmallAns;
}

This is less efficient, though – a decent compiler will turn the tail-recursive version into a simple loop (gcc, clang and msvc all do it).

CodePudding user response：

First task, when n equals zero the correct return value is count not 0. I.e. you have reached the end of the array so you must return all the zeros you have counted so far. This is necessary because you add to your count before your recursive call.

if (n == 0) return count;

On the other hand if you added to the count after the recursive call then return 0; would be correct.

Second task, actually return something from the CountZeros function after you have made your recursive call.

int SmallAns = CountZeros(a   1, n - 1, count);
return SmallAns;

Third task, use that returned value in the main function

count = CountZeros(a, 5, count);
cout << count;

Now, optional fourth task, there are a lot of unneeded variables in this code. See if you can remove the count variable in main and the smallAns and i variables in CountZeros.