explanation of this recursive function

Question

hey there can anyone tell me how this function work ?!

for function and void function :

int countoccu(int array[],int value,int lower,int upper)
{
    int counter=0;
    if(lower==upper)
        if (array[lower]==value)
            return 1;
        else
            return 0;
    else
        counter = counter + countoccu(array, value, lower+1, upper);

    if (array[lower]==value)
        counter++;
    return counter;
};

can anyone explain this for me

the output will be 3

void main()
{
    int array[5]={3,7,3,3,11};
    cout << countoccu(array,3,0,4) << endl;
}

Is this a homework question? If so, please provide some more input on what your thoughts so far are (see http://meta.stackexchange.com/questions/10811/how-do-i-ask-and-answer-homework-questions for guidance) — SirRichie, Jan 09 '14 at 12:11
`};` <-- this is not javascript... also `main` must have a return value so it can't be void. — deW1, Jan 09 '14 at 12:21
To clarify on what @dan said, `void main()` is [illegal](http://stackoverflow.com/a/2080996/1227469) and leads to undefined behaviour. Use `int main()` instead and (optionally) `return 0;` at the end of the function to indicate successful termination of the program. It's ok to omit the `return` statement, in which case it will return 0 by default. — JBentley, Jan 09 '14 at 12:52
This question appears to be off-topic because it is too localised. — Nicholas Wilson, Jan 10 '14 at 14:47

score 2 · Answer 1 · answered Jan 09 '14 at 12:15

2

It's a very stupid way to count number of value occurrences, for a given array, in given [upper, lower] range, using recurrence.

(If I understood it good.)

This looks like a homework, so I'll leave figuring it how it happens to you. My hint would be analyze code line by line, with a paper-sheet-pencil debugger.

answered Jan 09 '14 at 12:15

luk32

15,812
38
62

I guess, the upper element is counted twice – dousin Jan 09 '14 at 12:23
IMO it works correctly, it is stupid because it uses recursion for an iterative task, and makes it hardly comprehensible. I am not a big fan of doing `fun(n){ /* stuff */ return fun(n+1);}`. It's not even using stack for anything except a variable that can only be incremented or not. – luk32 Jan 09 '14 at 13:32

score 1 · Answer 2 · answered Jan 09 '14 at 12:17

int countoccu(int array[],int value,int lower,int upper){

int counter=0;

// Check if the end of the array is reached
if(lower==upper)

    // Is the last element the "value" we are looking for?
    if (array[lower]==value)
        // Yes, so count it
        return 1;
    // No, don't count it
    else return 0;

// Not the end of the array
else
    // Move the position to the next item in the array and count it and all the following values that equals "value"
    counter=counter+countoccu(array,value,lower+1,upper);

// Is the current item equal to the value being counted?
if (array[lower]==value)
    // Yes, so count it
    counter++;

return counter;

In your example you will get these calls:
countoccu(array,3,0,4) = 1+0+1+1+0 = 3
  countoccu(array,3,1,4) = 0+1+1+0 = 2
    countoccu(array,3,2,4) = 1+1+0 = 2
      countoccu(array,3,3,4) = 1+0 = 1
        countoccu(array,3,4,4) = 0 = 0

Vlad from Moscow · Answer 3 · 2014-01-09T14:23:34.287

Though the function is written badly its principle of the work is simple. It checks whether the element with lower index is equal to the given value. If so it increases the count and adds the count for the array starting from the next index after index lower that is lower + 1 (calling itself at this time with lower + 1).

I would rewrite the function the following way

/* constexpr */ size_t count( const int a[], size_t n, int value )
{
   return ( n == 0 ? 0 : ( ( a[0] == value ) + count( a + 1, n - 1, value ) ) );
}

I commented specifier constexpr because I think you do not know its meaning. So it may be omited.

explanation of this recursive function

3 Answers3