I saw an interesting post on social media the other day where they were discussing ways to implement an even or odd function. Here's one of the solutions that was given. 💻
def is_even(a):
return not is_odd(a);
def is_odd(a):
if (a == 1):
return True;
return is_even(a-1);
Take a moment to think about whether or not this will work.
Whenever I look at a solution like this I try to not only think about the common case, e.g. is_even(4), but also the uncommon or edge cases, e.g. is_even(0) or is_even(-1).
In the case of is_even(0) it starts off like this,
is_even( 0 )
is_odd( 0 )
is_even( -1 )
is_odd( -1 )
is_even( -2 )
is_odd( -2 )
is_even( -3 )
is_odd( -3 )
is_even( -4 )
is_odd( -4 )
is_even( -5 )
is_odd( -5 )
....
Since this is a Python script 🐍, it will continue this way until it reaches the maximum recursion depth.
RecursionError: maximum recursion depth exceeded while calling a Python object
One interesting thing about Python is that integers in Python have arbitrary precision. This means that Python will keep increasing the number of bits until it runs out of memory. To learn more about how Python stores integers, see this article, 🌐https://arpitbhayani.me/blogs/long-integers-python/.
So let's set Python aside for a moment and assume we're using 2's Complement with a fixed number of bits. In this case, something interesting happens.
Let's assume we have 3 bits to work with. This means we'd have a number system like that shown below.
If we start with is_even(0) once we get to is_even(-4) we'd return not is_odd(-4) then is_even(-4 - 1). This would be 100+111=1 011. We'd only keep 011 and since we added two negative numbers and got a positive result an 💥Overflow Exception would be raised. If we ignored this exception and continued on from is_even(3), we'd reach positive 1 and return the correct result, True.
So this code might actually work with some caveats, however, unclear recursive functions that require you to ignore exceptions are not a great solution. I'd much rather just return not bit 0. 🙂
-James Trimble
P.S. - If you're enjoying this newsletter, please share it with a friend. I'm thinking about discontinuing it or really limiting the number of articles if it doesn't get any traction. If you'd like it to continue, please share it. https://sendfox.com/theramblings
0 comments