递归函数（比特移位）

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 

以我头递归函数的输出应为：12 （6 + 4 + 2） 为什么这不是这样的？我必须说“393216”比我预期的数字“12”稍大。

我的期望：

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

所有共同= 12

Answer 1

的原因是由于运算符优先级。 Bitshift运算符的优先级低于算术。

默认情况下，x << 1 + recursion(x - 1)假定为x << (1 + recursion(x - 1))。

您可以通过使用括号覆盖默认优先级来解决问题。

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

print(recursion(3)) # 12 

Answer 2

运算符优先级。位移优先级低于加/减（see in docs）。因此，你需要

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))