python - 如何将此函数重写为递归函数？

Question

def digits(n):
    res = []
    while n > 0:
        res.append(n % 10)
        n /= 10
    return res

我想重写这个函数，所以它使用递归。我目前不知道该怎么做。谁能给我一些指导？

Answer 1

要创建递归函数，您需要确定两件事：

1) 基本情况 - 您要停止递归的条件

2) 一般情况 - 除了基本情况外，每个输入要做什么

你已经找到了这两个东西，基本情况是 while 循环条件，一般情况是 while 循环的内部。尝试利用这些信息继续前进。

Answer 2

这是一个可能的解决方案：

def digits(n):
    if n < 10:
        return [n]
    return digits(n/10) + [n%10]

digits(123)
> [1, 2, 3]

上述解决方案修复了代码中的错误，您以相反的顺序返回数字。另请注意，n必须是大于或等于零的整数才能产生正确的结果。

以下是它的工作原理：

1. 如果数字小于 10，则返回包含该数字的列表，因为没有更多数字需要处理
2. 如果数字大于 9，则获取当前数字中的最后一位，并将其添加到递归调用digits较小数字的结果列表的末尾 - 即我们刚刚处理的没有最后一位的数字。

在递归的每个步骤中，对的调用digits(123)将如下所示：

digits(123) = digits(123/10) + [3]
digits(12)  = digits(12/10)  + [2]
digits(1)   = [1]

现在我们向上调用堆栈：

[1]
[1] + [2]
[1, 2] + [3]
[1, 2, 3]

编辑 ：

接受@thg435 的挑战，这是一个尾递归解决方案：

def digits(n):
    def loop(i, acc):
        if i < 10:
            return [i] + acc
        return loop(i/10, [i%10] + acc)
    return loop(n, [])

Answer 3

当您使用递归时，一个好的基础是检查两个案例，一个基本案例和一个递归案例。基本情况是程序返回的条件和结果，在您的情况下，基本情况将是当 n > 0 时（如果您将其视为 while 循环，这是 while 循环退出的条件）。循环未完成时会发生递归情况（可以有多个），如果您与 while 循环进行比较，这基本上是循环的主体。在递归案例结束时，您需要再次调用函数并更改输入，在本例中为 n/10。

因此，您的函数定义将类似于：

def digits(n):

对于基本情况，您要检查 n 是否为 0，如果是，则返回空列表：

    if n <= 0:
        return []

现在，在递归的情况下，您想将 n%10 附加到列表中并再次调用您的函数，只是您想用不同的 n 调用它，更改为您在 while 循环中所做的更改：

    else:
        return [n%10]+digits(n/10)

所以，如果你跟踪这个，对于每个递归情况，你​​都会得到一个包含 n%10 的列表，然后它会添加新调用的结果，这将是 (n/10)%10 或空列表。例如，使用 n=100 运行这个函数会像这样分解：

newlist = digits(100)
newlist = [100%10]+digits(100/10)
newlist = [100%10]+([10%10] + digits(10/10))
newlist = [100%10]+([10%10] + ([1%10] + digits(10/10)))
newlist = [100%10]+([10%10] + ([1%10] + ([])))
newlist = [0,0,1]

嵌套括号用于显示函数数字是如何内联重写的。

Answer 4

def digits(n):
    res = []
    res.append(n%10)
    n /= 10
    if n != 0:
        return res + digits(n)
    else:
        return res