recursion?

[jellytelly]

Hi guys. So in my introduction to programming class, we have to do a recursive function to find out if a number is even or odd, but without using any math.

This is the model answer given:
int even (int x)
{
if (x == 0)return 1;
return !even(predecessor(x));
}

Can someone explain to me what the ! means, and how this recursion works?? I can't seem to figure it out:( Thanks guys!

[Peter87]

! means NOT. It turns true into false and vice versa.

[ne555]

! == not

even, odd, even, odd, even, odd...
The only number that knows if it is even or odd, is zero.
The other numbers ask their left neighbour.

[jellytelly]

oh man. i'm still confused.
here's the whole code:

int even (int x)
{
if (x == 0) return 1;
return !even(x-1);
}

int main ()
{
int x;
scanf("%d", &x);
if (even(x))
printf("even/n");
else
printf("odd/n");
return 0;
}

let's say the input is 3, so what would the function return the first round? and does it return it to the main or to the function again?
when x finally equals 0, how does this information relate to your input number?

anyway thanks for your help!

[booradley60]

Let's say the input is 3. Here's how the call stack would unwind and give you the correct result false. However, it assumes that you change the definition of 'even' to use the bool type, like this:

bool even (int x)
{
    if (x == 0) return true;
    return !even(x-1);
}

main
 |
 |--> even(3)
       |
       |--> ! (even(2))
       |        |
       |        |-->  ! (even(1))
       |        |         |
       |        |         |--> ! (even(0))
       |        |         |        |
       |        |         |        |-->return true;
       |        |         |        |
       |        |         |    ! (true)
       |        |         |        |
       |        |         |        |
       |        |         |<------false
       |        |         |
       |        |         |
       |        |     ! (false)
       |        |         |
       |        |         |
       |        |<-------true
       |        |
       |        |
       |    ! (true)
       |        |
       |        |
       |<------false
       |
       |
      false