CODEWITHSUNDEEP
pythonpython-2.7
wnnmaw
wnnmaw

Reputation: 5534

Unexpected behavior of tuple boolean evaluation

I am working on a code golf and attempting to write a recursive function using the tuple boolean evaluation syntax ((a,b)[bool]). My function is as follows (with some helpful prints):

def b(A,k,n):
 m=len(A)/2
 print "A: ", A
 print "m: ", m
 print "n: ", n
 print "A[m]", A[m]
 if A[m]==k:return m+n
 # return (m+n,(b(A[m:],k,m+n),b(A[:m],k,n))[A[m]<k])[A[m]!=k]
 return m+n if A[m]==k else (b(A[:m],k,n) if A[m]>k else b(A[m:],k,m+n))

Arguments A, k, and n are the input list to search, the key, and the index in the original A which a sublist starts at. m is the middle entry of the list. If I search [1,2,3,4,5,6,7] for 6, I would expect to see the following output

A:  [1, 2, 3, 4, 5, 6, 7]
m:  3
n:  0
A[m] 4
A:  [4, 5, 6, 7]
m:  2
n:  3
A[m] 6

The correct output and result are produced with the non-commented return statement. However, when I attempt to use the commented return statement (which should be equivalent), I receive a recursion depth error.

Moreover, if I replace one of the recursive calls with a determinate value, then search for a value on the edge, it functions as expected. For example, searching for 6 in [1,2,3,4,5,6,7] works correctly if my return statement is:

return (m+n,(b(A[m:],k,m+n),"anyValue")[A[m]>k])[A[m]!=k]

"anyValue" is never returned by my conditional in this case, so why does it matter what value I put in there?

Why do these two statements evaluate differently?

Upvotes: 1

Views: 113

Answers (2)

user2357112
user2357112

Reputation: 281624

When you do

thing() if condition else other_thing()

only one of thing() and other_thing() is evaluated. The one that isn't returned doesn't get evaluated at all, so you can do things like

base_case_value if base_case_condition else continue_recursing()

and the recursion will stop at the base case.

When you do

(continue_recursing(), base_case_value)[base_case_condition]

Python needs to build the tuple before it can be indexed, so both base_case_value and continue_recursing() are evaluated no matter what. Your function doesn't stop when it hits the base case.

Upvotes: 2

tdelaney
tdelaney

Reputation: 77377

The problem is that the two statements aren't equivalent. In the working "if" case, you only call b once per round. In the commented out "tuple boolean" case, you evaluate both b conditions before selecting which one to use with the boolean selector. Since b is recursive, and you always run the "bad" non terminating side along with the "good" terminating side, you get max recursion error.

Upvotes: 1

Related Questions