La comprensione e la visualizzazione di ricorsione

Question

ho fatto riferimento a diverse domande qui circa la ricorsione, ma io non sono in grado di capire come la ricorsione funziona per questo particolare problema: programma ricorsivo per ottenere tutte le combinazioni di caratteri di una stringa in 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') 

Ho fatto stampare i valori in modo che io possa vedere cosa sta succedendo. Questa è l'uscita:

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 

uscita completa: http://pastebin.com/Lg3pLGtP

Come ho mostrato in uscita, come ha fatto diventare il prefisso 'ab'?

Ho provato a visualizzare le chiamate ricorsive per il combi (prefisso + s [0], s [1:]). Sto capendo bene?

Answer 1

Ci sono due chiamate ricorsive a combi() nella funzione. Quindi il percorso delle chiamate non è una singola linea, ma piuttosto un albero binario che si biforca. Quello che stai vedendo è la seconda metà dell'albero.

Answer 2

Ho disegnato l'albero di ricorsione. Per profondità First Traversal, l'output finale è ottenuto all'ultimo nodo. Questa visualizzazione aiuta a capire cosa sta succedendo.

Answer 3

Theres a python module per quella

Generato con:

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