CODEWITHSUNDEEP
pythonpython-3.xrecursion
spencer
spencer

Reputation: 189

Understanding recursive odd/even functions

I'm currently studying python from http://www.sololearn.com/Play/Python and I'm having trouble understanding why this code works.

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_odd(1))

I get how recursion works for a fibonacci and factorial but I can't wrap my head around this one.

Upvotes: 1

Views: 890

Answers (4)

Craig Burgler
Craig Burgler

Reputation: 1779

is_even's base case resolves to True. Since is_odd(x) returns not is_even(x), the value True will be a part of the expression returned by is_odd. The question is how many times will that True value be negated. By tracing the calls you can see it will be negated an even number of times, and hence "retain" its truthiness, when x is odd [e.g.: x=3 ==> (not (not (not (not True)))) == True] and an odd number of times, and hence "lose" its truthiness, when x is even [e.g.: x=2 ==> (not (not (not True))) == False]. There's probably some term from logic that names this general property of multiple negation.

Upvotes: 2

citaret
citaret

Reputation: 446

A little hint:

0 -> True
1 -> not True
2 -> not not True
3 -> not not not True
...

and so on.

Upvotes: 0

BPL
BPL

Reputation: 9863

That recursive function is really a bad way to teach recursion, you should apply recursion only when it's useful. In fact, test those functions with negative numbers and you'll get RuntimeError: maximum recursion depth exceeded errors.

To check parity numbers you'd better use % operator or & and operator, ie:

def is_even(x):
    return (x & 1) == 0


def is_odd(x):
    return (x & 1) == 1

That said, I think @Elazar & @DAXaholic answers should give you some insights about that buggy recursive function and wrap your mind about it.

Upvotes: 0

Elazar
Elazar

Reputation: 21585

It's based on an inductive definition of evenness:

  • Zero is even
  • If some number "n" is even, then "n+1" is not even
  • If some number "n" is not even, then "n+1" is even

"odd" is obviously "not even".

The code takes this definition, and checks it backwards - using recursion.

  • If i have zero, then it is even
  • If I have some other number "n" , then it is even if "n-1" is not - that is, if "n-1" is odd.

Upvotes: 2

Related Questions