Simply recursive function misunderstanding

Question

This recursive function must return 1 if the sum of all digits of the num is even, if the sum is odd - return 0.

Please explain me what it exactly does in details and how the NOT operator works in this particular example. I haven't seen yet NOT on the recursive call and it confused me a bit.

int func(int num) {
    if (num < 10) {
        if (num % 2 == 0) {
            return 1;
        } else {
            return 0;
        }
    }
    if ((num % 10) % 2 == 0) {
        //roughly clear, but I'll be glad to receive some opinions about that to be sure
        return func(num / 10);
    } else {
        return !func(num / 10); //this line is not clear for me
    }
}

Try running it on a piece of paper with a couple of inputs. (Hint: `odd + odd = even`, `even + even = even`, `odd + even = odd`) — GalAbra, Aug 04 '18 at 11:30
This function works properly. My only question is how the NOT operator works if i apply it on the recursive call, the line in the last else statement that i marked is not so clear for me. — Asm ., Aug 04 '18 at 11:32
NOT operator works with function when retrun value is TRUE or FALSE because it is returning some valueso in your code it is always true i dont have clear idea of this behaviour — jasinth premkumar, Aug 04 '18 at 11:37
That's exactly the point of my question. But the output of the function is always valid smh, i've tried several inputs and every answer is correct. — Asm ., Aug 04 '18 at 11:39
check this answer https://stackoverflow.com/questions/15393935/boolean-in-an-if-statement#15394130 — jasinth premkumar, Aug 04 '18 at 11:43
@jasinthpremkumar: `true` and `false` are normal `int` value of `1` and `0` respectively. — too honest for this site, Aug 04 '18 at 16:54

score 2 · Answer 1 · answered Aug 04 '18 at 11:34

Any odd number can be represented a the sum of an even and an odd number. The sum of two odd numbers is always even.

This exploits that principle. In the last block, since the first digit of num (num%10) is odd, it basically inverts the result of func. If the value returned is even, then you need to add an odd number, which transforms it to an odd number. If the value returned is odd, then after adding the current digit, you get an even number. So, this essentially flips the output of func, so putting a not operator will do the same thing too.

score 0 · Answer 2 · answered Aug 04 '18 at 14:27

The ! operator compares its argument to 0: !expr is equivalent to expr == 0. The last expression relies on the fact that !0 == 1 and !1 == 0.

In the code posted, if the number is less than 10, the result is 1 is n is even and 0 if it is odd. Evenness is tested by computing the remainder of the division by 2.

Conversely if the the number has more than 1 digit (n >= 10), the function computes the result for the number with the last digit removed func(num / 10) and returns it directly if n is even, since adding an even digit to a sum does not change its evenness, and returns its opposite if n is odd as adding the last digit which is odd will change the evenness of the sum.

It seems simpler and more readable to compute the sum of the digits and check its evenness:

int func(int num) {
    int sum = 0;
    while (num > 0) {
       sum += num % 10;
       num /= 10;
    }
    return sum & 1;
}

Here is another alternative where only the least significant bit is computed:

int func(int num) {
    int odd = 0;        // default to even
    while (num > 0) {
       odd ^= num & 1;  // invert if current digit is odd
       num /= 10;       // drop last digit
    }
    return odd;
}

Note that none of the above functions handle negative numbers correctly.

Simply recursive function misunderstanding

2 Answers2