3

我刚刚遇到了一个棘手的问题。以下代码应该将单词拆分为 length 块numOfChar。函数调用自身，这使得函数内部不可能有结果列表 ( res)。但是，如果我将它作为全局变量保留在外部，那么具有不同输入值的函数的每次后续调用都会导致错误的结果，因为res不会被清除。

谁能帮我吗？

这是代码（如果您有兴趣，这是PySchools.com 的问题 7-23）：

res = []

def splitWord(word, numOfChar):        
    if len(word) > 0:
        res.append(word[:numOfChar])
        splitWord(word[numOfChar:], numOfChar)    
    return res

print splitWord('google', 2)
print splitWord('google', 3)
print splitWord('apple', 1)
print splitWord('apple', 4)
4

3 回答 3

5

纯递归函数不应该修改全局状态，这算作副作用。

而不是追加和递归，试试这个：

def splitWord(word, numOfChar): 
    if len(word) > 0:
        return [word[:numOfChar]] + splitWord(word[numOfChar:], numOfChar)
    else:
        return []

在这里，您在每次调用时将单词一次一块地切割成碎片，然后在上升时将碎片重建成一个列表。

这是一种称为尾递归的常见模式。

PS正如@e-satis所说，递归不是在 Python 中执行此操作的有效方法。另请参阅@e-satis 的答案，了解更详细的尾递归示例，以及使用生成器解决问题的更 Pythonic 方式。

于 2012-05-29T18:30:00.910 回答
2

这里完全不需要递归：

def splitWord(word, numOfChar):
   return [word[i:i+numOfChar] for i in xrange(0, len(word), numOfChar)]

如果您坚持使用递归解决方案，最好避免使用全局变量（它们使推理发生的事情变得非常棘手）。这是一种方法：

def splitWord(word, numOfChar):
   if len(word) > 0:
      return [word[:numOfChar]] + splitWord(word[numOfChar:], numOfChar)
   else:
      return []
于 2012-05-29T18:29:48.473 回答
2

为了详细说明@Helgi 的答案，这里有一个性能更高的递归实现。它更新列表而不是对两个列表求和（这导致每次都创建一个新对象）。

此模式强制您将列表对象作为第三个参数传递。

def split_word(word, num_of_chars, tail):

    if len(word) > 0:
        tail.append(word[:num_of_chars])
        return split_word(word[num_of_chars:], num_of_chars, tail)

    return tail

res = split_word('fdjskqmfjqdsklmfjm', 3, [])

这种形式的另一个优点是它允许尾递归优化。它在 Python 中毫无用处，因为它不是一种执行这种优化的语言，但如果你将这段代码翻译成 Erlang 或 Lisp，你将免费获得它。

请记住，在 Python 中，您受到递归堆栈的限制，没有办法摆脱它。这就是为什么递归不是首选方法的原因。

您很可能会使用生成器，使用yieldand itertools（一个操作生成器的模块）。这是一个可以将任何可迭代对象拆分为块的函数的一个很好的示例：

from itertools import chain, islice

def chunk(seq, chunksize, process=iter):
    it = iter(seq)
    while True:
        yield process(chain([it.next()], islice(it, chunksize - 1)))

现在如果你开始学习 Python 会有点复杂，所以我不指望你现在完全掌握它，但你能看到它并知道它的存在是件好事。您稍后会回来讨论它（我们都这样做了，Python 迭代工具一开始是压倒性的）。

这种方法的好处是：

  • 它可以分块任何可迭代的，不仅仅是字符串，还包括列表、字典、元组、流、文件、集合、查询集，你可以命名它......
  • 它接受任何长度的迭代，甚至是一个未知长度的迭代（想想这里的字节流）。
  • 它占用的内存很少，因为生成器最好的一点是它们会一个接一个地动态生成值，并且在计算下一个结果之前它们不会存储先前的结果。
  • 它返回任何性质的块，这意味着您可以拥有 x 个字母的块、x 个项目的列表，甚至是生成 x 个项目的生成器（这是默认设置）。
  • 它返回一个生成器，因此可以在其他生成器的流中使用。将数据从一个生成器传输到另一个生成器（bash 风格）是一种出色的 Python 能力。

要获得与您的函数相同的结果，您将执行以下操作：

In [17]: list(chunk('fdjskqmfjqdsklmfjm', 3, ''.join))
Out[17]: ['fdj', 'skq', 'mfj', 'qds', 'klm', 'fjm']
于 2012-05-29T21:10:26.477 回答