CODEWITHSUNDEEP
c#if-statementrecursion
jeroen wiskas
jeroen wiskas

Reputation: 13

c# recursion check if even

I need help understanding this. I really don't understand this piece of code and could someone here explain exactly what happens?

So this is the code:

static bool IsEven(int n)
{
    if (n == 0) return true;

    if (IsEven(n - 1))
    {
        return false;
    }
    else
    {
        return true;
    }
}

And then I do this:

Console.WriteLine(IsEven(10));

How does it actually work? If I enter in number 10, it prints out true. If I enter number 7, it prints out false. But I don't understand why it even works.

It checks if the number is 0, then it returns true. But I entered 10 (which clearly is not 0) and it still print out true. Then it checks number -1.

So that would be 10-1, which is 9. But how does it know that 9 is NOT even? (it returns false).

I don't understand this code, but it works. I am so confused honestly.

Upvotes: 1

Views: 1419

Answers (3)

Eugene Sh.
Eugene Sh.

Reputation: 18381

Let's try to understand it starting with mathematics. 0 is even by a definition. We know that each addition of 1 will flip the "eveness" of the number. So we can write the reursive rule as follows:

Base case: IsEven(0) = true
Induction: IsEven(n) = NOT( IsEven(n-1) ) ; for n > 0

So we can easily code it:

static bool IsEven(int n)
{
    if (n == 0) return true;
    return (!IsEven(n - 1));
}

So far so good. But note, the (!A) can be rewritten instead as this awkward condition:

if (A)
{
    return false;
}
else
{
    return true;
}

You can convince yourself by substituting A with true or false.

Now we just substitute A with IsEven(n-1) and paste it to the above code and get the original

static bool IsEven(int n)
{
    if (n == 0) return true;

    if (IsEven(n - 1))
    {
        return false;
    }
    else
    {
        return true;
    }
}

Upvotes: 1

TyCobb
TyCobb

Reputation: 9089

Think of it like this: 

IsEven(3)
|   IsEven(2)
|   |   IsEven(1)
|   |   |   IsEven(0)
|   |   |   Return True
|   |   Return False
|   Return True
Return False

It's always going to eventually get to 0 if the input was non-negative and start going back up the chain. IsEven(1) above means that IsEven(2) and IsEven(3) is still being executed. Those method calls have not ended yet.

What the IsEven(n) method is doing is returning the opposite of the lower number. Passing in 4 means it has to check if 3 is even. Since it isn't, it will return true for 4.

As others have mentioned, I would suggest writing it out, but I would also suggest a breakpoint and using the Step-In IDE command to go into the IsEven method so you can watch the parameter value change and follow the flow as it is happening. Or at least add in some Console.WriteLine for you watch.

Upvotes: 2

Equalsk
Equalsk

Reputation: 8224

Walk through it logically using a lower number like 3 so there are not as many recursions to think about.

The first time we call IsEven(3); it does this:

if (3 == 0) return true;

Well 3 does not equal 0 so it continues with this:

if (IsEven(3 - 1))

Which is the same as:

if (IsEven(2))

So now we're in the next call to IsEven. The first check is 2 == 0 which of course it is not, so it continues with IsEven(2 - 1).

Now we're in the third call to IsEven with IsEven(1). Well again 1 == 0 is not true so it continues with IsEven(1 - 1).

Now we're in the final (fourth) call to IsEven with IsEven(0). Well now 0 == 0 is true so we return true back to the third call.

So now back in the third call IsEven(1 - 1) is true so it performs the action in the first bracket which is to return false.

Back in the second call IsEven(2 - 1) is now false so it takes the action in the second bracket which is return true.

Back in the first call IsEven(3 - 1) is true so it takes the action in the first bracket which is to return false indicatining that 3 is indeed not even.

It's like integer inception.

Of course a real example would probably use the modulo % operator like this.

public static bool IsEven(int number)
{
    return number % 2 == 0; 
}

Upvotes: 3

Related Questions