如何理解二进制表示函数的递归

Question

我跟踪了以下代码，其中一部分对我来说没有意义：def bin_rep(n: int) -> str:     """Return the binary representation of n     >>> bin_rep(0)     "0"     >>> bin_rep(1)     "1"     >>> bin_rep(5)     "101"     """     if n > 1:         return bin_rep(n // 2) + bin_rep(n % 2)     else:         return str(n)我不了解的部分是，为什么要添加bin_rep(n//2)和bin_rep(n%2)。我知道没有添加项将无法正常工作，但是我无法解决为什么存在添加项的问题。

Answer 1

bin_rep(n)返回的二进制字符串表示形式n。

终止条件n <= 1是bin_rep(0) -> '0'或bin_rep(1) -> '1'。

bin_rep(2)必须返回'10'。为此，它计算：

bin_rep(2 // 2) + bin_rep(n % 2)

bin_rep(1) + bin_rep(0)

'1' + '0'  # String concatenation, not decimal addition!

'10'

...这是正确的答案。那应该有助于清除您的理解。

Answer 2

那不是加法。 bin_rep返回一个字符串。+字符串类型的运算符是串联。阅读为

binary representation of n right-shifted a bit

    concatenated with

binary representation of n's right-most bit

这样可以清除吗？