遞歸函數（比特移位）

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