递归技术，而不是蟒蛇

名单技术，我有一个功能，它的名字是positive_negative递归技术，而不是蟒蛇

def positive_negative(list_changes): 
    """ (list of number) -> (number, number) tuple 

    list_changes contains a list of float numbers. Return a 2-item 
    tuple where the first item is the sum of the positive numbers in list_changes and 
    the second is the sum of the negative numbers in list_changes. 

    >>> positive_negative([0.01, 0.03, -0.02, -0.14, 0, 0, 0.10, -0.01]) 
    (0.14, -0.17) 
    """

我可以用列表技术如下写这个函数：

def positive_negative(list_changes): 
    pos = sum([item for item in list_changes if item > 0.0]) 
    neg = sum ([item for item in list_changes if item < 0.0]) 
    return pos, neg

，这是一个很好的解决方案。现在我的问题是如何使用递归技术来解决相同的功能，我已经尝试了下面的代码，但不幸的是有一些错误。

def positive_negative(list_changes): 
    pos = 0.0 
    neg = 0.0 
    if len(list_changes)== 0: 
     pos =+ 0.0 
     neg =+ 0.0 
     return pos,neg 
    else: 
     if list_changes[0] > 0.0 : 
      pos =+ list_changes[0] 
     else: 
      neg =+ list_changes[0] 
     positive_negative(list_changes[1:]) 


    return pos,neg

你能帮我找出我的错误是什么，以及如何得到正确的递归函数。

谢谢

来源

2013-04-03 mazlor

作为一个侧面说明，解决问题的更好方法是使用生成器表达式而不是列表理解 - 只是删除方括号，而列表版本的工作原理完全相同，除了不必为了传递而构建整个列表它总结，它建立它懒惰。 – abarnert 2013-04-03 23:54:36

谢谢你，宝贵的意见。 – mazlor 2013-04-03 23:59:20

你的第一个问题是这样的：

pos =+ list_changes[0]

Python没有一个=+操作。所以，这相当于：

pos = (+list_changes[0])

由于list_changes[0]是一个数字，+n是一样的n为任意数量的（除非在某些边缘情况下它不事在这里），你只是更换pos每一次，而不是增加它。

你可能想这样的：

pos += list_changes[0]

但是，你正在尝试使用+=在所有的事实是一个更根本的误解。堆栈上的每个positive_negative都有自己的pos和neg值。它们从0.0开始，然后向它们添加0.0或list_changes[0]，然后调用一个不影响它们的函数，然后返回它们。所以，你最终要返回0.0, list_changes[0]或list_changes[0], 0.0;不管在列表后面出现什么，都不会影响结果。

如果您希望递归函数调用添加任何内容，您需要对其返回值进行一些操作。事情是这样的：当然

def positive_negative(list_changes): 
    if len(list_changes)== 0: 
     return 0.0, 0.0 
    else: 
     pos, neg = positive_negative(list_changes[1:]) 
     if list_changes[0] > 0.0: 
      pos += list_changes[0] 
     else: 
      neg += list_changes[0] 
     return pos, neg

这个解决方案显然不是尾递归...但是，这并不重要，因为Python没有做尾递归优化反正。我认为这是您尝试完成的最接近的解决方案。

来源

2013-04-03 23:56:27 abarnert

我知道，递归是不是在Python一个很好的选择，只是想学习如何使用这种方式，我喜欢这种解决方案已提出，谢谢。 – mazlor 2013-04-04 00:15:50

使用一些蓄电池（PSUM，nsum）：

def positive_negative(list_changes, psum=0, nsum=0): 
    if len(list_changes) == 0: 
      return psum, nsum 
    if list_changes[0] < 0: 
      nsum += list_changes[0] 
    else: 
      psum += list_changes[0] 
    return positive_negative(list_changes[1:], psum, nsum) 

# and another version: 
def positive_negative2(list_changes, psum=0, nsum=0): 
    if len(list_changes) == 0: 
      return psum, nsum 
    if list_changes[0] < 0: 
      return positive_negative(list_changes[1:], 
          psum, nsum + list_changes[0]) 
    return positive_negative(list_changes[1:], 
          psum + list_changes[0], nsum) 

print positive_negative([0.01, 0.03, -0.02, -0.14, 0, 0, 0.10, -0.01])

输出

(0.14, -0.17)

作为一个侧面说明，蟒蛇没有做尾调用优化的使用递归的时候，所以要谨慎。如果您的列表中有大约1000个项目，上述功能将失败。

来源

2013-04-03 23:57:21 perreal

这真的只是模拟迭代与尾递归（这是毫无意义的Python，它有反复和不优化尾递归）。对于OP来说，理解它是如何工作的确是值得的，但这可能不是他想要做的。 – abarnert 2013-04-04 00:05:21

这并不是说“使用递归是不建议”，那就是使用递归_TO模拟不建议iteration_（与年轻气盛，以确保您的递归尾递归是没有意义的）。有很多自然递归问题，递归限制足够深入。（当然，你仍然可以使用Python，只要你坚持限度内学习递归。） – abarnert 2013-04-04 00:08:19

@abarnert，感谢您的评论。尽管如此，尾递归也有利于清晰。 – perreal 2013-04-04 00:10:41

不使用尾递归：

import operator 


def positive_negative_change(l): 
    if not l: 
     return (0.0, 0.0) 

    if l[0] >= 0: 
     return tuple(map(operator.add, (l[0], 0.0), 
         positive_negative_change(l[1:]))) 
    else: 
     return tuple(map(operator.add, (0.0, l[0]), 
         positive_negative_change(l[1:])))

在Python，如果你是一个会用发电机或尾递归... 到刷牙递归刚刚看了小阴谋家

来源

2013-04-04 00:05:32 locojay

递归技术，而不是蟒蛇

回答

相关问题