理解和可視化遞歸

我這裏提到的幾個問題有關遞歸，但我無法理解遞歸如何爲這個特殊的問題：遞歸程序，以獲取在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

理解和可視化遞歸

回答

相關問題