此分治法有什么作用？

Question

我确信这很简单，这就是为什么我很沮丧的原因。我在一次采访中得到了这段代码，并被问及代码的计算内容和复杂程度。我还是很困惑。我尝试将输出记为2的底数，但仍然没有找到模式。这是代码：

def mystery(n):
  if n == 0:
    return 0
  if n % 2 == 0:
    return mystery(n/2)
  else:
    return mystery(2(n-1)) + 1

我知道第二行正在测试什么时候是偶数，但是，我仍然不明白此功能的整体作用。有任何想法吗？**编辑：将A更改为神秘。

Answer 1

假设A应该是对mystery的递归调用，则：

这实际上不是分而治之的算法。它只是以某种回旋方式返回n的二进制表示形式的1位的数目。

如果您逐步了解n为奇数时发生的情况，会更容易理解。然后对于某些n，2x+1 = x，并且mystery(n) =mystery(4x)+1=mystery(2x)+1=mystery(x)+1= mystery(floor(n/2))+1