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

5th Oct 2018, 4:12 AM
Kevin
1 Resposta
+ 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 :)
5th Oct 2018, 6:55 AM
Kishalaya Saha
Kishalaya Saha - avatar