理解与可视化递归

Question

我在这里查了好几个关于递归的问题，但我还是不太明白递归在这个特定问题中是怎么工作的：

这是一个用Python写的递归程序，用来获取字符串中所有字符的组合：

st= []
def combi(prefix, s):
    if len(s)==0: return 
    else:
        st.append(prefix+s[0])        

        ''' printing values so that I can see what happens at each stage '''
        print "s[0]=",s[0]
        print "s[1:]=",s[1:]
        print "prefix=",prefix
        print "prefix+s[0]=",prefix+s[0]
        print "st=",st

        combi(prefix+s[0],s[1:])
        combi(prefix,s[1:])
        return st

print combi("",'abc')

我让程序打印出值，这样我就能看到发生了什么。这是输出结果：

s[0]= a
s[1:]= bc
prefix= 
prefix+s[0]= a
st= ['a']
s[0]= b
s[1:]= c
prefix= a
prefix+s[0]= ab
st= ['a', 'ab']
s[0]= c
s[1:]= 
prefix= ab
prefix+s[0]= abc
st= ['a', 'ab', 'abc']
s[0]= c
s[1:]= 
prefix= a  ----> How did prefix become 'a' here. Shouldn't it be 'abc' ? 
prefix+s[0]= ac
st= ['a', 'ab', 'abc', 'ac']
.........
.........
['a', 'ab', 'abc', 'ac', 'b', 'bc', 'c'] # final output

完整输出：http://pastebin.com/Lg3pLGtP

从输出中可以看到，前缀是怎么变成'ab'的呢？

我试着想象一下递归调用的过程，像这样：combi(prefix+s[0],s[1:])。我理解得对吗？

Answer 1

我画了一个递归树。通过深度优先遍历，最后的结果是在最后一个节点得到的。这个可视化图帮助我们理解发生了什么。

Answer 2

来自这个优秀的基于浏览器的Python递归可视化工具：

你可以把你的代码粘贴成：

st= []
def combi(prefix, s):
    if len(s)==0: 
        return 
    else:
        st.append(prefix+s[0])     
        combi(prefix+s[0],s[1:])
        combi(prefix,s[1:])
        return st

然后它会生成一个图表，你可以一步一步地查看每个调用。（最神奇的是，这段Python代码是在你的浏览器里通过WebAssembly执行的！）

你也可以查看一个独立的Python模块来实现这个功能

生成的代码是：

from rcviz import callgraph, viz
st= []
@viz
def combi(prefix, s):
    if len(s)==0: 
        return 
    else:
        st.append(prefix+s[0])     
        combi.track(st = st) #track st in rcviz 
        combi(prefix+s[0],s[1:])
        combi(prefix,s[1:])
        return st

print combi("",'abc')
callgraph.render("combi.png")

Answer 3

这个函数里有两个递归调用，也就是它会自己调用自己两次。所以，这些调用的过程不是一条直线，而是像一棵分叉的二叉树。你现在看到的就是这棵树的后半部分。