+ 1

# Can someone walk me through the process of this Recursion?

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))

1 Respuesta

+ 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 :)