# data[].attributes.attachment_link.title
12 - Torres de Hanoi mediante Recursividad (EDDJava)

# data[].attributes.attachment_link.title
11 - Sucesión Fibonacci mediante Recursividad (EDDJava)

# data[].attributes.attachment_link.title
10 - Factorial de un Número Mediante Recursividad (EDDJava)

# data[].attributes.body
Procesos recursivos e iterativos

Hemos visto que la recursión es una herramienta muy elegant y con un alto nivel de abstracción. Pero hay que tener cuidado al utilizarla, porque a veces una solución recursiva pura es muy elegante pero tiene un coste demasiado elevado.

Veremos en este apartado que en estos casos es posible modificar la recursión y construir una solución que crea un proceso iterativo utilizando lo que se denomina recursión por la cola.

El coste espacial de la recursión

Vamos examinar en primer lugar el coste espacial de la recursión. ¿Cuál es el coste espacial de una llamada recursiva? ¿Qué información debo guardar para realizar la recursión? La respuesta es que el coste viene dado por el número de llamadas a funciones que quedan a la espera de que termine la recursión. Veamos algunos ejemplos.

longitud

Comenzamos repasando la función longitud que hemos visto anteriormente. Supongamos la siguiente invocación de esta función:

(longitud '(a b c d)) -> 4

La traza de llamadas recursivas que se han generado con la llamada anterior es la siguiente:

(longitud '(a b c d))
(+ 1 (longitud '(b c d)))
(+ 1 (+ 1 (longitud '(c d))))
(+ 1 (+ 1 (+ 1 (longitud '(d)))))
(+ 1 (+ 1 (+ 1 (+ 1 (longitud '())))))
(+ 1 (+ 1 (+ 1 (+ 1 0))))
(+ 1 (+ 1 (+ 1 1)))
(+ 1 (+ 1 2))
(+ 1 3)
4

Cada llamada a la recursión deja en espera una llamada a la función + con los parámetros 1 y el propio resultado de la recursión. Como en cualquier llamada a una función, este estado local se almacena en una /pila de llamada/ de la que será recuperado cuando la llamada termine. En el caso de la recursión la pila va creciendo hasta que la recursión termina. Si por un error la recursión no termina y se entra en un bucle infinito en algún momento se produce un stack overflow, un desbordamiento de la memoria reservada por el sistema operativo para el programa que está en funcionamiento.

Estas llamadas en espera son las que determinan el coste espacial de la recursión. En este caso el coste espacial depende linealmente de la longitud de la palabra. Se trata de un coste O(n), siendo n la longitud de la palabra.

fibonacci

El coste espacial y el temporal depende del número de llamadas a la recursión. En el caso en que se realicen dos llamadas a la recursión tendríamos un coste exponencial.

Veámoslo con una recursión que implementan de forma elegante, pero poco eficiente, la serie de Fibonacci.

Recordemos que la secuencia de números de Fibonacci se define con la siguiente expresión:

fib (n) = fib (n-1) + fib (n-2)
fib (1) = fib (0) = 1

De esta forma, la secuencia de números de Fibonacci es: 1, 1, 2, 3, 5, 8, 13, 21, …

La función recursiva que resulta de aplicar directamente esta ecuación es la siguiente:

(define (fib n)
(cond ((= n 0) 0)
        ((= n 1) 1)
        (else (+ (fib (- n 1))
                 (fib (- n 2))))))

La diferencia con las funciones recursivas vistas hasta ahora es que en el cuerpo de la función se realizan dos llamadas recursivas. Esto genera un proceso recursivo en forma de árbol, como se comprueba en la siguiente figura, extraída del Abelson & Sussman:

Cada llamada a la recursión produce otras dos llamadas, con lo que el número de llamadas finales es 2n, siendo n el número que se pasa a la función. El coste espacial y temporal es por tanto de O(2n). Podemos comprobar con el intérprete que es imposible evaluar la función para números a partir de 30.

¿Es posible diseñar la función recursiva de otra forma, para evitar este coste? Vamos a verlo.

Procesos recursivos e iterativos

En la asignatura hecho la distinción entre programas y los procesos que éstos generan. Esta distinción se hace muy importante en el caso de los programas recursivos.

Hemos visto en el apartado anterior que el proceso generado por una función recursiva tiene a veces un alto coste espacial y temporal debido a las llamadas que permenacen en espera en la pila de la recursión.

Es posible escribir programas recursivos que generen procesos que no dejan llamadas en espera. A estos procesos los llamamos procesos iterativos, en contraposición con los procesos recursivos que generan los programas vistos hasta ahora.

La siguiente versión de la función factorial está escrita de forma que el proceso generado es iterativo y no deja llamadas en espera.

(define (factorial-iter n)
   (fact-iter-aux n n))

(define (fact-iter-aux product n)
    (if (= n 1)
        product
        (fact-iter-aux (* product (- n 1))  (- n 1))))

La función (fact-iter-aux product n) es la que implementa la nueva versión de factorial. El parámetro adicional product que se ha añadido guarda en cada llamada el cálculo parcial del factorial. Cuando la recursión llega a su fin ya se tiene el resultado calculado y se devuelve directamente, sin necesidad de evaluar ninguna función en espera.

Lo podemos comprobar en la secuencia de llamadas que se produce para evaluar (factorial-iter 4):

(factorial-iter 4)
(factorial-iter-aux 4 4)
(factorial-iter-aux 12 3)
(factorial-iter-aux 24 2)
(factorial-iter-aux 24 1)
24

Veamos otro ejemplo más, la versión iterativa de la función longitud que calcula la longitud de una lista.

(define (longitud-iter lista)
   (longitud-iter-aux lista 0))

(define (longitud-iter-aux lista result)
   (if (null? lista)
      result
      (longitud-iter-aux (cdr lista) (+ result 1))))

La función longitud-iter ahora recibe un argumento adicional, denominado result. Igual que en la función fact-aux anterior en él se almacena el valor parcial del cálculo de la recursión. En este caso de la longitud de la palabra.

En cada llamada recursiva se incrementa en 1 el resultado parcial y se elimina un elemento de la lista. De esta forma, cuando la lista esté vacía, el resultado habrá acumulado su longitud (siempre que inicialmente se haya pasado 0 como valor).

La función longitud se redefine para que llame a longitud-iter con los valores iniciales correctos.

Como podemos comprobar, tampoco se deja ninguna llamada en espera en la pila de llamada. Cuando alcanzamos el caso base de la recursión tenemos la respuesta al problema completo.

(longitud 'abcdef)
(longitud-iter 'abcdef 0)
(longitud-iter 'bcdef 1)
(longitud-iter 'cdef 2)
(longitud-iter 'def 3)
(longitud-iter 'ef 4)
(longitud-iter 'f 5)
(longitud-iter "" 6)
6

Procesos iterativos

Las dos funciones anteriores son ejemplos de funciones que generan procesos iterativos.

En general, las versiones iterativas son menos elegantes y más difíciles de entender que las recursivas, pero son más eficientes.

En otros lenguajes de programación existen bucles (for, while) para definir procesos iterativos. En un lenguaje funcional puro no existen bucles; el proceso iterativo se implementa como hemos visto. Se utiliza uno o más parámetros auxiliares y se modifica su valor en cada llamada a la recursión.

Esta recursión que no deja llamadas en espera también recibe el nombre de tail recursión o recursión por la cola. El código del intérprete que evalua la recursión por la cola puede tratar estas llamadas de una forma especial, sabiendo que no hay que devolver el resultado para que vuelva a ser procesado. Se devuelve el último valor a la llamada original y se puede eliminar la pila de la llamada.

Fibonacci iterativo

La versión recursiva de la función que devuelve el número de Fibonacci tenía un coste exponencial, debido a las dos llamadas recursivas.

(define (fib n)
  (cond ((= n 0) 0)
        ((= n 1) 1)
        (else (+ (fib (- n 1))
                 (fib (- n 2))))))

Se puede implementar una versión eficiente de la misma función utilizando el mecanismo de recursión por la cola.

(define (fib-iter a b count)
  (if (= count 0)
      b
      (fib-iter (+ a b) a (- count 1))))

(define (fib n)
  (fib-iter 1 0 n))

La función (fib-iter a b count) define un proceso iterativo que va calculando cada número sucesivo de fibonacci utilizando los parámetros a y b. El parámetro count cuenta el número de iteraciones.

Esta recursión tiene un coste lineal O(n) y permite calcular sin problemas valores de fibonacci imposibles de obtener con la recursión anterior.

Memoization

La memoization es una técnica de optimización que permite mantener la elegancia de los procesos recursivos sin incurrir en el coste de las llamadas repetidas a la recursión.

Si miramos la traza de (fibonaci 4) podemos ver que se está llamando de forma repetida a la recursión con los mismos valores.

Por ejemplo, para calcular (fib 200) hay que llamar a (fib 199) y (fib 198). A su vez, para calcular (fib 199) se llama a (fib 198) y (fib 197). ¿Por qué llamar dos veces a (fib 198)? Estamos en programación funcional y el resultado de la llamada siempre va a ser el mismo. ¿No podríamos guardar el valor devuelto por (fib 198) la primera vez y utilizarlo la segunda vez? De esta forma no volveríamos a lanzar la recursión para este valor (ni para ningún otro).

Esto es lo que hace la memoization, en una llamada recursiva guarda el valor devuelto por cada una de las llamadas en alguna estructura de datos adecuada (una tabla hash por ejemplo) y lo reutiliza en el resto de llamadas.

La forma de implementar la memoization en Scheme utiliza continuaciones y la forma especial no funcional set!, características del lenguaje que todavía no hemos estudiado. Una explicación muy buena de cómo hacerlo se puede encontrar en Community Scheme Wiki.

Triángulo de pascal

El último ejemplo de función recursiva que vamos a transformar en iterativa es el triángulo de Pascal.

Cada elemento del triángulo de Pascal es la suma de los dos números que hay sobre él:

              1
            1   1
          1   2   1
        1   3   3   1
      1   4   6   4   1
    1   5  10  10  5   1
  1   6  15  20  15  6   1
1   7  21  35  35  21  7   1
             ...

La función Pascal(fila, columna) se define matemáticamente de la siguiente forma:

Pascal(fila, 0) = 1 para cualquier valor de fila
Pascal(fila, columna) = 1 si fila = columna
Pascal(fila, columna) = Pascal(fila-1,columna-1) + Pascal(fila-1, columna) en otro caso

La función Scheme que calcula de forma recursiva el número de Pascal que se encuentra en una determinada fila y columna es la siguiente:

(define (pascal row col)
  (cond ((= col 0) 1)
        ((= col row) 1)
        (else (+ (pascal (- row 1) (- col 1))
                 (pascal (- row 1) col) ))))

Al igual que con la función fibonacci esta solución es muy poco eficiente. Para calcular un valor de la recursión se hacen dos llamadas recursivas, lo que genera un proceso en forma de árbol con un coste exponencial.

Una forma de solucionar el problema con una versión iterativa consiste en generar cada una de las filas del triángulo a partir de la anterior. La fila se puede representar con una lista.

La función (pascal-sig-fila fila) se encarga de construir la fila siguiente del triángulo de Pascal a partir de la anterior. Por ejemplo:

(pascal-sig-fila '(1 3 3 1)) -> (1 4 6 4 1)

Su implementación se basa en la función (pascal-sig-fila-central fila) que calcula de forma recursiva los elementos interiores de la fila. Esta función no es iterativa.

(define (pascal-sig-fila fila)
    (append '(1)
                (pascal-sig-fila-central fila)
                '(1)))

(define (pascal-sig-fila-central fila)
   (if (= 1 (length fila))
      '()
       (append (list (+ (car fila) (car (cdr fila))))
                   (pascal-sig-fila-central (cdr fila)))))

La función (pascal-iter-aux fila n) es la que realiza las n iteraciones utilizando fila como parámetro auxiliar en el que se van construyendo las sucesivas filas. Termina cuando la longitud de la fila calculada coincide con n.

Por último, la función (pascal-iter fila col) llama a la anterior para producir la fila número fila, y devuelve el elemento número col:

(define (pascal-iter fila col)
   (if (= 0 col)
      1
      (list-ref (pascal-iter-aux '(1 1) fila) col)))

(define (pascal-iter-aux fila n)
    (if (= n (- (length fila) 1))
        fila
        (pascal-iter-aux (pascal-sig-fila fila) n)))

La función pascal-sig-fila se encarga de construir la fila siguiente del triángulo de Pascal a partir de la anterior. Por ejemplo:

La función pascal-iter va llamando de forma iterativa a pascal-sig-fila hasta que llegamos a la fila n que deseamos. La función pascal recoge esa fila y devuelve el elemento col deseado.

Puedes probar los siguientes valores para comprobar la diferencia de rendimiento entre las dos versiones:

(pascal 28 10) -> 13123110
(pascal-iter 28 10) -> 13123110

Estructuras de datos recursivas

En este apartado vamos a estudiar el diseño y la implementación en Scheme de tres estructuras de datos que tienen definiciones recursivas:

Expresiones-s

Árboles binarios

Árboles genéricos

Expresiones-s

Las expresiones-s (expresión simbólica) son la base del diseño del lenguaje de programación LISP. Fueron introducidas en 1958 por John McCarthy, en el artículo Recursive Functions of Symbolic Expressions and Their Computation by Machine, Part I, en el que define el lenguaje de programación LISP.

Definición

En su formulación original de McCarty, una expresión-s es una expresión matemática que se define con la siguiente formulación recursiva:

Un dato atómico es una expresión-s

Si e₁ y e₂ son expresiones-s, la expresión (e₁ . e₂) también es una expresión-s

Por ejemplo, las siguientes expresiones son expresiones-s de McCarthy:

(A . B)
(A . (B . C))
((A . B) . (C . D))
(A. ((A . B) . (C . D)))

Y las siguientes expresiones no son expresiones-S de McCarthy:

(A . B . C)
(A)
(() . B)

En la misma formulación, McCarthy define una lista como un tipo especial de expresión-s que termina con el átomo NIL:

(m₁, m₂, …, mn) -> (m₁ . (m₂ . ( … (mn . NIL) … )))

Esta formulación matemática fue el origen del concepto de pareja de LISP utilizando las funciones cons, car y cdr (también definidas en el mismo artículo).

En la actualidad, el concepto de expresión-s se ha extendido, eliminando la notación del punto y refiriéndose a expresiones con símbolos (identificadores) entre un número balanceado de paréntesis.

Los siguientes son ejemplos de expresiones-s extendidas:

(= 4 (+ 2 2))
(if (= x y) (* x y) (+ (/ x y) 45))
(define (factorial x) (if (= x 0) 1 (* x (factorial (- x 1)))))

Esta es la interpretación que vamos a utilizar a partir de ahora cuando hablemos de expresión-s en general.

En Scheme las expresiones-s se implementan con listas. Cuando el intérprete, en su bucle read-eval-print recibe una expresión-s, la convierte en una lista e intenta evaluarla.

Cualquier expresión de Scheme correcta es una expresión-s, pero al revés no. Por ejemplo, las siguientes expresionesn-s son expresiones correctas de Scheme:

(define (factorial x) (if (= x 0) 1 (* x (factorial (- x 1)))))
(define lista (quote (1 (2 (3)))))

Y la siguiente expresión-s no lo es:

(1 (2 (3)))

La consideración de una expresión-s como una lista nos lleva a su última definición recursiva:

Una expresión-s es una lista cuyos elementos pueden ser datos atómicos o expresiones-s

Una expresión-s vacía es una lista vacía

Con esta definición, considerando las expresiones-s como listas, vemos que se pueden aplicar las funciones car y cdr para recorrerlas:

La función car devolverá un dato atómico u otra expresión-s

La función cdr devolverá la expresión-s resultante de eliminar el primer elemento de la lista. Nunca devolverá un dato atómico.

Estructura jerárquica

Las expresiones-s representan una estructura de niveles, en la que la lista inicial define el nivel 1, y las siguientes expresiones anidadas van aumentando de nivel.

Los datos atómicos constituyen las hojas de la estructura.

Otro ejemplo (ejercicio en clase):

(let ((x 12)
      (y 5))
   (+ x y)))

Las funciones que podemos utilizar para recorrer una expresion-s son:

list y quote: construcción

cons: añadir elemento a la cabeza

car: devuelve el primer dato (puede ser una hoja o una expresión-S)

cdr: devuelve el resto (siempre una expresión-S)

null?: comprueba si es lista vacía

Para remarcar el carácter jerárquico de las expresiones-s definimos la función hoja? que comprueba si el elemento es una hoja o una expresión-s (lista)

(define (hoja? x)
   (not (pair? x)))

Funciones sobre expresiones-s como estructuras jerárquicas

(cuenta-hojas-exp exp): cuenta las hojas

(niveles-exp exp): cuenta los niveles

(pertenece-exp x exp): busca una hoja

(cuadrado-exp exp): eleva todas las hojas al cuadrado

(map-exp f exp): similar a map

La función (cuenta-hojas-exp exp) cuenta las hojas que hay en una expresión-s

(define (cuenta-hojas-exp exp)
    (cond
      ((null? lista) 0)
      ((hoja? (car exp)) (+ 1 (cuenta-hojas-exp (cdr exp))))
      (else
           (+ (cuenta-hojas-exp (car exp))
              (cuenta-hojas-exp (cdr exp))))))

La función (niveles-exp exp) devuelve el número de niveles de una expresión-s.

(define (niveles-exp exp)
   (cond
      ((null? exp) 0)
      ((hoja? exp) 0)
      (else (max (+ 1 (niveles-exp (car exp)))
                 (niveles-exp (cdr exp))))))

La función (pertenece-exp? x exp) comprueba si el átomo x aparece en la expresión-s

(define (pertenece-exp? x exp)
         (cond
             ((null? exp) #f)
             ((hoja? exp) (equal? x exp))
             (else (or (pertenece-exp? x (car exp))
                       (pertenece-exp? x (cdr exp))))))

La función (cuadrado-exp exp) devuelve una expresión-s formada por números con la expresión-s con la misma estructura y los números elevados al cuadrado.

(define (cuadrado-exp exp)
  (cond ((null? exp) '())
        ((hoja? exp) (cuadrado exp))
        (else (cons (cuadrado-exp (car exp))
                    (cuadrado-exp (cdr exp)) )) ))

Por último (map-exp f exp) devuelve una expresión-s formada con la misma estructura que la original con el resultado de aplicar a cada uno de sus átomos la función f

(define (map-exp f exp)
  (cond ((null? exp) '())
        ((hoja? exp) (f exp))
        (else (cons (map-exp f (car exp))
                    (map-exp f (cdr exp)) )) ))

Árboles binarios

Un árbol binario es una estructura que contiene tres elementos: un dato, un árbol binario izquierdo y un árbol binario derecho.

Esta definición es recursiva y necesita un caso base. Es el siguiente: un árbol binario puede ser también un árbol-vacio, un símbolo especial vacio-bt que simboliza un árbol que no tiene datos ni hijos.

En la asignatura no nos preocupa cuáles son los datos del árbol, ni su ordenación; sólo su estructura. Veremos un conjunto de funciones que definen la barrera de abstracción para trabajar con árboles binarios y después las utilizaremos para construir funciones de mayor nivel.

Barrera de abstracción

Ya hemos comentado que una de las características de los lenguajes de programación es que permiten construir abstracciones.

Llamamos barrera de abstracción al conjunto de funciones que permiten trabajar con una abstracción y aislan su implementación. Estas funciones definen la especificación de la abstracción: qué nos permite hacer la abstracción.

En el caso de las estructuras de datos, las funciones de la barrera de abstracción permiten crear nuevas estructuras y trabajar con ellas.

Cuando estamos trabajando con una estructura de datos o con cualquier otra abstracción no debemos saltar la barrera de abstracción. Las funciones superiores siempre deben usar las funciones proporcionadas por la barrera de abstracción. De esta forma no les afectan posibles cambios en la implementación de la barrera.

En informática se utilizan barreras de abstracción continuamente. Otros nombres alternativos que recibe este concepto son: capa de una aplicación, interfaz, API (Application Programming Interface).

Por ejemplo, las distintas capas de un sistema operativo, un driver de un dispositivo, un API accesible por web de una aplicación como Twitter o Google Maps o todo un nuevo lenguaje para hacer un (como OpenGL para crear gráficos 3D).

Muchos lenguajes de programación tienen elementos más elaborados para definir abstracciones (clases, métodos, paquetes, modificadores de visibilidad, etc.). En el caso de Scheme, la única forma de definir una barrera de abstracción es definiendo una lista de funciones.

Barrera de abstracción de árbol binario

Representamos la barrera de abstracción dibujando dos capas separadas por una lista de funciones. La capa inferior representa el código que implementa la barrera de abstracción. La capa superior representa el código que usa la barrera de abstracción.

En el caso de los árboles binarios, definimos la siguiente barrera:

Las funciones de la barrera son las siguientes:

(make-bt dato izq-bt der-bt): crea un árbol binario con un dato, un árbol binario izquierdo y un árbol binario derecho

vacio-bt: constante que define el árbol binario vacío

(dato-bt bt): devuelve el dato de un árbol binario

(izq-bt bt): devuelve el árbol binario izquierdo

(der-bt bt): devuelve el árbol binario derecho

(hoja-bt? bt): comprueba si el árbol es una hoja (no tiene hijos)

(vacio-bt? bt): comprueba si el árbol es vacío

Usamos el convenio de que todas las funciones de la barrera terminan con el mismo sufijo. En esta caso -bt de binary tree. También usamos el convenio de llamar make- a la función que construye la estructura de datos.

Una vez que hemos definido las funciones (y suponiendo que alguien las haya implementado) podemos usarlas para trabajar con la abstracción. Por ejemplo vamos a construir un árbol binario y a obtener algunos de sus elementos.

    *
   / \
  +   8
 / \
5   3

(define t1 (make-bt 5 vacio-bt vacio-bt))
(define t2 (make-bt 3 vacio-bt vacio-bt))
(define t3 (make-bt '+ t1 t2))
(define t4 (make-bt 8 vacio-bt vacio-bt))
(define t5 (make-bt '* t3 t4))
(dato-bt t5) -> *
(dato-bt (izq-bt t5)) -> +
(dato-bt (izq-bt (izq-bt t5))) -> 5

Implementación de los árboles binarios

Necesitamos una estructura con la que podamos guardar 3 elementos: el dato de la raiz, el sub-árbol izquierdo y el sub-árbol derecho.

La forma natural en Scheme es utilizar una lista que contiene a esos tres elementos. Y el árbol binario vacio se puede representar entonces como una lista vacía.

Vemos que con esta definición un árbol binario se puede expresar como una expresión-s. En el caso del ejemplo visto en la figura la expresión-s que define el árbol binario es:

(10 (5 (3 () ()) ()) (23 (12 () ()) (28 () ())))

La implementación de la barrera de abstracción en Scheme es la siguiente:

(define (make-bt dato izq der)
    (list dato izq der))
(define vacio-bt '())

(define (vacio-bt? btree) (null? btree))
(define (dato-bt btree) (car btree))
(define (izq-bt btree) (car (cdr btree)))
(define (der-bt btree) (car (cdr (cdr btree))))

(define (hoja-bt? btree)
   (and (vacio-bt? (izq-bt btree))
        (vacio-bt? (der-bt btree))))

Funciones de mayor nivel

Terminamos construyendo algunas operaciones sobre árboles binarios, definidas sobre la barrera de abstracción anterior.

(to-list-bt bt): devuelve una lista formada por los elementos del bt

(member-bt? x bt): busca el elemento x en un árbol binario ordenado

(insert-bt x bt): "inserta" (realmente, no modifica el árbol que se pasa como parámetro, sino que crea otro) un dato en un árbol binario ordenado

(insert-list-bt lista bt): "inserta" una lista en un árbol binario ordenado

(list-to-bt list): construye un árbol binario ordenado a partir de una lista

to-list-bt

La función (bt-to-list bt) construye una lista con los elementos contenidos en el árbol binario bt.

(define (to-list-bt btree)
   (if (vacio-bt? btree)
      '()
      (append (to-list-bt (izq-bt btree))
              (list (dato-bt btree))
              (to-list-bt (der-bt btree)))))

La recursión de esta función se basa en obtener el dato de la raíz, obtener de forma recursiva la lista de elementos de la rama izquierda y la lista de elementos de la rama derecha. La función append concatena todos los elementos. Dependiendo del orden en que los concatenemos aparecerán los elementos en pre-order, in-order o post-order.

(member-bt? x bt)

La función (member-bt? x bt) comprueba si un número x pertenece a un árbol binario ordenado bt. En el árbol binario ordenado todos los datos del hijo izquierdo son menores que el dato de la raíz y los del hijo derecho son mayores.

La búsqueda se implementa con la típica búsqueda dicotómica:

Si el dato de la raíz del árbol es menor que x, hacemos una llamada recursiva para comprobar si el dato está el subárbol derecho

Si el dato es mayor que x, buscamos x en el subárbol izquierdo

Si el dato de la raiz es igual que x devolvemos #t.

El coste de la búsqueda es log(n).

(define (member-bt? x bt)
   (cond
      ((vacio-bt? bt) #f)
      ((= x (dato-bt bt)) #t)
      ((< x (dato-bt bt))
         (member-bt? x (izq-bt bt)))
      (else
         (member-bt? x (der-bt bt)))))

(insert-bt x bt)

La función insert-bt devuelve un nuevo árbol binario nuevo a partir de bt en el que se ha colocado el dato x en su posición correcta.

La función se basa en identificar en qué subárbol va el dato que estamos insertando. Si el dato es mayor que la raíz hay que ponerlo en el hijo derecho, por lo quec onstruimos un nuevo árbol con la misma raíz e hijo izquierdo que el actual y como hijo derecho ponemos el resultado de la llamada recursiva de insertar un dato en el árbol derecho (¡confía en la recursión!). Si el dato es menor hacemos lo contrario.

(define (insert-bt x bt)
   (cond
      ((vacio-bt? bt) (make-bt x vacio-bt vacio-bt))
      ((< x (dato-bt bt))
         (make-bt (dato-bt bt)
                    (insert-bt x (izq-bt bt))
                    (der-bt bt)))
      ((> x (dato-bt bt))
         (make-bt (dato-bt bt)
                    (izq-bt bt)
                    (insert-bt x (der-bt bt))))
      (else bt)))

(insert-list-bt lista bt)

La función insert-list-bt se basa en la función anterior para insertar todos los elementos de una lista en un árbol binario. Al igual que en el caso anterior, hay que hacer notar que no existe tal inserción, sino que se construye un árbol nuevo que se devuelve como resultado.

(define (insert-list-bt lista bt)
   (if (null? lista)
      bt
      (insert-list-bt (cdr lista)
          (insert-bt (car lista) bt))))

(list-to-bt lista)

Por último, la función list-to-bt construye una árbol binario ordenado a partir de una lista de números utilizando la función anterior.

(define (list-to-bt lista)
   (insert-list-bt lista vacio-bt))

Árboles genéricos

A diferencia de los árboles binarios, los árboles genéricos pueden tener un número de hijos variables. Se usan en un gran número de dominios en los que es necesario representar estructuras jerárquicas: procesadores de lenguaje, documentos XML, documentos HTML, etc.

La definición recursiva del tipo de datos árbol:

Un árbol genérico está formado por un dato y una lista de árboles hijos (también árboles)

La lista de árboles hijos puede ser vacía. De esta forma, a diferencia de los árboles binarios, en los árboles genéricos no usamos el concepto de árbol-vacio. Un árbol o nodo hoja es un árbol cuya lista de hijos es una lista vacía.

La siguiente figura representa un árbol genérico.

Y su representación utilizando la definición anterior:

Barrera de abstracción e implementación de árboles genéricos

La barrera de abstracción de los árboles genéricos se construye únicamente con las siguientes funciones:

(make-tree dato lista-hijos): construye un árbol a partir de un dato y una lista de hijos formada por árboles. La lista puede ser vacía.

(dato-tree tree): devuelve el dato de la raíz del árbol

(hijos-tree tree): devuelve una lista de árboles hijos

Vemos que utilizamos el sufijo -tree para todas las funciones.

Una estructura muy relevante es la lista de hijos, una lista de árboles. En las siguientes funciones vamos a utilizar esta estructura en bastantes ocasiones. Vamos por ello a darle un nombre y denominarla bosque. Decimos, por tanto, que la función hijos-tree es un bosque formado por los hijos del árbol.

¿Cómo implementamos los árboles? En Scheme es muy fácil, utilizando una lista. El primer elemento de la lista es el dato del árbol y el resto de la lista (otra lista) es la lista de hijos.

Las implementación de las funciones es la siguiente:

(define (make-tree dato lista-hijos)  (cons dato lista-hijos))
(define (dato-tree tree)  (car tree))
(define (hijos-tree tree)  (cdr tree))

El árbol anterior se puede construir con las siguientes instrucciones:

(define t1 (make-tree 5 '()))
(define t2 (make-tree 2 '()))
(define t3 (make-tree 3 '()))
(define t4 (make-tree 10 '()))
(define t5 (make-tree 12 '()))
(define t6 (make-tree '* (list t2 t3)))
(define t7 (make-tree '- (list t5)))
(define t8 (make-tree '+ (list t1 t6 t4)))
(define tree (make-tree '* (list t8 t7)))

Si expresamos el árbol en forma de lista podemos comprobar que es una expresión-s:

(+ (5) (* (2) (3)) (10))

De hecho, podríamos construirlo también utilizando directamente su formulación como expresión-s:

(define tree '(+ (5) (* (2) (3)) (10)))

Funciones sobre árboles genéricos

Vamos a construir las siguientes funciones que trabajan sobre árboles genéricos:

(tree-to-list tree): devuelve una lista con los datos del árbol original

(square-tree tree): eleva al cuadrado todos los datos de un árbol manteniendo la estructura del árbol original

(map-tree f tree): devuelve un árbol con la estructura del árbol original aplicando la función f a sud datos.

Vamos a ver que todas ellas comparten un mismo patrón de recursión mutua en la que la función se divide en dos partes: una función sobre árboles y otra sobre bosques (listas de árboles) que se aplica a los hijos.

(tree-to-list tree)

Comencemos con la función (tree-to-list tree) devuelve una lista con todos los elementos del árbol.

(define (to-list-tree tree)
   (cons (dato-tree tree)
         (to-list-bosque (hijos-tree tree)))))

(define (to-list-bosque bosque)
   (if (null? bosque)
       '()
       (append (to-list-tree (car bosque))
               (to-list-bosque (cdr bosque)))))

La recursión de esta función es muy interesante, ya que se basa en una recursión mútua.

La función (to-list-tree tree) obtiene la lista de hijos del nodo actual y llama a la función (to-list-bosque) con ella. Esta función devuelve una lista plana con todos los datos del bosque que le pasamos como parámetro. Sólo falta entonces añadir el dato del árbol inicial.

A su vez, la función to-list-bosque llama a la función to-list-tree para obtener la lista con los datos del primer árbol, se llama a si misma para obtener el bosque con el resto de árboles de la lista y concatena ambas listas llamando a la función append.

(cuadrado-tree tree)

La función cuadrado-tree devuelve el árbol resultante de aplicar la función cuadrado a los números del árbol que se pasa como parámetro.

Es importante notar, al igual que hacíamos cuando hablábamos de árboles binarios, que el árbol resultante es una copia del árbol que se pasa como parámetro y que no se pueden modificar directamente los datos del árbol original porque nos encontramos en el paradigma de programación funcional.

(define (cuadrado-tree tree)
   (make-tree (cuadrado (dato-tree tree))
                   (cuadrado-bosque (hijos-tree tree))))

(define (cuadrado-bosque bosque)
   (if (null? bosque)
       '()
       (cons (cuadrado-tree (car bosque))
               (cuadrado-bosque (cdr bosque)))))

Ambas funciones tienen un patrón muy similar de recursión mutua al usado en la función anterior tree-to-list.

Otra versión muy interesante y compacta es la siguiente:

(define (cuadrado-tree tree)
   (make-tree (cuadrado (dato-tree tree))
              (map cuadrado-tree (hijos-tree tree))))

La recursión se basa en aplicar la propia función a cada uno de los hijos. Para ello se obtiene la lista de hijos con la función hijos-tree y se usa la función map para aplicar la propia función a todos los elementos de esa lista (que son árboles). La lista de árboles resultante se utiliza para construir el árbol que se devuelve añadiendo como dato el cuadrado del dato original.

map-tree

Por último, la función map-tree es la generalización de la función cuadrado-tree anterior y permite aplicar una función cualquiera de un argumento a todos los datos del árbol inicial, devolviendo el árbol resultante.

(define (map-tree f tree)
   (make-tree (f (dato-tree tree))
              (map-bosque f (hijos-tree tree))))

(define (map-bosque f bosque)
   (if (null? bosque)
       '()
       (cons (map-tree f (car bosque))
             (map-forest f (cdr bosque)))))

# data[].attributes.attachment_link.description
Definición: Se llama recursividad a un proceso mediante el que una función se llama a sí misma de forma repetida, hasta que se satisface alguna determinada condición. El proceso se utiliza para computaciones repetidas en las que cada acción se determina mediante un resultado anterior. Se pueden escribir de esta forma muchos problemas iterativos.