Понимание и визуализация рекурсии

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

Как я показал на выходе, как же префикс стал «аб»?

Я попытался визуализировать рекурсивные вызовы для combi (префикс + s [0], s [1:]). Правильно ли я это понимаю?

Answer 1

В функции есть два рекурсивных вызова: combi(). Таким образом, путь вызовов - это не одна строка, а двоичное дерево, которое вилки. То, что вы видите, это вторая половина дерева.

Answer 2

Я нарисовал дерево рекурсии. По глубине Первый обход конечный результат получается на последнем узле. Эта визуализация помогает понять, что происходит.

Answer 3

Theres a python module для этого

Сформирован с:

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