理解和可视化递归

我这里提到的几个问题有关递归，但我无法理解递归如何为这个特殊的问题：递归程序，以获取在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（前缀+ s [0]，s [1：]）的递归调用。我理解它吗？ Visualization of Recursion

来源

2012-02-07 Bharat

函数中有两个递归调用combi()。因此，调用路径不是一条线，而是一个二叉树。你看到的是树的后半部分。

来源

2012-02-07 03:40:44 Amber

我想即第二递归调用'COMBI（前缀，S [1：]）'将以'combi（''，'bc'）'开始，并且通过形成b，bc的相同过程。这里在最后一步s [0]是'c'，当递归出前缀+ s [0]变成''+ c = c如果我理解正确吗？顺便说一句，我已经添加了一个完整的输出到问题的pastbin链接。 – Bharat 2012-02-07 03:48:28

如果您熟悉深度优先搜索，那么Amber提到的树就是如何遍历（或生成的，这取决于您想如何查看它）。 – kevintodisco 2012-02-07 03:56:27

@RBK：这是来自* combi（'a'，'bc'）''combi（'a'，'c'）'*的调用，它将创建第二个'prefix ='a''。 – Amber 2012-02-07 03:59:41

我画了递归树。通过深度优先遍历，最终输出得到最后一个节点。这种可视化有助于理解发生了什么。

Recursion Tree

来源

2012-02-07 18:26:50 Bharat

的Theres a python module对于

rcviz output

与生成：

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")

来源

2014-05-24 21:51:17 carlsborg

谢谢。看起来很有趣。我会尝试一下。 – Bharat 2014-05-25 04:08:38

这个库非常有用。谢谢。上投票。 – Bharat 2014-05-27 16:21:47

理解和可视化递归

回答

相关问题