fonction Recursion (avec décalage de bits)

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 

Dans ma tête, la sortie de la fonction récursive doit être: 12 (6 + 4 + 2) Pourquoi est-ce pas le cas? Je dois dire que "393216" est légèrement plus grand que mon nombre attendu "12".

Mon attente:

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

Tous ensemble = 12

Answer 1

La raison est due à la priorité des opérateurs. Les opérateurs Bitshift ont une priorité inférieure à l'arithmétique. Par défaut, x << 1 + recursion(x - 1) est supposé être x << (1 + recursion(x - 1)).

Vous pouvez résoudre le problème en remplaçant la priorité par défaut à l'aide de parenthèses.

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

print(recursion(3)) # 12 

Answer 2

Priorité d'opérateur. Les décalages de bits ont une priorité inférieure à l'addition/soustraction (see in docs). Par conséquent, vous devez

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

comme actuellement votre fonction est équivalente à interpréter

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