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

Question

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

我想重写这个函数，所以它使用递归。我目前失去了做什么。任何人都可以给我一些方向吗？

Answer 1

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

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

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

上述解决方案修复一个bug在你的代码，你在相反的顺序返回的数字。另请注意，为了生成正确的结果，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 2

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

1）基本情况 - 在其上要停止递归

2）一般情况下的条件 - 怎么办在每个输入，但基本情况

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

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