有没有一种方法可以用递归计算二进制整数的位数

Question

所以我想制作这个函数的一个版本，但这次使用递归：

def binary_length(natural):
res = 1
while natural >= 2:
res += 1
natural //= 2
return res

我的看法是：

def binary_length_recursive(natural):
res = 1
while natural >= 2:
res += 1
natural //= 2
if res%2==0:
return res
else:
return binary_length_recursive(natural)

我看过推荐的文章，但对我的情况没有多大帮助。

Answer 1

递归函数的思想是递归本身就是循环。

你知道0和1有一个数字，你知道这个数字的其余部分用除以2来表示。因此：

>>> def binary_length(n):
...     if n <= 1:
...         return 1
...     return 1 + binary_length(n//2)
...

测试：

>>> [(n, binary_length(n)) for n in range(10)]
[(0, 1), (1, 1), (2, 2), (3, 2), (4, 3), (5, 3), (6, 3), (7, 3), (8, 4), (9, 4)]

Answer 2

您需要再次调用数字除以2的函数。

def binary_length(number):
if number < 2:
return 1
return 1 + binary_length(number // 2)