递归函数（带移位）

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

原因是运算符优先级。位移运算符的优先级低于算术运算符。

默认情况下，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

运算符优先级。移位的优先级低于 addition/subtraction (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))

递归函数（带移位）

Recursion function (with bit shift)

python

bit-shift