如何以递归方式递增二进制数(以列表形式)而不转换为整数？

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语句显然是不正确的,但我将其用作占位符.我不确定使用什么条件作为增量的基本情况.我想我应该使用一个随身携带变量来跟踪我是否携带了一个,但除此之外,我仍然坚持如何继续.

Answer 1

这一步很“棘手”，因为每一步都有两件事要做：

1. 我当前查看的号码是多少？（二元问题0/1）
2. 应该增加吗？（我们有进位吗？）（二元问题是/否）

这导致了4个案例。

还有一个额外的“情况”是我们是否得到了一个列表，但这并不是那么有趣。

所以我会描述如下：

if not carry:
    # technically meaningless so just return the entire list immediately
    return list

# we have "carry", things will change
if not list:
    # assumes [] == [0]
    return [1]

if list[0]:
    # step on `1` (make it 0 and carry)
    return [0] + increment(rest_of_list)

# step on `0` (make it 1 and no more carry)
return [1] + rest_of_list

我强烈建议将列表更改为元组并使用它们。

另请注意，递归位于反向列表上，因此应用如下：

def increment_helper(lst, carry):
    if not carry:
        return lst

    if not lst:
        return [1]

    if lst[0]:
        return [0] + increment_helper(lst[1:], True)

    return [1] + lst[1:]


def increment(lst):
    # long but really just reverse input and output
    return increment_helper(lst[::-1], True)[::-1]

我通过立即返回列表（短路）使用了一些快捷方式，但是即使没有进位，您也可以通过进行递归来使其更加“纯粹”。