首页
学习
活动
专区
圈层
工具
发布
社区首页 >问答首页 >从递归函数返回集合

问从递归函数返回集合
EN

Stack Overflow用户
提问于 2014-09-04 02:35:16
回答 2查看 2K关注 0票数 0

我编写了一个简短的程序来显示DFA的可能输出。事实上,它给出了预期的结果。但是我一直在尝试重写这个函数,以便它返回结果,而不是使用全局变量--我想不出怎么做。请有人解释一下,如果不使用全局变量,我将如何做到这一点?

代码语言:javascript
复制
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")
EN

回答 2

Stack Overflow用户

回答已采纳

发布于 2014-09-04 02:42:02

这里有两种选择:自上而下的积累,或自下而上。

如果你做的是自下而上的话,你可以不需要任何变异就能做到。这确实使将递归编写为尾调用变得更加困难(有时是不可能的),但这很好,因为(a) Python无论如何都不会消除尾调用,而且(b)即使这样做了,算法也不会受益,因为它会进行多次调用。所以,我先展示一下:

代码语言:javascript
复制
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"))

要做到自顶向下,只需将result传递给state和str,就像向下传递一样:

代码语言:javascript
复制
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.

问题是,这不会返回结果,而是将其作为参数--您必须在顶层传递一个空集,如下所示:

代码语言:javascript
复制
result = set()
gen_strings(max_length, result=result)

但你总能把它包起来。将gen_strings重命名为gen_strings_r,然后编写如下:

代码语言:javascript
复制
def gen_strings(max_length, state="A", str=""):
    result = set()
    gen_strings_r(max_length, state, str, result)
    return result

或者你可以将两者结合起来,向下传递一个值,用于构建一个向上返回的值。这给了你自下而上(避免变异)和自上而下(允许尾叫)的好处,这使得它成为函数式语言中非常常见的成语,尤其是纯函数式语言。但在这种情况下,它并不比普通的自下而上更有优势,而且它需要对代码进行更大的更改,所以我不会费心地编写它。

票数 2
EN

Stack Overflow用户

发布于 2014-09-04 02:50:14

你可以做个了结:

代码语言:javascript
复制
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
票数 0
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/25656475

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档