En informática , la recursión es un tipo de operación que es dual a la recursión . Mientras que la recursión funciona analíticamente , comenzando con datos más alejados de un caso base y dividiéndolos en datos más pequeños y repitiendo hasta llegar a un caso base, la recursión funciona sintéticamente, comenzando con un caso base y construyéndolo, produciendo iterativamente datos más alejados de un caso base. En pocas palabras, los algoritmos recursivos utilizan los datos que ellos mismos producen, bit a bit, a medida que están disponibles y se necesitan, para producir más bits de datos. Un concepto similar pero distinto es la recursión generativa , que puede carecer de una "dirección" definida inherente a la recursión y la recursión.
Mientras que la recursión permite a los programas operar sobre datos arbitrariamente complejos, siempre que puedan reducirse a datos simples (casos base), la correcursión permite a los programas producir estructuras de datos arbitrariamente complejas y potencialmente infinitas, como streams , siempre que puedan producirse a partir de datos simples (casos base) en una secuencia de pasos finitos . Mientras que la recursión puede no terminar, nunca alcanzando un estado base, la correcursión comienza desde un estado base y, por lo tanto, produce pasos posteriores de manera determinista, aunque puede continuar indefinidamente (y, por lo tanto, no terminar bajo una evaluación estricta), o puede consumir más de lo que produce y, por lo tanto, volverse no productiva . Muchas funciones que tradicionalmente se analizan como recursivas pueden, alternativamente, y posiblemente de manera más natural, interpretarse como funciones correcursivas que terminan en una etapa dada, por ejemplo, relaciones de recurrencia como el factorial.
La corecursion puede producir estructuras de datos finitas e infinitas como resultados, y puede emplear estructuras de datos autorreferenciales . La corecursion suele utilizarse junto con la evaluación diferida , para producir solo un subconjunto finito de una estructura potencialmente infinita (en lugar de intentar producir una estructura infinita completa a la vez). La corecursion es un concepto particularmente importante en la programación funcional , donde la corecursion y los codatos permiten que los lenguajes totales trabajen con estructuras de datos infinitas.
La corecursión se puede entender por contraste con la recursión, que es más familiar. Si bien la corecursión es de interés principalmente en la programación funcional, se puede ilustrar utilizando la programación imperativa , que se realiza a continuación utilizando la función de generador en Python . En estos ejemplos , se utilizan variables locales y se asignan valores de manera imperativa (destructivamente), aunque estos no son necesarios en la corecursión en la programación funcional pura . En la programación funcional pura, en lugar de asignar a variables locales, estos valores calculados forman una secuencia invariable y se accede a los valores anteriores por autorreferencia (los valores posteriores en la secuencia hacen referencia a valores anteriores en la secuencia que se va a calcular). Las asignaciones simplemente expresan esto en el paradigma imperativo y especifican explícitamente dónde ocurren los cálculos, lo que sirve para aclarar la exposición.
Un ejemplo clásico de recursión es el cálculo del factorial , que se define recursivamente por 0! := 1 y n! := n × (n - 1)! .
Para calcular recursivamente su resultado en una entrada dada, una función recursiva se llama a sí misma (una copia de) sí misma con una entrada diferente ("más pequeña" de alguna manera) y usa el resultado de esta llamada para construir su resultado. La llamada recursiva hace lo mismo, a menos que se haya alcanzado el caso base . Por lo tanto, se desarrolla una pila de llamadas en el proceso. Por ejemplo, para calcular fac(3) , esta llama recursivamente a su vez a fac(2) , fac(1) , fac(0) ("enrollando" la pila), en cuyo punto la recursión termina con fac(0) = 1 , y luego la pila se desenrolla en orden inverso y los resultados se calculan en el camino de regreso a lo largo de la pila de llamadas hasta el marco de llamada inicial fac(3) que usa el resultado de fac(2) = 2 para calcular el resultado final como 3 × 2 = 3 × fac(2) =: fac(3) y finalmente devuelve fac(3) = 6 . En este ejemplo, una función devuelve un solo valor.
Este desenrollado de pila se puede explicar definiendo el factorial de forma recursiva como un iterador , donde se comienza con el caso de , y luego a partir de este valor inicial se construyen valores factoriales para números crecientes 1, 2, 3... como en la definición recursiva anterior con la "flecha del tiempo" invertida, por así decirlo, leyéndola al revés como . El algoritmo correcursivo así definido produce un flujo de todos los factoriales. Esto se puede implementar concretamente como un generador . Simbólicamente, teniendo en cuenta que calcular el siguiente valor factorial requiere llevar un registro tanto de n como de f (un valor factorial anterior), esto se puede representar como:
o en Haskell ,
( \ ( n , f ) -> ( n + 1 , f * ( n + 1 ))) ` iterar ` ( 0 , 1 ) es decir, "a partir de , en cada paso se calculan los siguientes valores como ". Esto es matemáticamente equivalente y casi idéntico a la definición recursiva, pero enfatiza que los valores factoriales se construyen , avanzando desde el caso inicial, en lugar de calcularse después de ir primero hacia atrás, hasta el caso base, con un decremento. La salida directa de la función correcursiva no solo contiene los valores factoriales, sino que también incluye para cada valor los datos auxiliares de su índice n en la secuencia, de modo que se puede seleccionar cualquier resultado específico entre todos ellos, cuando sea necesario.
Existe una conexión con la semántica denotacional , donde las denotaciones de programas recursivos se construyen de forma correcursiva de esta manera.
En Python, una función factorial recursiva se puede definir como: [a]
def factorial ( n : int ) -> int : """Función factorial recursiva.""" si n == 0 : devuelve 1 de lo contrario : devuelve n * factorial ( n - 1 ) Esto podría entonces llamarse, por ejemplo, ¡ factorial(5)para calcular 5 !.
Un generador correcursivo correspondiente se puede definir como:
def factorials (): """Generador correcursivo.""" n , f = 0 , 1 while True : yield f n , f = n + 1 , f * ( n + 1 ) Esto genera un flujo infinito de factoriales en orden; una porción finita del mismo se puede producir mediante:
def n_factorials ( n : int ): k , f = 0 , 1 mientras k <= n : rendimiento f k , f = k + 1 , f * ( k + 1 )¡Esto podría entonces ser llamado para producir los factoriales hasta 5! a través de:
para f en n_factoriales ( 5 ): print ( f )Si solo nos interesa un factorial determinado, se puede tomar solo el último valor, o podemos fusionar la producción y el acceso en una sola función,
def nth_factorial ( n : int ): k , f = 0 , 1 mientras k < n : k , f = k + 1 , f * ( k + 1 ) devuelve fComo se puede ver fácilmente aquí, esto es prácticamente equivalente (simplemente sustituyendo returnel único yieldallí) a la técnica del argumento acumulador para la recursión de cola , desenrollada en un bucle explícito. Por lo tanto, se puede decir que el concepto de corecursión es una explicación de la materialización de los procesos de computación iterativos mediante definiciones recursivas, cuando corresponda.
De la misma manera, la secuencia de Fibonacci se puede representar como:
Como la secuencia de Fibonacci es una relación de recurrencia de orden 2, la relación correcursiva debe seguir dos términos sucesivos, con el correspondiente a desplazarse hacia adelante un paso y el correspondiente a calcular el término siguiente. Esto puede implementarse de la siguiente manera (usando la asignación paralela ):
def fibonacci_sequence (): a , b = 0 , 1 mientras True : rendimiento a a , b = b , a + bEn Haskell,
mapa fst ( ( \ ( a , b ) -> ( b , a + b )) ` iterar ` ( 0 , 1 ) ) El recorrido de árboles mediante un enfoque de profundidad es un ejemplo clásico de recursión. Dually, el recorrido de amplitud se puede implementar de forma muy natural mediante la recursión conjunta.
De manera iterativa, se puede recorrer un árbol colocando su nodo raíz en una estructura de datos y luego iterando con esa estructura de datos mientras no esté vacía, eliminando en cada paso el primer nodo y colocando los nodos secundarios del nodo eliminado nuevamente en esa estructura de datos. Si la estructura de datos es una pila (LIFO), esto produce un recorrido en profundidad, y si la estructura de datos es una cola (FIFO), esto produce un recorrido en amplitud:
Usando la recursión, un recorrido en profundidad de un árbol se implementa simplemente como un recorrido recursivo de cada uno de los nodos hijos del nodo raíz por turno. Por lo tanto, el segundo subárbol hijo no se procesa hasta que el primer subárbol hijo haya terminado. El valor del nodo raíz se maneja por separado, ya sea antes de que se recorra el primer hijo (resultando en un recorrido en preorden), después de que se termine el primero y antes del segundo (en orden), o después de que se termine el segundo nodo hijo (posorden), asumiendo que el árbol es binario, para simplificar la exposición. La pila de llamadas (de las invocaciones de la función de recorrido recursivo) corresponde a la pila que se iteraría con la manipulación explícita de la estructura LIFO mencionada anteriormente. Simbólicamente,
"Recursión" tiene aquí dos significados. En primer lugar, las invocaciones recursivas de las funciones de recorrido del árbol . Más pertinente aún, tenemos que lidiar con cómo se construye aquí la lista de valores resultante . La creación de salida recursiva, de abajo hacia arriba, dará como resultado el recorrido del árbol de derecha a izquierda. Para que se realice realmente en el orden de izquierda a derecha previsto, la secuenciación debería ser impuesta por algún medio externo, o se lograría automáticamente si la salida se construyera de arriba hacia abajo, es decir, de manera corecursiva .
También se puede implementar un recorrido en amplitud que genere su salida en orden descendente, de manera recursiva, comenzando en el nodo raíz, generando su valor, [b] luego recorriendo en amplitud los subárboles, es decir, pasando la lista completa de subárboles al siguiente paso (no un solo subárbol, como en el enfoque recursivo), generando en el siguiente paso los valores de todos sus nodos raíz, luego generando sus subárboles secundarios, etc. [c] En este caso, la función generadora, de hecho la secuencia de salida en sí, actúa como la cola. Como en el ejemplo factorial anterior, donde la información auxiliar del índice (en qué paso uno estaba, n ) se empujó hacia adelante, además de la salida real de n !, en este caso se empuja hacia adelante la información auxiliar de los subárboles restantes, además de la salida real. Simbólicamente,
lo que significa que en cada paso, se genera la lista de valores en los nodos de este nivel y luego se procede a los nodos del siguiente nivel. Generar solo los valores de los nodos a partir de esta secuencia simplemente requiere descartar los datos del árbol secundario auxiliar y luego aplanar la lista de listas (los valores se agrupan inicialmente por nivel (profundidad); al aplanar (desagrupar) se obtiene una lista lineal plana). Esto es extensionalmente equivalente a la especificación anterior. En Haskell,
![{\displaystyle {\text{trav}}_{\text{nn}}(t)={\text{auxiliar}}_{\text{nn}}([t])}](https://wikimedia.org/api/rest_v1/media/math/render/svg/89328dec40dd9836eed66ed5167573b1c677aae6)
![{\displaystyle {\text{auxiliares}}_{\text{df}}([t,\ ...ts])={\text{val}}(t);\ {\text{auxiliares}}_{\text{df}}([\ ...{\text{hijos}}(t),\ ...ts\ ])}](https://wikimedia.org/api/rest_v1/media/math/render/svg/222521251079e12e45ff97b9177f5a8af7c192dd)
![{\displaystyle {\text{auxiliar}}_{\text{bf}}([t,\ ... ts])={\text{val}}(t);\ {\text{auxiliar}}_{\text{bf}}([\ ... ts,\ ... {\text{hijos}}(t)\ ])}](https://wikimedia.org/api/rest_v1/media/math/render/svg/bc3fd33c7372adada4715eff280387b897279db1)
![{\displaystyle {\text{df}}_{\text{en}}(t)=[\ ...{\text{df}}_{\text{en}}({\text{izquierda}}(t)),\ {\text{val}}(t),\ ...{\text{df}}_{\text{en}}({\text{derecha}}(t))\ ]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5a3c4bc6138e56f766e02594d3f64801b59ae7f0)
![{\displaystyle {\text{df}}_{\text{pre}}(t)=[\ {\text{val}}(t),\ ...{\text{df}}_{\text{pre}}({\text{izquierda}}(t)),\ ...{\text{df}}_{\text{pre}}({\text{derecha}}(t))\ ]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3f46813d03b3658845676b19d70c6b6757edec64)
![{\displaystyle {\text{df}}_{\text{post}}(t)=[\ ...{\text{df}}_{\text{post}}({\text{izquierda}}(t)),\ ...{\text{df}}_{\text{post}}({\text{derecha}}(t)),\ {\text{val}}(t)\ ]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/423545be6f3ace13edbd1b750b77b70cca4c1288)
![{\displaystyle v,ts=([],[{\text{Árbol completo}}]):({\text{Valores raíz}}(ts),{\text{Árboles secundarios}}(ts))}](https://wikimedia.org/api/rest_v1/media/math/render/svg/abc4431a08ceceae11ed62c62bba28de708f1579)
concatMap fst ( ( \ ( v , ts ) -> ( valores_raíz ts , árboles_hijos ts )) ` iterar ` ( [] , [ árbol_completo ]) ) En particular, dado un árbol infinito, [d] el recorrido recursivo en amplitud recorrerá todos los nodos, al igual que para un árbol finito, mientras que el recorrido recursivo en profundidad descenderá por una rama y no recorrerá todos los nodos, y de hecho, si recorre el orden posterior, como en este ejemplo (o en orden), no visitará ningún nodo, porque nunca llega a una hoja. Esto muestra la utilidad de la recursión en amplitud en lugar de la recursión para tratar con estructuras de datos infinitas. Aún queda una salvedad para los árboles con el factor de ramificación infinito, que necesitan un entrelazado más atento para explorar mejor el espacio. Véase cola de milano .
En Python, esto se puede implementar de la siguiente manera. [e] El recorrido en profundidad posterior al orden habitual se puede definir como: [f]
def df ( nodo ): """Recorrido en profundidad posterior al orden.""" si el nodo no es None : df ( nodo . izquierda ) df ( nodo . derecha ) print ( nodo . valor ) Esto se puede llamar luego df(t)para imprimir los valores de los nodos del árbol en orden de profundidad posterior al orden.
El generador corecursivo de amplitud se puede definir como: [g]
def bf ( árbol ): """Generador recursivo en amplitud.""" lista_árbol = [ árbol ] mientras lista_árbol : nueva_lista_árbol = [] para árbol en lista_árbol : si árbol no es None : rendimiento árbol . valor nueva_lista_árbol . append ( árbol . izquierda ) nueva_lista_árbol . append ( árbol . derecha ) lista_árbol = nueva_lista_árbol Esto se puede llamar para imprimir los valores de los nodos del árbol en orden de amplitud:
para i en bf ( t ): imprimir ( i )Los tipos de datos iniciales pueden definirse como el punto fijo más pequeño ( hasta el isomorfismo ) de alguna ecuación de tipo; el isomorfismo viene dado por una álgebra inicial . Dualmente, los tipos de datos finales (o terminales) pueden definirse como el punto fijo más grande de una ecuación de tipo; el isomorfismo viene dado por una coalgebra final .
Si el dominio del discurso es la categoría de conjuntos y funciones totales , entonces los tipos de datos finales pueden contener valores infinitos no bien fundados , mientras que los tipos iniciales no. [1] [2] Por otro lado, si el dominio del discurso es la categoría de órdenes parciales completos y funciones continuas , que corresponde aproximadamente al lenguaje de programación Haskell , entonces los tipos finales coinciden con los tipos iniciales, y la coálgebra final y el álgebra inicial correspondientes forman un isomorfismo. [3]
La corecursion es entonces una técnica para definir recursivamente funciones cuyo rango (codominio) es un tipo de datos final, de manera similar a la forma en que la recursión ordinaria define recursivamente funciones cuyo dominio es un tipo de datos inicial. [4]
La siguiente discusión proporciona varios ejemplos en Haskell que distinguen la correcursión. En términos generales, si uno trasladara estas definiciones a la categoría de conjuntos, seguirían siendo correcursivas. Este uso informal es coherente con los libros de texto existentes sobre Haskell. [5] Los ejemplos utilizados en este artículo son anteriores a los intentos de definir la correcursión y explicar qué es.
La regla para la recursión primitiva sobre codatos es la doble de la de la recursión primitiva sobre datos. En lugar de descender sobre el argumento mediante la coincidencia de patrones en sus constructores (que se llamaron antes de , en algún lugar, por lo que recibimos un dato listo para usar y obtenemos sus subpartes constituyentes, es decir, "campos"), ascendemos sobre el resultado completando sus "destructores" (u "observadores", que se llamarán después de , en algún lugar, por lo que en realidad estamos llamando a un constructor, creando otro bit del resultado que se observará más adelante). Por lo tanto, la recursión crea codatos (potencialmente infinitos), mientras que la recursión ordinaria analiza datos (necesariamente finitos). La recursión ordinaria podría no ser aplicable a los codatos porque podría no terminar. Por el contrario, la recursión no es estrictamente necesaria si el tipo de resultado son datos, porque los datos deben ser finitos.
En "Programación con streams en Coq: un estudio de caso: la Criba de Eratóstenes" [6] encontramos
hd ( conc a s ) = a tl ( conc a s ) = s ( tamiz p s ) = si div p ( hd s ) entonces tamiz p ( tl s ) de lo contrario conc ( hd s ) ( tamiz p ( tl s )) hd ( primos s ) = ( hd s ) tl ( primos s ) = primos ( tamiz ( hd s ) ( tl s )) donde los números primos "se obtienen aplicando la operación de números primos al flujo (Enu 2)". Siguiendo la notación anterior, la secuencia de números primos (con un 0 descartable como prefijo) y flujos de números que se tamizan progresivamente, se pueden representar como
o en Haskell,
![{\displaystyle p,s=(0,[2..]):(hd(s),tamiz(hd(s),tl(s)))}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ab229486da06530a791f3e0e1161368565a38fc0)
( \ ( p , s @ ( h : t )) -> ( h , tamiz h t )) ` iterar ` ( 0 , [ 2 .. ]) Los autores analizan cómo no se garantiza que la definición de sievesea siempre productiva y podría quedarse estancada, por ejemplo, si se la llama con [5,10..]como flujo inicial.
He aquí otro ejemplo en Haskell. La siguiente definición produce la lista de números de Fibonacci en tiempo lineal:
fibs = 0 : 1 : zipWith ( + ) fibs ( cola fibs ) Esta lista infinita depende de una evaluación diferida; los elementos se calculan según sea necesario y solo los prefijos finitos se representan explícitamente en la memoria. Esta característica permite que los algoritmos en partes de los codatos terminen; estas técnicas son una parte importante de la programación Haskell.
Esto también se puede hacer en Python: [7]
>>> de itertools import tee , chain , islice >>> def fibonacci (): ... def deferred_output (): ... rendimiento de salida ... ... resultado , c1 , c2 = tee ( deferred_output (), 3 ) ... paired = ( x + y para x , y en zip ( c1 , islice ( c2 , 1 , None ))) ... salida = chain ([ 0 , 1 ], paired ) ... devolver resultado >>> print ( * islice ( fibonacci ()), 20 ), sep = ', ' ) 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181La definición de zipWithse puede incluir en línea, lo que da como resultado lo siguiente:
fibs = 0 : 1 : siguiente fibs donde siguiente ( a : t @ ( b : _ )) = ( a + b ) : siguiente t Este ejemplo emplea una estructura de datos autorreferencial . La recursión ordinaria hace uso de funciones autorreferenciales , pero no admite datos autorreferenciales. Sin embargo, esto no es esencial para el ejemplo de Fibonacci. Se puede reescribir de la siguiente manera:
fibs = fibgen ( 0 , 1 ) fibgen ( x , y ) = x : fibgen ( y , x + y ) Esto emplea únicamente una función autorreferencial para construir el resultado. Si se utilizara con un constructor de lista estricto, sería un ejemplo de recursión descontrolada, pero con un constructor de lista no estricto , esta recursión protegida produce gradualmente una lista definida indefinidamente.
La correcursión no tiene por qué producir un objeto infinito; una cola correcursiva [8] es un ejemplo particularmente bueno de este fenómeno. La siguiente definición produce un recorrido en amplitud de un árbol binario de arriba hacia abajo , en tiempo lineal (ya incorporando el aplanamiento mencionado anteriormente):
datos Árbol a b = Hoja a | Rama b ( Árbol a b ) ( Árbol a b ) bftrav :: Árbol a b -> [ Árbol a b ] bftrav árbol = árbol : ts donde ts = gen 1 ( árbol : ts ) gen 0 p = [] gen len ( Hoja _ : p ) = gen ( len - 1 ) p gen len ( Rama _ l r : p ) = l : r : gen ( len + 1 ) p -- ----lectura---- ----escritura anticipada--- -- árbol bfvalues = [v | (Rama v _ _) <- árbol bftrav]Esta definición toma un árbol y produce una lista de sus subárboles (nodos y hojas). Esta lista tiene un doble propósito, ya que es la cola de entrada y el resultado ( gen len pproduce su salida lenen muescas por delante de su puntero de entrada, p, a lo largo de la lista). Es finita si y solo si el árbol inicial es finito. La longitud de la cola debe rastrearse explícitamente para garantizar la terminación; esto se puede omitir con seguridad si esta definición se aplica solo a árboles infinitos.
Este código Haskell utiliza una estructura de datos autorreferencial, pero no depende esencialmente de una evaluación perezosa. Se puede traducir directamente a, por ejemplo, Prolog, que no es un lenguaje perezoso. Lo esencial es la capacidad de construir una lista (usada como cola) de manera descendente . Para ello, Prolog tiene recursión de cola módulo cons (es decir, listas abiertas), que también se pueden emular en Scheme, C, etc., utilizando listas enlazadas con un puntero centinela de cola mutable:
bftrav ( Árbol , [ Árbol | TS ]) :- bfgen ( 1 , [ Árbol | TS ], TS ).bfgen ( 0 , _ , []) :- !. % 0 entradas en la cola -- detiene y cierra la lista bfgen ( N , [ leaf ( _ ) | P ], TS ) :- N2 es N - 1 , bfgen ( N2 , P , TS ). bfgen ( N , [ branch ( _ , L , R )| P ], [ L , R | TS ]) :- N2 es N + 1 , bfgen ( N2 , P , TS ). %% ----read----- --write-ahead--Otro ejemplo particular ofrece una solución al problema del etiquetado en amplitud. [9] La función labelvisita cada nodo de un árbol binario en el modo de amplitud, reemplazando cada etiqueta con un entero, siendo cada entero subsiguiente mayor que el último en 1. Esta solución emplea una estructura de datos autorreferencial, y el árbol binario puede ser finito o infinito.
etiqueta :: Árbol a b -> Árbol Int Int etiqueta t = tn donde ( tn , ns ) = ir t ( 1 : ns ) go :: Árbol a b -> [ Int ] -> ( Árbol Int Int , [ Int ]) go ( Hoja _ ) ( i : a ) = ( Hoja i , i + 1 : a ) go ( Rama _ l r ) ( i : a ) = ( Rama i ln rn , i + 1 : c ) donde ( ln , b ) = go l a ( rn , c ) = go r b O en Prolog, para comparar,
etiqueta ( Árbol , Tn ) :- etiqueta ( Árbol , [ 1 | Ns ], Tn , Ns ).etiqueta ( hoja ( _ ), [ I | A ], hoja ( I ), [ I + 1 | A ]). etiqueta ( rama ( _ , L , R ),[ I | A ], rama ( I , Ln , Rn ),[ I + 1 | C ]) :- etiqueta ( L , A , Ln , B ), etiqueta ( R , B , Rn , C ).Un apomorfismo (como un anamorfismo , como unfold ) es una forma de correcursión de la misma manera que un paramorfismo (como un catamorfismo , como fold ) es una forma de recursión.
El asistente de prueba Coq admite la correcursión y la coinducción mediante el comando CoFixpoint.
La corecursion, conocida como programación circular, data al menos de (Bird 1984), quien atribuye su origen a John Hughes y Philip Wadler ; se desarrollaron formas más generales en (Allison 1989). Las motivaciones originales incluían la producción de algoritmos más eficientes (que permitieran una sola pasada sobre los datos en algunos casos, en lugar de requerir múltiples pasadas) y la implementación de estructuras de datos clásicas, como listas doblemente enlazadas y colas, en lenguajes funcionales.
clase Árbol : def __init __ ( self , valor , izquierda = Ninguno , derecha = Ninguno ) : self.valor = valor self.izquierda = izquierda self.derecha = derecha def __str__ ( self ): devuelve str ( self . valor )e inicializar un árbol, digamos mediante:
t = Árbol ( 1 , Árbol ( 2 , Árbol ( 4 ), Árbol ( 5 )), Árbol ( 3 , Árbol ( 6 ), Árbol ( 7 )))En este ejemplo, los nodos se etiquetan en orden de amplitud:
1 2 34 5 6 7