Recursion function (with bit shift)

Question

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 so? I have to say that "393216" is slightly larger than my expected number of "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

Answer 1

The reason is related to the priority of the operator. Beeftrack operators have lower priority than arithmetic.

The default x << 1 + recursion(x - 1)is considered x << (1 + recursion(x - 1)).

You can fix the problem by overriding the default priority using parentheses.

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

print(recursion(3)) # 12

Answer 2

. , / (. ). ,

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

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