建立从递归算法

发电机我有我使用走在红黑树，和存储各种节点信息（列表中storage）递归方法。建立从递归算法

def _walk (self, storage, func, starting_node) : 
    if starting_node is not self._nil : 
     self._walk(storage, func, starting_node.left) 
     storage.append(func(starting_node)) 
     self._walk(storage, func, starting_node.right)

不过，我想，这样它建立一个发电机（从我的理解这应该节省时间和内存）重新实现此方法。什么是“最好”的做法？

来源

2012-11-05 rectangletangle

我不认为它会为你节省多少堆栈电子量 - 除非你的意思，使存储的发电机，而不是一个列表。 –

gnibbler，这正是我的意思。感谢让我澄清。 – rectangletangle

通过从步行解耦动作开始

def _walk (self, starting_node) : 
    if starting_node is not self._nil : 
     for x in self._walk(starting_node.left): 
      yield x 
     yield starting_node 
     for x in self._walk(starting_node.right): 
      yield x 

def traverse(self): 
    starting_node = ???  # maybe these are passed as 
    func = ???    # parameters to traverse 
    for node in self._walk(starting_node): 
     yield func(node)

traverse大致相当于

imap(func, self._walk(starting_node))

或该发电机表达

(func(x) for x in self._walk(starting_node))

可以减少第使用手动优化尾递归

def _walk (self, starting_node) : 
    while starting_node is not self._nil : 
     for x in self._walk(starting_node.left): 
      yield x 
     yield starting_node 
     starting_node = starting_node.right

来源

2012-11-05 03:44:52

如果我没弄错，为'_walk'递归调用不会产生任何东西。 – georg

@ thg435，你没有错 - 固定。 –

def _walk (self, func, starting_node) : 
    if starting_node is not self._nil : 
     for x in self._walk(func, starting_node.left) : 
      yield x 
     yield func(starting_node) 
     for x in self._walk(func, starting_node.right) : 
      yield x

来源

2012-11-05 03:49:52 light

建立从递归算法

回答

相关问题