En la entrada anterior, mostré un poco la relación que existe entre listas y recursividad. Ahora voy a describir un poco más esa relación haciendo una serie de ejemplos tomados del conocido libro How to design programs. Disfrútenlos.

Nota: Esta entrada parte del hecho de que se conoce la idea de recursividad y la relación que existe entre ésta y las listas. En caso de no comprender bien ese tema, por favor lea la entrada introducción a la recursividad. Esta no es una traducción literal.

Fuente: Compound data, Part 2: Lists

Uno de los primeros ejemplos es un inventario. Un inventario comienza con una página en blanco, eso para los programadores de Scheme sería una lista vacía o como ya sabemos un empty. Luego, quien administra el inventario añade elementos a la lista, por ejemplo, en una juguetería se agregarían muñecas, pelotas, flechas, arcos y la hoja de papel que contiene el inventario siempre tendría espacio en blanco al final, lo que indicaría que la lista termina con un vacío (empty en inglés). En nuestro lenguaje de programación, lo anterior obedece a la ya descrita definición recursiva de una lista (un elemento seguido de una lista de elementos -el resto de la lista).

Ejemplo: Lista de juguetes

(define juguetes1 (cons 'arco (cons 'flecha (cons 'pelota empty))) )
(define juguetes2 (cons 'arco (cons 'muñeca (cons 'pelota empty))) )

Como hemos visto anteriormente, la definición de una lista podría ser más simple usando la función list, pero la declaración de la línea anterior es recursiva, ya que usa cons que toma un elemento y una lista para devolver una nueva lista compuesta por la unión de los dos argumentos.

¿Cómo saber si en cierta lista de juguetes existe uno en particular, por ejemplo, una ‘muñeca?

Se concibe una receta de diseño como un mecanismo simplificado para saber cómo hacer una función general. En nuestro caso, la receta se implementaría mediante el desarrollo de operaciones simples que hagan parte o todo el trabajo que quisiéramos de la función general pero sobre un conjunto de datos conocido, luego, comprendidos todos los casos y la mecánica general de la función se construye ésta de tal manera que sea más general y haga su trabajo sobre un conjunto da datos arbitrario y desconocido.

Para desarrollar una función que descubra si en una lista arbitraria (cuyo contenido es incierto) existe cierto elemento particular, vamos a mirar cómo se haría primero manualmente sobre una lista de datos conocida y luego desarrollamos la función deseada.

Quiero saber si en la lista anterior existe por lo menos un ‘arco. Dado que es el primero de la lista, la operación es trivial:

(equal? (first juguetes1) 'arco) -->  true

Y si preguntáramos por, por ejemplo, una ‘pelota que es la tercera haríamos la siguiente operación:

(cond [ (equal? (first juguetes1) 'pelota) true] [ (equal? (first (rest juguetes1)) 'pelota) true][ (equal? (first (rest (rest juguetes1))) 'pelota) true][else false] )

Como vemos, es posible determinar qué operaciones se necesitan regularmente para obtener el resultado esperado, ahora necesitamos saber cómo hacerlo sin conocer la lista. El código anterior sólo sirve para listas de tres o más elementos, sin embargo para listas de más de tres elementos que contengan el valor buscado más allá del tercer elemento siempre dirá que no está. Por otro lado, el mismo problema se podría partir en varias partes notables:

  • ¿Qué hacer si pasan una lista vacía a la función?, ¿qué retornar?
  • ¿Cuándo se logra el objetivo?, es decir, ¿cuándo retornar true?
  • ¿Se puede simplificar el problema?

Si la lista pasada como argumento es  vacía, se puede devolver false, ya que si la lista está vacía el elemento buscado no existe dentro ella. ¿Cuándo se logra el objetivo?, cuando un elemento de la lista es el buscado, es decir, en esa único caso la función retornaría true, pero las operaciones recursivas en una lista están limitadas a first/rest y sólo first me retorna un elemento particular de la lista, por lo tanto sólo puedo saber si el primer elemento es el que busco o no. ¿Se puede simplificar el problema?, sí, los casos anteriores retornan false y true respectivamente y eso es todo lo que va a retornar la función, osea que esos son los casos que terminan la ejecución de la misma, por otro lado la simplificación de la operación consiste en acercarla a uno de esos dos casos: o el primero es el buscado o la lista quedó vacía y el elemento no estaba en la lista.

La solución al problema (función que busca si hay flechas en un inventario de juguetes) se puede presentar entonces de la siguiente manera:

(define (hay-flecha? inv)
(cond
[(equal? (first inv) 'flecha) true]
[(empty? inv) false]
[else (hay-flecha? (rest inv))]
)
)
; Casos de prueba, el primero debe retornar true, el segundo debe retornar false
(hay-flecha? juguetes1)
(hay-flecha? juguetes2)

La función anterior se puede intepretar más precisamente como la función que verifica si hay por lo menos un elemento ‘flecha en la lista de juguetes pasada como argumento. Como vemos, la operación de la función es bastante clara: si el primer elemento es el buscado retorne verdadero (lo encontró), si la lista está vacía retorne falso (no hay flecha) y si no es ninguno de los dos casos, continúe hasta llegar a alguno de los dos.

Sumar una lista de números

Otro ejemplo es la suma de una lista de números. ¿Cuáles son los casos base?: cuando la lista está vacía y cuando la lista tiene un sólo elemento, en caso contrario hay que ejecutar una parte del problema y reducirlo para acercarlo a alguno de los casos base (operar sobre el resto de la lista).

(define numeros (list 2 4 6))

La operación directa sería la siguiente:

(+ (first numeros) (first (rest numeros)) (first (rest (rest numeros))))

De la operación manual se deducen dos cosas, un caso base es cuando la lista queda vacía (rest (rest … )), esta concatenación de extracciones del primer elemento vaciarán finalmente la lista. Por otro lado, la operación se hace sobre el primer elemento y sobre cada llamado adicional de rest. La solución sería entonces la siguiente:

(define numeros (list 2 4 6))
(define (suma ldn)
(if (empty? ldn) 0
(+ (first ldn) (suma (rest ldn)))
)
)
; Llamados de prueba, el primero debe retornar 12 (2 + 4 +6) el segundo 0 y el tercero 10
(suma numeros)
(suma empty)
(suma (list 3 7))

Ejercicios

Los anteriores son ejemplos de recursividad del libro citado, ahora voy a poner la interpretación de algunos de los ejercicios propuestos en el mismo. Para todos los casos valide que los valores pasados sí son de los tipos esperados, es decir, si se dice lista de números se debe validar que cada elemento sea un número:
  1. Desarrolle la función cuantos-simbolos que determina cuántos elementos de una lista son símbolos, por ejemplo (cuantos-simbolos (list ‘a 1 2 “c”)) debe retornar 1, ya que sólo uno de los elementos es un símbolo.
  2. Desarrolle la función cuantos-numeros, que determina cuántos elementos de una lista son números de la misma manera que en el punto anterior se contaban los símbolos.
  3. Desarrolle la función menos-de-mil, que toma una lista de precios (números) y determina si todos los valores están por debajo de 1000, en otras palabras, retornará verdadero o falso según se cumpla la condición.
  4. Generalice la función anterior, para que tome no sólo la lista sino el valor umbral. En otras palabras, si la función se llama con una lista de números y el valor 100, la función retornará verdadero si todos los valores están por debajo de 100, si se llama con una lista de números y el valor 1, la función retornará verdadero si todos los valores están por debajo de 1.
  5. Desarrolle la función verificar-rango que toma una lista de temperaturas (números) y verifica que todas estén dentro del rango 5°C a 95°C.
  6. Generalice la función anterior para que la función tome no sólo la lista de números sino un rango válido y se verifique que todas las temperaturas están dentro del rango dado.
  7. Desarrolle la función convertir que toma una lista de números de 0 a 9 y retorna el valor posicional completo, por ejemplo (convertir (list 1 2 3)) debe retornar 321 (significado: convertir las cifras 3 2 1 al valor trescientos veintiuno), (convertir (lista 5 1 9)) debe retornar 915.
  8. Desarrolle la función delta, que toma dos listas de precios (números), los mismos productos al principio del año y al final del año y obtiene la diferencia de precios. En otras palabras, retornar una lista compuesta por la diferencias de precios de la primera lista con la segunda, si un precio aumentó el resultado debe ser positivo y si un precio bajó debe ser negativo.
  9. Use el teachpack htdp/draw para hacer una función que consume una lista de números y una estructura posn. La función debe dibujar círculos rojos centrados en el punto dado pero con radios iguales a aquellos de la lista de números dada. Retornar true. No olvide crear un canvas invocando la función (start 300 300) antes de llamar a la función.
  10. Desarrolle la función bin-dec que tome una lista de unos y ceros únicamente y retorne el valor decimal que compone la lista, por ejemplo, (bin-dec (list 1 0 1 0)) debe retornar 10 (2^3+2^1).