CODEWITHSUNDEEP
pythonrecursion
Sam Dillard
Sam Dillard

Reputation: 690

Recursively checking for odd or even

In this code:

def is_even(x):
  if x == 0:
    return True
  else:
    return is_odd(x-1)

def is_odd(x):
  return not is_even(x)

print(is_even(2))
print(is_odd(2))

I keep going through this in my head and wondering how it's working. It seems to me that eventually x in is_even(x) will return True every time. However, when I run the code, it works perfectly fine and returns True and False appropriately. Can someone explain how that's happening?

I understand the basic concept of recursion and fully understand how the famous factorial example works. However, this one is hard for me to wrap my head around.

Feeling inept right now...

Upvotes: 4

Views: 2692

Answers (5)

cs95
cs95

Reputation: 402333

It always helps to decompose a recurrence relation till you find its base case.

is_even(2) => return is_odd(1) 
           => return not is_even(1) 
           => return not is_odd(0)
           => return not not is_even(0)
           => return not not True
           => return True            ---- (1)


is_odd(2) => return not is_even(2) 
          => return not True       [from (1)] 
          => return False

In general, from your recurrence functions, it is easy to observe that is_even(n) will return [not not not ... n times] True, while is_odd(n) will return [not not not ... n - 1 times] True. So the number of nots and hence the final expression depend on n (aha!). Well, that's certainly a roundabout way of asking whether

n % 2 == 0

Upvotes: 9

AChampion
AChampion

Reputation: 30258

Add a couple of print statements and you will see what it is doing:

from __future__ import print_function

def is_even(x):
    if x == 0:
        print('True')
        return True
    else:
        return is_odd(x-1)

def is_odd(x):
    print('not', end=' ')
    return not is_even(x)

>>> is_even(5)
not not not not not True
False
>>> is_odd(5)
not not not not not not True
True

Upvotes: 5

JoshKopen
JoshKopen

Reputation: 960

I think that all the other answers are great but potentially the easiest way to understand the problem is how many times the answer will get "not"ed. Every time it passes through the is_odd function a not will be added on to the final answer. True will always be returned but for even numbers, there will always be an even number of nots which cancel each other out, but for odd numbers they will always have an odd number of nots and therefore return false.

Upvotes: 1

Uriel
Uriel

Reputation: 16174

That's true; the recursion is supposed to end inside is_even.

And when that will happen, you'll know that the number you have is 0.

Now lets go backwards. This final state will be achieved by two cases - direct call to is_even(0) or a call from is_odd(0). In the first case - the result is all good. In the second - the result will be returned to the is_odd function, negated, and therefore will be falsy - giving a correct result.

Now, here the missing piece comes - the recursion: in order to reach this state, we need to decrease the argument each time, passing it through the opposite function - and that's exactly what we get with return is_odd(x-1).

Note: eventually this recursion leads to a chain of negations of the value True returned by the is_even. This chain is of length x where x is your number, and therefore odd or even in correspondence.

Therefore, the following code will do the same (lacking the is_odd nice side effect):

def is_even (x):
    res = True
    while x:
        res = not res
        x -= 1
    return res

Upvotes: 2

MSeifert
MSeifert

Reputation: 152607

Like in most cases it might be helpful to include simply prints to follow the execution:

def is_even(x):
    print('check if {} is even'.format(x))
    if x == 0:
        return True
    else:
        return is_odd(x-1)

def is_odd(x):
    print('check if {} is odd'.format(x))
    return not is_even(x)

Then in your cases:

>>> print(is_even(2))
check if 2 is even
check if 1 is odd
check if 1 is even
check if 0 is odd
check if 0 is even
True

>>> print(is_odd(2))
check if 2 is odd
check if 2 is even
check if 1 is odd
check if 1 is even
check if 0 is odd
check if 0 is even
False

So basically it decrements the number until it's 0. The point is just how many nots have been accumulated in the is_odd calls. If it's an even number of nots then the result will be True, otherwise False.

Upvotes: 3

Related Questions