Can someone walk me through the process of this Recursion?

Question

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))
print(is_even(3))

Answer 1

Hi Kevin!

I know this example is in the Python tutorial, but I'm not a big fan of this one. It's neither simple nor efficient. Anyway, let's work this out. I'm using imperfect notations, but hope it is clear...

is_odd(1)
= not is_even(1)
= not is_odd(1-1) [since 1 != 0]
= not is_odd(0)
= not not is_even(0)
= not not True
= not False
= True

is_even(3)
= is_odd(3-1) [since 3 != 0]
= is_odd(2)
= not is_even(2)
= not is_odd(2-1) [since 2 != 0]
= not is_odd(1)
...
= not True [Following the steps above]
= False

What's the code doing really?

The is_even() function has a base case: it returns True when the argument x is 0. This is a characteristic feature of every recursion: we need a way to stop the recursive process at some point. Some call it the termination condition.

Now when x is not zero, the is_even() function returns is_odd(x-1). Why? Because, when x-1 is odd, then x is even, and when x-1 is even, x is odd. This brings us to the second characteristic feature of recursion (and the reason behind its name): calling itself with a smaller argument. (Here we have two functions that play ping pong among themselves, but the idea is still the same.)

is_odd() employs an even simpler logic: if x is even, the it is not odd, and vice-versa. So it just returns not is_even(x).

So that's recursion for you: it defines a base case, and keeps calling itself with a smaller /simpler argument until it reaches the base case.

Let me know if anything sounds confusing :)