entendimiento y la visualización de la recursividad

que hace referencia a varias preguntas aquí acerca de la recursividad, pero no soy capaz de entender cómo la repetición funciona para este problema en particular: programa recursivo para obtener toda combinación de caracteres de una cadena en Python:entendimiento y la visualización de la recursividad

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

Lo he hecho imprimir los valores para que pueda ver lo que está sucediendo. Esta es la salida:

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

potencia total de salida: http://pastebin.com/Lg3pLGtP

Como he mostrado en la salida, ¿cómo se convierten prefijo 'ab'?

He intentado visualizar las llamadas recursivas para el combi (prefix + s [0], s [1:]). ¿Lo estoy entendiendo bien? Visualization of Recursion

Fuente

2012-02-07 Bharat

Hay dos llamadas recursivas a combi() en la función. Por lo tanto, la ruta de las llamadas no es una sola línea, sino un árbol binario que se bifurca. Lo que estás viendo es la segunda mitad del árbol.

Fuente

2012-02-07 03:40:44 Amber

I pensaron que la segunda llamada recursiva es decir, 'combi (prefijo, s [1:])' comenzaría como 'combi ('', 'bc')' y pasaría por el mismo proceso formando b, bc. Aquí en el último paso s [0] es 'c' y cuando vuelve a sacar el prefijo + s [0] se convierte en '' + c = c si lo entiendo ¿verdad? Por cierto, agregué un enlace de pastbin del resultado completo a la pregunta. – Bharat

Si está familiarizado con la búsqueda en profundidad, es como se cruza (o se genera) el árbol que Amber menciona, según cómo quiera verlo). – kevintodisco

@RBK: Es la llamada para 'combi ('a', 'c')' * de * 'combi ('a', 'bc')' que está creando el segundo 'prefix = 'a''. – Amber

Dibujé el árbol de recursión. Por profundidad, primer recorrido, el resultado final se obtiene en el último nodo. Esta visualización ayuda a comprender lo que está sucediendo.

Recursion Tree

Fuente

2012-02-07 18:26:50 Bharat

Theres a python module para que

rcviz output

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

Fuente

2014-05-24 21:51:17 carlsborg

Gracias. Parece interesante. Voy a tratar de salir. – Bharat

Esta biblioteca es muy útil. Gracias. Hasta votado. – Bharat

entendimiento y la visualización de la recursividad

Respuesta

Cuestiones relacionadas