Aplicación de los intérpretes interactivo y recursivo

Recursión

Ya hemos visto algunos ejemplos de funciones recursivas. Una función es recursiva cuando se llama a si misma. Una vez que uno se acostumbra a su uso, se comprueba que la recursión es una forma mucho más natural que la iteración de expresar un gran número de funciones y procedimientos.
Recordemos el ejemplo típico de función recursiva, el factorial:

(define (factorial x)
   (if (= x 0)
      1
      (x * (factorial (- x 1)))))

La formulación matemática de la recursión es sencilla de entender, pero su implementación en un lenguaje de programación no lo es tanto. El primer lenguaje de programación que permitió el uso de expresiones recursivas fue el LISP. En el momento de su creación existía ya el Fortran, que no permitía que una función se llamase a si misma.

Confía en la recursión

Ya sabemos cómo es un algoritmo recursivo. Hemos visto varios ejemplos utilizando números, identificadores o listas. Pero… ¿cómo diseñar un algoritmo recursivo? Para resolver un problema de forma recursiva debes:

1. Descomponer el problema principal en alguna versión más simple, que puedas resolver llamando a la propia función recursiva
2. Confiar en la recursión para resolver esta versión más simple del problema y que va a devolver su solución
3. Obtener la solución al problema completo a partir de la solución de la versión más simple

La frase confía en la recursión quiere decir que cuando estés analizando el funcionamiento de un programa recursivo y veas una llamada recursiva debes confiar en que esta llamada va a devolver el resultado que se prentende.
Es útil escribir y pensar en los procedimientos recursivos de forma declarativa, teniendo en cuenta lo que hacen y no cómo lo hacen. Es útil pensar en la formulación recursiva del problema de una forma matemática, analítica o gráfica antes de ponerse a programar. Es muy útil también probar con algunos ejemplos concretos.
¿Cuándo para el algoritmo? Cuando el problema es lo más simple posible y ya no se puede simplificar más: este es el caso base. Debemos entonces devolver un valor concreto, la recursión ya ha terminado.
Vamos a utilizar estos consejos para construir algunos procedimientos recursivos.

longitud

Queremos diseñar la función (longitud lista) que devuelva la longitud de una lista.
Un ejemplo de un diseño recursivo de la función podría ser el siguiente:

• Supongamos que tenemos la lista (a b c d).
• ¿Cómo podemos llamar a la propia función longitud de forma recursiva con una lista más pequeña?
• Podríamos quitar el primer elemento de la lista llamando a cdr y calcular la longitud de la lista restante, confiando en la llamada recursiva:

  (longitud (cdr '(a b c d))) ->
  (longitud '(b c d)) -> 3
  

• Hemos obtenido 3. Como habíamos quitado el primer elemento de la lista, la longitud de la lista original se obtien sumando 1.
• Este ejemplo nos lleva a la formulación declarativa de la recursión:

  longitud (lista) = 1 + longitud (resto (lista))
  

• Falta el caso base. Normalmente es la parte más sencilla. En este caso es trivial: la longitud de la lista vacía es 0.

Y sólo queda convertir este diseño en un programa de Scheme:

(define (longitud lista)
   (if (null? lista)
      0
      (+ 1 (longitud (cdr lista)))))

sumatorio

Queremos implementar la función (sumatorio n m) que devuelve la suma de los números desde n hasta m, ambos incluidos.
Igual que en el ejemplo anterior, comenzamos con un caso sencillo y vemos cómo se puede formular recursivamente.

sumatorio(8,20) = 8+9+...+20 = 8 + (9+10+...+20) = 8+sumatorio(9,20)

También se podría expresar otra recursión:

sumatorio(8,20) = 8+9+...+20 = (8+9+...+19)+20 = sumatorio(8,19)+20

Podemos considerar como caso base el caso en el que n/=/m y devolver n, o el caso en el que n/>/m y devolver 0.
El paso a Scheme es directo.
Versión 1:

(define (sumatorio n m)
   (if (= n m)
      0
      (+ n (sumatorio (+ n 1) m))))

Versión 2:

(define (sumatorio n m)
   (if (= n m)
      0
      (+ m (sumatorio n (- m 1)))))

elemento?

Otro ejemplo. La función (elemento? x lista) que comprueba si el elemento x está incluido en la lista.
El diseño recursivo consiste en quitar el primer elemento de la lista y preguntar si es x o si x está en el resto de la lista. La descripción declarativa es la siguiente:

(define (elemento? x lista)
   (if (null? lista)
      #f
      (or (equal? x (car lista))
          (elemento? x (cdr lista)))))

nth

Vamos a ver cómo encontrar el elemento n-ésimo de una lista de forma recursiva. Este va a ser un ejemplo algo distinto a los anteriores, ya que aquí no tendremos que construir ninguna solución a partir de la llamada recursiva, sino que debermos buscar esta solución haciendo cada vez más sencillo el problema.
Vamos a llamar a la función (nth n lista), donde n es la posición del elemento que queremos devolver (comenzando por 1) y lista es la lista que recorremos.
Podemos empezar por preguntarnos qué sabemos hacer con las listas:

• Devolver el primer elemento de una lista utilizando la función car
• Devolver el resto de la lista sin el primer elemento utilizando la función cdr

O sea, que si nos preguntaran por el primer elemento de la lista:

(nth 1 '(a b c))

para devolverlo habría que llamar a car:

(car '(a b c)) -> a

¿Cómo podríamos usar la recursión para devolver un elemento que no está en primer lugar? Esto es, ¿qué hacer cuando n es distinto de 1? Habrá que simplificar el problema y pasarle a la llamada recursiva la lista sin el primer elemento y habiendo restado 1 a n:

(define (nth n lista)
  (if (= n 1)
    (car lista)
    (nth (- n 1) (cdr lista)))

¿Qué pasaría si se llama a la función con el número n siendo mayor que el número de elementos de la lista? Tendríamos un error, ya que la se intentaría obtener el primer elemento de una lista vacía. Para solucionarlo, basta con contemplar este caso como otra posible condición de terminación de la recursión:

(define (nth n lista)
  (cond
    ((null? lista) lista)
    ((= n 1) (car lista))
    (else (nth (- n 1) (cdr lista)))))

Recursión mutua

A veces es útil usar un patrón de recursión mutua, en el que dos funciones se llaman una a la otra. El patrón recuerda la famosa ilustración Drawing Hands de M.C. Escher:

Un primer ejemplo de este comportamiento es la definición recursiva mutua de par e impar:

• x es par si x-1 es impar
• x es impar si x-1 es par
• 0 es par

La implementación en Scheme es directa:

(define (par? x)
   (if (= 0 x)
      #t
      (impar? (- x 1))))

(define (impar? x)
   (if (= 0 x)
      #f
      (par? (- x 1))))

Un ejemplo algo más complejo es la curva de Hilbert. La curva de Hilbert es una curva fractal que tiene la propiedad de rellenar completamente el espacio. Su dibujo tiene una formulación recursiva.

Vemos que la curva H3 se puede construir a partir de la curva H2.
Utilizamos la librería graphics/turtles que permite usar la conocida tortuga y comandos de Logo en Scheme (draw y turn).

• La función (h-der i w) dibuja una curva de Hilbert de orden i con una longitud de trazo w a la derecha de la tortuga.
• La función (h-izq i w) dibuja una curva de Hilbert de orden i con una longitud de trazo w a la izquierda de la tortuga.

Para dibujar una curva de Hilbert de orden i a la derecha de la tortuga:

1. Gira la tortuga -90
2. Dibuja una curva de orden i-1 a la izquierda
3. Avanza w dibujando
4. Gira 90
5. Dibuja una curva de orden i-1 a la derecha
6. Avanza w dibujando
7. Dibuja una curva de orden i-1 a la derecha
8. Gira 90
9. Avanza w dibujando
10. Dibuja una curva de orden i-1 a la izquierda
11. Gira -90

El algoritmo para dibujar a la izquierda es simétrico.
Algoritmo en Scheme:

(require graphics/turtles)
(turtles #t)
(define (h-der i w)
    (if (> i 0)
        (begin
          (turn -90)
          (h-izq (- i 1) w)
          (draw  w)
          (turn 90)
          (h-der (- i 1) w)
          (draw w)
          (h-der (- i 1) w)
          (turn 90)
          (draw w)
          (h-izq (- i 1) w)
          (turn -90))))
(define (h-izq i w)
    (if (> i 0)
      (begin
        (turn 90)
        (h-der (- i 1) w)
        (draw  w)
        (turn -90)
        (h-izq (- i 1) w)
        (draw w)
        (h-izq (- i 1) w)
        (turn -90)
        (draw w)
        (h-der (- i 1) w)
        (turn 90))))

Podemos probarlo con distintos parámetros de grado de curva y longitud de trazo:

(clear)
(h-izq 3 20)
(h-izq 6 5)

El resultado de esta última llamada es:

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 2ⁿ, siendo n el número que se pasa a la función. El coste espacial y temporal es por tanto de O(2ⁿ). 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 coldeseado.
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₂, …, m_n) -> (m₁ . (m₂ . ( … (m_n . 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)))h

ttp://www.dccia.ua.es/dccia/inf/asignaturas/LPP/2010-2011/teoria/tema4.html#sec-3_2