python - 如何在不转换为整数的情况下递归递增二进制数(以列表形式)？

Question

例如，给定列表 [1, 0, 1] 代码将返回 [1,1,0]。其他例子:

[1,1,1] -- > [1,0,0,0]
[1,0,0,1] --> [1,0,1,0]

我很难理解递归的基本情况是什么，以及如何针对 (n-1) 情况实现。

def increment_helper(number):
    newNum = []
    if len(number) ==1:
        if number[0] == 1:
            carry = 1
            newNum.append(0)

        else:
            carry = 0
            newNum.append(1)
    else:
        return increment_helper(number-1)
    return newNum

所以我确定这里有很多错误，特别是我如何调用我的递归，因为我不确定如何在存储以某种方式删除的数字时在列表上递归。 else return 语句显然不正确，但我将其用作占位符。我不确定使用什么条件作为增量的基本情况。我想我应该使用一个 carry 变量来跟踪我是否携带了一个，但除此之外我还不知道如何继续。

Answer 1

啊哈!好吧，你知道你在做什么。基本大纲是

基本案例:我怎么知道我什么时候完成了？

当您用完数字时，您就完成了。 number 应该是单个数字的列表；检查它的长度以确定何时不会重现。

递归案例:下一步是什么？

递归的一般概念是“做一些简单的事情，将问题减少一点，然后用较小的问题递归”。您在这部分的工作是对一位数字进行加法运算。如果你需要继续下去(那个数字有进位吗？)，然后重复。否则，您将拥有完成所需的所有信息。

具体应用

您的递归步骤将涉及调用 increment_helper 少一位:不是 number - 1，而是 number[:-1]。

从每次递归返回后，您将然后想要附加刚刚完成的数字。例如，如果您递增 1101，您的第一个调用将看到右侧递增的那个有一个进位。新数字是 0，你必须重复。按住 0 一会儿，用 110 给自己打电话，然后得到那个电话的结果。将您保存的 0 附加到它，然后返回到您的主程序。

这会让你动起来吗？