CODEWITHSUNDEEP
pythonbit-shift
Sebastian Nielsen
Sebastian Nielsen

Reputation: 4219

Recursion function (with bit shift)

def recursion(x):
    if x == 0:
        return 0
    else:
        return x << 1 + recursion(x - 1)

print(recursion(3)) # 393216


print(3 << 1) # 6
print(2 << 1) # 4
print(1 << 1) # 2

In my head the output of the recursion function should be: 12 (6+4+2) Why is this not the case? I must say "393216" is slightly bigger than my expected number "12".

My expectation:

--> return 1<<1==2 for 1
--> return 2<<1==4 for 2
--> return 3<<1==6 for 3
0 --> return 0 for 0

All together = 12

Upvotes: 5

Views: 956

Answers (2)

miradulo
miradulo

Reputation: 29710

Operator precedence. Bit shifts have lower precedence than addition/subtraction (see in docs). Hence you need 

def recursion(x):
    if x == 0:
        return 0
    else:
        return (x << 1) + recursion(x - 1)

as currently your function is being interpreted equivalent to 

def recursion(x):
    if x == 0:
        return 0
    else:
        return x << (1 + recursion(x - 1))

Upvotes: 4

cs95
cs95

Reputation: 402814

The reason is due to operator precedence. Bitshift operators have lower precedence than arithmetic.

By default, x << 1 + recursion(x - 1) is assumed to be x << (1 + recursion(x - 1)).

You can fix the issue by overriding the default precedence using parentheses.

def recursion(x):
    if x == 0:
        return 0
    else:
        return (x << 1) + recursion(x - 1)

print(recursion(3)) # 12

Upvotes: 8

Related Questions