Can anyone explain this recursion code!!

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

output:
True
False

Answer 1

The `is_odd` function is simply returning the inverse (`not` keyword) of the `is_even` function, and that is logically correct.

The recursion is happening in the `is_even` function, so let's break it down in parts:

(1) The base case of the recursion is when x = 0. When that happens, `is_even` returns True and the recursion ends.

(2) From (1) we conclude that x cannot be negative or you'll end up in an infinite recursive "loop". That's because we are passing x-1 to the `is_odd` function when the base case isn't met, which means the arguments passed to the functions are decreasing. If x is initially negative and it only decreases, then x = 0 never happens and the recursion doesn't end.

(3) If x > 0 the `is_even` function takes the logical assumption that for any x that is even, x-1 is obligatory odd. That is not hard to prove mathematically.

So by all means, what happens when you call, say, `is_odd(5)`, is that initially x=5 and it keeps getting passed from one function to another, until it x=0.

Answer 2

take a pencil and a sheet of paper and try with 5 and 4.

4 is even?
check if 3 is not even
check if 2 is even
check if 1 is not even
check if 0 is even

returns true
so 1 is not even
so 2 is even
so 3 is not even
so 4 is even.

Answer 3

is_even returns the same logical value as it receives.
is_odd returns the opposite, it reverses the outcome.
is_even is the only one that decrements x (x = x - 1).
The base case x=0 terminates returning True.
Look at the trivial cases first

is_even(0) returns True

is_odd(0) returns the opposite =False (one reverse)

is_even(1) returns the same as is_odd(0) =False (one reverse)

is_odd(1) returns the opposite = True (two reverses cancel out)

is_even(2) returns the same as is_odd(1) = True (2 reverses)

is_even(x)
If x is any positive* number it will go through an even number of reverses (=True) if it's even and an odd number (=False) if it's odd.

(*Yes this program fails to check for negative values and will cause a runtime error for those)

is_odd(x)
Reverses the outcome of is_even(x) and so produces False for even and True for odd.