How does this code work?

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

It's very simple - these are recursive functions for determining even and odd numbers.

is_odd(1) # Out: not not True =>
not True = False => not False = True
Out: True.

https://code.sololearn.com/cGOKJEQr4QN2/?ref=app

Answer 2

@Shantanu , (this is not a criticism, just a statement of facts.)

your question was *how does this code works*. this is a very good question, since understanding recursion can be confusing.

however, using this particular task for recursion has disadvantages and risks.

using recursion can be helpful in various coding requirements. but in this case it is an absolutely anti-pattern. recursion depth and number of execution steps are an issues when processing larger numbers.

also the number of total executing steps is unnecessarily high. for the given samples we need 42 steps to get the result for an input of 1 and 2. this number of steps will increase by using larger numbers. maybe the code could be optimized, but the issues are inherent.

a simple and pythonic way could be 1 small function that returns True or False. this code 9 execution steps:

def is_even(num):
return num % 2 == 0

print(is_even(1)) # False
print(is_even(2)) # True

Answer 3

Solo ,

[EDITED]: have you tested your code with a negativ number like -1?

answering your question:

1) i used a debugger that calculates the number of execution steps and shows the result
2) which programming language is missing the modulo operator? 🙃, but we could also use this function:

def is_even(num):
return num // 2 == num / 2

Answer 4

It is a recursion between two alternating functions.
Tip: insert a print statement in both functions which will show you the sequence how they call each other (print the function name and the value of X).

Answer 5

So, as to your question, according to the diagnosis your programs works badly :)

Printing in the middle of the function is purely for debugging purpose so you would see what was happening, it did not change the return value.
The real problem is that your is_odd does not have a base case.

Answer 6

Solo
Another way to check for odd/even, is using binary and operator.
Try this:

for x in range(10):
print(x & 1)

Answer 7

Tibor Santa , the output is
0
1
0
1
0
1
0
1
0
1
Does 0 means that the number is even?

Answer 8

Tibor Santa 😄😄😄 I agree that this is the fastest way to solve, but let's do it without bitwise operations. 😉

Answer 9

Shantanu yes, or rather 0 is the negation of an odd number.

Answer 10

Solo the bitwise trick was only an answer to your second question, what if modulo didn't exist. But it is purely theoretical, because it's also simple to implement it with other math operators, like: x-x/2*2

The real problem with the alternating function presented at the beginning, is that it requires two base cases. 0 is even, and 1 is odd. The base cases can be handled in a single function, or one case in each branch.
Furthermore that implementation was not able to handle negative numbers.
Here I present the correct way to solve it and with random test cases.
Lothar is right that this implementation is very wasteful too, there are too many steps if large numbers must be analyzed, Python will quickly hit a memory limit.

https://code.sololearn.com/c44b74Uwo1p3/?ref=app

Answer 11

Solo , we can know if a number is even or odd without % by:
for i in range(10):
if (i//2)*2 == i:
print(f"{i} is Even")
else:
print(f"{i} is Odd")
Tell me if this is what you asked for or I got the question wrongly 😃.

Answer 12

Tibor Santa , I'm not disputing the conventional wisdom about recursion that Lothar kindly gave us. A recursive solution can only be compared to a loop, not to bitwise or mathematical calculations. But what I probably disagree with is that you're arguing that two main cases need to be considered in this case. What's great about this example is that it demonstrates that you can use the same base register for two functions. This is very important...

Answer 13

Solo you are right! Sorry, that was an oversight on my part. Somehow I had the impression that the example code was not working correctly for odd numbers, but in fact it is correct 😅
The test cases were misleading me.

Answer 14

Tibor Santa it's okay, everyone makes mistakes, but not everyone knows how to admit their mistakes. Happy coding! 🖐️😎

Answer 15

Shantanu, not exactly what I wanted, but it's my fault that I didn't explain well enough. I wanted you to write two functions similar to these recursive functions, but using a loop. That is, only logical operators can be used. So that you independently determine all the pros and cons of the recursive function.
Happy coding! 🖐️😎

Answer 16

Lothar , I have two questions:
1. Where did steps 9 and 42 come from? 🤔
2. Of course, the use of the division operator modulo for its intended purpose is a priority, but how would you write the code if it did not exist (%)? 😉

Answer 17

Lothar , about the modulo divisor - you tell me in which language it is absent, since you wrote that this is a pythonic solution 😉
And about step-by-step calculations of code execution, how about if the recursion is written in one line 😎

even = lambda n: 1 if n==0 else odd(n-1)
odd = lambda n: not even(abs(n))
print(odd(-498))
print(even(498))

Try writing two similar functions with a loop without any calculations. 😎

Answer 18

Tibor Santa, still after putting the print statement the output is same.