是否可以“中断”递归函数并在以后继续？

Question

我有一个函数some_result = treesearch(node)（montecarlo树搜索的一种变体），它递归地搜索一棵大树。它决定通过next_node = expensive_heuristic(node)遍历树的顺序，然后在树的后面的叶子上传播结果。我必须执行许多这样的搜索，并且expensive_heuristic(...)可以成批高效地计算，例如通过SIMD

因此，我的想法是创建一个包含所有搜索/根节点的列表，批量计算expensive_heuristic以选择遍历的“方向”，并重复此操作，直到找到一个叶，并将结果传播回树

当然，我可以使用队列而不是递归来重新编写搜索（保留历史记录），但我很好奇是否可以保留递归样式。我是否可以“中断”递归并将其放入列表/队列中，以便在python的稍后阶段继续它

Answer 1

可以使用yield、yield from和send；感谢juanpa.arrivillaga在评论中的建议

下面的代码在随机二叉树中搜索多达10个节点，并返回其中的最大值。每当它必须计算用于指导搜索的heuristic时，它就会中断生成/搜索

import random


class Node(object):
    def __init__(self, heuristic_value):
        self.children = {"left": None, "right": None}
        self.child_values = heuristic_value
        self.value = random.randint(0, 100)
        self.terminal = random.random() > 0.9

    def add_leaf(self):
        if self.terminal:
            return self.value

        direction = self.select()
        if self.children[direction]:
            value = yield from self.children[direction].add_leaf()
        else:
            value = yield from self.expand(direction)
        value = self.backup(direction, value)

        return value

    def select(self):
        if self.child_values["left"] > self.child_values["right"]:
            return "left"
        else:
            return "right"

    def expand(self, direction):
        heuristic_value = yield
        child = Node(heuristic_value)
        self.children[direction] = child
        return child.value

    def backup(self, direction, value):
        self.child_values[direction] = value
        if value > self.value:
            return value
        else:
            return self.value


def heuristic():
    return {"left": random.randint(0, 100), "right": random.randint(0, 100)}


tree = Node(heuristic())
for _ in range(10):
    gen = tree.add_leaf()
    value = None
    while True:
        try:
            gen.send(value)
            value = heuristic()
        except StopIteration as value:
            max_val = value
            break

print(f"Largest Value: {max_val}")