如何将此函数重写为递归函数？ [英] How to rewrite this function as a recursive function?

问题描述

  def digits（n）：
 res = [] 
 while n> 0：
 res.append（n％10）
n / = 10 
返回资源
  

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

解决方案

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

  def数字（n）：
如果n < 10：
 return [n] 
返回数字（n / 10）+ [n％10] 
 
数字（123）
> [1，2，3] 
  

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

作品：

1. 如果数字小于10，则返回一个包含数字的列表，因为没有更多数字需要处理


2. 如果数字大于9，则获取当前数字中的最后一位数字，并将其添加到列表的末尾，递归调用 digits
   
   

   调用在一个较小的数字上 - 即没有我们刚刚处理的最后一位数字的数字。





 数字（123）在递归的每一步都看起来像这样：数字（123）=数字（123/10）+ [3​​] 
数字（12）=数字（12/10）+ [2] 
数字（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，[]）
  




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

I want to rewrite this function so it uses recursion. I'm currently lost as to what to do. Can anyone give me some direction?

解决方案

Here's a possible solution:

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

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

The above solution fixes a bug in your code, you were returning the digits in reverse order. Also notice that n must be an integer greater than or equal to zero for producing correct results.

Here's how it works:

1. If the number is less than 10, then return a list with the number, as there are no more digits to be processed
2. If the number is greater than 9, get the last digit in the current number and add it to the end of the list that results of recursively calling digits on a smaller number - namely, the number without the last digit that we just processed.

The call to digits(123) will look like this at each step of the recursion:

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

Now we go up the call stack:

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

EDIT :

Accepting @thg435's challenge, here's a tail-recursive solution:

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

这篇关于如何将此函数重写为递归函数？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！