Hiểu và hình dung đệ quy

Question

tôi nhắc đến nhiều câu hỏi ở đây về đệ quy nhưng tôi không thể hiểu làm thế nào đệ quy làm việc cho vấn đề này cụ thể: chương trình đệ quy để có được tất cả sự kết hợp của các nhân vật trong một chuỗi bằng 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') 

Tôi đã in nó các giá trị để tôi có thể thấy những gì đang xảy ra. Đây là kết quả:

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 

Full đầu ra: http://pastebin.com/Lg3pLGtP

Như tôi đã trình bày trong đầu ra, làm thế nào tiền tố trở thành 'ab'?

Tôi đã cố gắng hình dung các cuộc gọi đệ quy cho combi (tiền tố + s [0], s [1:]). Tôi có hiểu nó đúng không?

Answer 1

Có hai cuộc gọi đệ quy đến combi() trong hàm. Vì vậy, đường dẫn của các cuộc gọi không phải là một dòng duy nhất, mà là một cây nhị phân mà dĩa. Những gì bạn đang nhìn thấy là nửa thứ hai của cây.

Answer 2

Tôi đã vẽ cây đệ quy. Theo Depth First Traversal, kết quả cuối cùng là ở nút cuối cùng. Hiển thị trực quan này giúp hiểu điều gì đang xảy ra.

Answer 3

Theres a python module cho rằng

tạo với:

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