How does this two-function recursion work?

Question

I've tried to understand for about 2 hours, but I'm still confused.

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

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

Recursion can be hard to understand at first. Once you take examples and walk through the code over and over again, you will figure it out. — zedfoxus, Sep 21 '21 at 02:15
This is a terrible example for learning recursion. This task [should be done with modulo](/a/13636743/4518341) (`%`), not repeated subtraction, and definitely not recursive subtraction. For n=499 or greater, it'll actually crash. Before asking here, try reading a tutorial first, like maybe [this one from RealPython](https://realpython.com/python-recursion/). — wjandrea, Sep 21 '21 at 03:15
BTW, welcome to Stack Overflow! Check out the [tour], and [ask] if you want tips. — wjandrea, Sep 21 '21 at 03:15
@wjandrea this could be a homework assignment where the instructor may have asked to create recursive functions instead of using modulo. The code may not be for efficiency but for learning purpose. I've heard of candidates being asked this question in interviews too. — zedfoxus, Sep 21 '21 at 04:01
@zedfoxus Then it's a bad exercise. There are tons of better applications for recursion, like traversing a recursive data structure, calculating a factorial, or the Collatz conjecture. And I just remembered, checking whether a number is odd can actually be simplified down to [`n & 1`](/a/37354069/4518341), which is even simpler than modulo. — wjandrea, Sep 21 '21 at 16:35
@wjandrea I am with you. This is not the best exercise to teach recursion. Factorial is a great one to learn memoization and recursion. The reality is that some teachers and interviewers give this example. — zedfoxus, Sep 21 '21 at 16:38
@Sheng_cai, you have 2 answers. If either of the answer was helpful, could you mark your chosen answer as accepted to put closure to your question? You can mark an answer as accepted by clicking on the check mark/tick mark by the answer (assuming you can). — zedfoxus, Oct 07 '21 at 16:52
This is a terrible idea to use in practice, but I think it's a fine example for demonstrating *mutual* recursion, which by nature is just more complex than recursion involving a single function. — chepner, Dec 09 '21 at 14:56

ddejohn · Answer 1 · 2021-09-21T02:54:16.000

For a recursive function to be successful (not recurse infinitely), it needs two things:

A recursive function must always have a base case (or exit condition)
A recursive function must tend towards the base case (or in other words, it must reduce the "size" of the problem to a smaller version of the same problem iteratively until the base case is reached)

The base case for this function is when n == 0 at which point the is_even() function returns a value, True, as opposed to returning the result of a function call.

What is_even() does is call itself with ever decreasing values of n until n == 0 at which point it returns True because it has reached the base case. The reason it works is because each recursive call tacks on a boolean not to its return value.

A call to this function will therefore return either an even number of negations in front of a True or an odd number of negations. If there are an even number of negations, then each pair will cancel out and you'll end up with True. If there are an odd number of negations, then you'll end up with one last not in front of a True.

Examples:

is_even(2) = not is_even(1)
           = not (not is_even(0))  # base case, returns True
           = not (not True)
           = not (False)
           = True

is_even(3) = not is_even(2)
           = not (not is_even(1))
           = not (not (not is_even(0)))  # base case, returns True
           = not (not (not True))
           = not (not (False))
           = not (True)
           = False

Note that the way your code is written, it's possible to recurse infinitely by initially calling is_even() with any negative integer (or any non-integral float). This will raise a RecursionError.

This is because even though is_even() satisfies the first rule (must have a base case), it violates the second rule in some cases (it doesn't always reduce the problem to a "smaller version of itself". In this case, by calling is_even(-1), each recursive call will subtract 1 from this value, thereby growing the size of the problem:

is_even(-1) = not is_even(-2)
            = not (not is_even(-3))
            = not (not (not is_even(-4)))
            .
            .
            .

Same thing happens with a non-integral float:

is_even(1.1) = not is_even(0.1)
             = not (not is_even(-0.9))
             = not (not (not is_even(-1.9)))
             .
             .
             .

score 2 · Accepted Answer · answered Sep 21 '21 at 02:13

In recursion, you keep on looping through the same operation until a condition breaks that loop. Let's go through your code with an example.

Is 1 odd or even?

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

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

print(is_even(1))

In this example,

def is_even(n) is called. n = 1
n is not 0, so the else condition is reached
Return is_odd(0) is called but we don't know what is_odd is
(A) So, is_odd(0) is called before the return can happen
..(B) is_odd returns the inverse of is_even(0), but we have to find out what is_even(0) is
.... is_even(0) checks whether n = 0. It is. So, it returns True
..(B) gets True. It returns the inverse of True, which is False. (B) returns False
(A) receives False and returns it to print
print prints False

Now try to follow the same logic with 2. You'll undergo more steps than above.

This is the kind of explanation that the OP would find most helpful, I think. +1 — Don Branson, Sep 21 '21 at 02:25

How does this two-function recursion work?

2 Answers2

Is 1 odd or even?