从递归函数返回一个集合

Question

我写了一个简单的程序，用来展示一个确定性有限自动机（DFA）可能的输出。现在这个程序能给出我预期的结果。不过，我一直在尝试重写这个函数，让它返回结果，而不是使用全局变量，但我就是搞不定。有人能告诉我怎么做，而不使用全局变量吗？

result  = set()

def gen_strings(max_length, state = "A", str = ""):
    global result
    if len(str) > max_length:
        return
    if state == "A":
        gen_strings(max_length, "B", str + "0")
        gen_strings(max_length, "C", str + "1")

    elif state == "B":
        gen_strings(max_length, "D", str + "1")

    elif state == "C":
        gen_strings(max_length, "D", str + "0")

    elif state == "D":
        result.add(str)
        gen_strings(max_length, "A", str + "0")
        gen_strings(max_length, "A", str + "1")

Answer 1

你可以使用一个闭包：

def gen_str(max_length, state = "A", str = ""):
    result  = set()    

    def rec_gen_strings(max_length, state = "A", str = ""):

        if len(str) > max_length:
            return
        if state == "A":
            rec_gen_strings(max_length, "B", str + "0")
            rec_gen_strings(max_length, "C", str + "1")

        elif state == "B":
            rec_gen_strings(max_length, "D", str + "1")

        elif state == "C":
            rec_gen_strings(max_length, "D", str + "0")

        elif state == "D":
            result.add(str)
            rec_gen_strings(max_length, "A", str + "0")
            rec_gen_strings(max_length, "A", str + "1")

    rec_gen_strings(max_length, state, str)
    return result

Answer 2

这里有两种选择：自上而下的累积，或者自下而上的累积。

---

如果你选择自下而上的方法，你可以在不改变任何东西的情况下完成。这确实会让你写递归时变得更难（有时候甚至不可能写成尾调用），但这没关系，因为（a）Python本身就不优化尾调用，和（b）即使它优化了，你的算法也不会受益，因为它会进行多次调用。所以，我先展示这种方法：

def gen_strings(max_length, state = "A", str = ""):
    if len(str) > max_length:
        return set()
    if state == "A":
        return (gen_strings(max_length, "B", str + "0") |
                gen_strings(max_length, "C", str + "1"))

    elif state == "B":
        return gen_strings(max_length, "D", str + "1")

    elif state == "C":
        return gen_strings(max_length, "D", str + "0")

    elif state == "D":
        return ({str} |
                gen_strings(max_length, "A", str + "0")
                gen_strings(max_length, "A", str + "1"))

---

如果你想用自上而下的方法，只需像传递state和str一样传递result：

def gen_strings(max_length, state="A", str="", result=None):
    if len(str) > max_length:
        return
    if state == "A":
        gen_strings(max_length, "B", str + "0", result)
        gen_strings(max_length, "C", str + "1", result)
    # etc.

问题在于，这种方法并不会返回结果，而是把结果作为参数传递——你需要在最上层传入一个空的集合，像这样：

result = set()
gen_strings(max_length, result=result)

但你总是可以把这个包起来。把gen_strings重命名为gen_strings_r，然后写这个：

def gen_strings(max_length, state="A", str=""):
    result = set()
    gen_strings_r(max_length, state, str, result)
    return result

---

或者你可以把两者结合起来，传递一个值下去，用来构建一个值再返回上来。这种方法结合了自下而上的优点（避免改变）和自上而下的优点（允许尾调用），这在函数式编程语言中非常常见，尤其是在纯函数式语言中。但在这种情况下，它并没有比简单的自下而上方法更有优势，而且需要对你的代码进行更大的改动，所以我就不写这个了。