双递归教育的例子

Question

这个功能对我来说没有意义.我已经在所有地方添加了印刷语句,以弄清楚发生了什么,我仍然没有得到它.如果有人能向我解释,我将不胜感激.

def f(s):
    if len(s) <= 1:
        return s
    return f(f(s[1:])) + s[0]

print(f("mat"))

这就是我看到的情况.所以我们从长度为3的字符串开始并绕过if语句.我们首先在内部f(s [1:])上工作.所以现在我们有一个长度为2("at")的字符串再次绕过if语句并输入f(s [1]),它给出了长度为1("t")的字符串,最后输入if语句并返回"T".对我来说,这条路很冷.

从我的print语句中,我看到创建了一个长度为2的新字符串,然后返回"a".最终产品最终成为"atm".由于"+ s [0]"部分我得到了"m"被标记,但为什么它是"atm"而不是"tam"？

我老老实实地花了几个小时,不能下雨.任何帮助,将不胜感激.

Answer 1

通过使用他们正在执行的操作填充函数调用,将整个事情扩展为长时间步骤.处理最深/最嵌入的第一个括号.在添加之前处理函数调用.

为清楚起见,我将忽略所有字符串引号.

f(mat)           -> mat is 3 chars:
                    call f on at for f(at), and call f on that.
                    add m.

f(f(at))+m       -> inner f(at), at is 2 chars:
                    call f on t for f(t), and call f on that.
                    add a.

f(f(f(t))+a)+m   -> innermost f(t) returns t.

f(f(t)+a)+m      -> inner f(t) returns t as well.

f(ta)+m          -> [here, the first f(f(at)) has been reduced to f(ta)]
                    ta is 2 chars:
                    call f on a for f(a), and call f on that.
                    add t.

f(f(a))+t+m      -> inner f(a) returns a.

f(a)+t+m         -> f(a) returns a as well.

a + t + m        -> 

atm              -> everything reduces to atm.

Answer 2

简短版本：a和t被交换两次，因此内部f("at")调用返回"ta"，然后外部f()调用被传递"ta"并返回"at"。

更长的版本：我不会明确地为您说明它，因为您不会通过这种方式学到那么多，但请考虑这个函数，它是完全等效的：

def f2(s):
    if len(s) <= 1:
        return s
    x = f2(s[1:])
    return f2(x) + s[0]

print(f2("mat"))

当你打电话时f2("mat")，s[1:]是"at"。现在，返回什么f2("at")？将该值（ 的值x）代入f2(x) + s[0]表达式中，看看会得到什么。

尝试遍历f2("at")和的值f2("ta")，看看是否可以发现发生了什么。如果您在工作 15-20 分钟后仍然需要帮助，请对此答案发表评论，我将对其进行更多扩展。