Tema 4: Procedimientos y estructuras recursivas · Tema 4: Procedimientos y estructuras recursivas Sesión 9: Recursión (1) martes 8 de marzo de 2011 En este tema veremos... •Diseño

Tema 4: Procedimientos y estructuras recursivas

Sesión 9: Recursión (1)

martes 8 de marzo de 2011

En este tema veremos...

• Diseño de procedimiento recursivos

• Recursión mutua

• Coste espacial de la recursión

• Recursión por la cola

• Expresiones S

• Árboles binarios y genéricos


Confía en la recursión

• Para diseñar procedimientos recursivos debemos fijarnos en lo que hace el procedimiento (programación declarativa):

• Debemos descomponer el problema de forma que podamos lanzar la recursión sobre una versión más sencilla del mismo

• Obtener la solución de la versión más pequeña

• Devolver la solución completa

• Debemos confiar en que la llamada recursiva va a hacer su trabajo y devolver el resultado correcto, sin preocuparnos de cómo lo va a hacer.

• Es útil utilizar una notación matemática antes de programar.


Longitud de una lista

• Definición matemática de la longitud de una lista:

• Implementación:





Longitud (l) = 1 + Longitud (resto (l)) Longitud (lista-vacía) = 0





Longitud (l) = 1 + Longitud (resto (l)) Longitud (lista-vacía) = 0

(define (mi-length items) (if (null? items) 0 (+ 1 (mi-length (cdr items)))))


Sumatorio

• Definición matemática del sumatorio:



Sumatorio



Sumatorio(min,max) = min + Sumatorio (min+1, max) Sumatorio(min,max) = min si min=max


Sumatorio



Sumatorio(min,max) = min + Sumatorio (min+1, max) Sumatorio(min,max) = min si min=max

(define (sumatorio min max) (if (= min max) min (+ min (sumatorio (+ 1 min) max))))


list-reverse

• ¿Cómo podríamos de invertir una lista forma recursiva? Un minuto para confiar en la recursión

• Escribe la definición matemática

• Escribe el programa en Scheme


mi-list-ref



mi-list-ref


(define (mi-list-ref lista n) (cond ((null? lista) (error "indice mayor que tamaño de lista")) ((= n 0) (car lista)) (else (mi-list-ref (cdr lista) (- n 1)))))


Recursión mutua

• Hay veces en que la definición de una función se puede realizar en función de una segunda, que a su vez se define en base a la primera.

• Ejemplo:

• Programas en Scheme:

x es par si x-1 es imparx es impar si x-1 es par0 es par


Recursión mutua


• Ejemplo:



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


Recursión mutua


• Ejemplo:




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


Ejemplo avanzado: curvas 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 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.


Algoritmo curva de Hilbert

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

• El algoritmo para dibujar a la izquierda es simétrico.

Gira la tortuga -90Dibuja una curva de orden i-1 a la izquierdaAvanza w dibujandoGira 90Dibuja una curva de orden i-1 a la derechaAvanza w dibujandoDibuja una curva de orden i-1 a la derechaGira 90Avanza w dibujandoDibuja una curva de orden i-1 a la izquierdaGira -90


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


Lo probamos

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

• El resultado de esta última llamada es:

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



Sesión 10: Recursión (2)

miércoles 9 de marzo de 2011

Hoy veremos...




• Recursión por la cola

• Expresiones S



Recordamos... Recursión mutua

• Hay veces en que la definición matemática de una función se puede realizar en función de una segunda, que a su vez se define en base a la primera.

• Ejemplo:




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


Ejemplo avanzado de recursión mutua: Curvas de Hilbert

• Hilbert: matemático alemán que diseñó las curvas que llevan su nombre en 1900s.

• 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.

H1 H2 H3



• Utilizamos la librería graphics/turtles que permite usar la 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.


Algoritmo curva de Hilbert

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

• El algoritmo para dibujar a la izquierda es simétrico.

Gira la tortuga -90Dibuja una curva de orden i-1 a la izquierdaAvanza w dibujandoGira 90Dibuja una curva de orden i-1 a la derechaAvanza w dibujandoDibuja una curva de orden i-1 a la derechaGira 90Avanza w dibujandoDibuja una curva de orden i-1 a la izquierdaGira -90


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


Lo probamos

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

• El resultado de esta última llamada es:

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


Ejercicio recursión mutua

• Implementa, utilizando recursión mutua, una variante de map que sólo aplique la función a ciertas partes de la lista.

> (map-par cuadrado '(1 1 1 3 3 3)) (1 2 1 6 3 6)> (map-impar cuadrado '(1 1 1 3 3 3)) (2 1 2 3 6 3)> (map-par car '((1 2 3) (4 5 6) (7 8) (a b c))) ((1 2 3) 4 (7 8) a)> (map-impar car '((1 2 3) (4 5 6) (7 8) (a b c))) (1 (4 5 6) 7 (a b c))

– (map-par f lista): devuelve una nueva lista donde las posiciones pares son el resultado de aplicar f al correspondiente elemento en la lista, y las impares no varían.– (map-impar f lista): devuelve una nueva lista donde las posiciones impares son el resultado de aplicar f al correspondiente elemento de la lista, y las pares no varían.


Ejercicio recursión mutua

(define (map-par f lis) (if (null? lis) ‘() (cons (car lis) (map-impar f (cdr lis)))))

(define (map-impar f lis) (if (null? lis) ‘() (cons (f (car lis)) (map-par f (cdr lis)))))

>(map-par cuadrado (1 2 3 4))> (map-impar cuadrado (2 3 4))> >(map-par cuadrado (3 4))> > (map-impar cuadrado (4))> > >(map-par cuadrado ())< < <()< < (16)< <(3 16)< (4 3 16)<(1 4 3 16)

>(map-impar cuadrado (1 2 3 4))> (map-par cuadrado (2 3 4))> >(map-impar cuadrado (3 4))> > (map-par cuadrado (4))> > >(map-impar cuadrado ())< < <()< < (4)< <(9 4)< (2 9 4)<(1 2 9 4)


La pila de la recursión

• Vamos a estudiar el comportamiento del proceso generado por una llamada a un procedimiento recursivo

• Examinamos cómo se realizan las llamadas recursivas











(mi-length '(a b c d))(+ 1 (mi-length '(b c d)))(+ 1 (+ 1 (mi-length '(c d))))(+ 1 (+ 1 (+ 1 (mi-length '(d)))))(+ 1 (+ 1 (+ 1 (+ 1 (mi-length '())))))(+ 1 (+ 1 (+ 1 (+ 1 0))))(+ 1 (+ 1 (+ 1 1)))(+ 1 (+ 1 2))(+ 1 3)4



• Cada llamada a la recursión deja una función en espera de ser evaluada cuando la recursión devuelva un valor (en el caso anterior el +)

• Esta función, junto con sus argumentos, se almacenan en la pila de la recursión

• Cuando la recursión devuelve un valor, los valores se recuperan de la pila, se realiza la llamada y se devuelve el valor a la anterior llamada en espera

• Si la recursión está mal hecha y nunca termina se genera un stack overflow


El coste espacial de la recursión

• El coste espacial de un programa es una función que relaciona la memoria consumida por una llamada para resolver un problema con alguna variable que determina el tamaño del problema a resolver

• La notación O() indica una cota superior a ese coste

• En el caso de la función mi-length el tamaño del problema viene dado por la longitud de la lista

• El coste espacial de mi-length es O(n), siendo n la longitud de la lista


El coste espacial depende del número de llamadas a la recursión

• Ejemplo: Fibonacci

• Secuencia de Fibonacci: 1,1,2,3,5,8,13

• Formulación matemática:

• En Scheme:






• En Scheme:

Fibonacci(n) = Fibonacci(n-1) + Fibonacci(n-2) Fibonaci(1) = Fibonacci(0) = 1






• En Scheme:

Fibonacci(n) = Fibonacci(n-1) + Fibonacci(n-2) Fibonaci(1) = Fibonacci(0) = 1

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


Evaluación de una llamada a Fibonacci

• Cada llamada a la recursión produce otras dos llamadas

• El número de llamadas finales es 2^n, siendo n el número que se pasa a la función

• Coste espacial y temporal: O(2^n)

• ¿Qué pasaría con (fibonaci 100)?


Proceso iterativo

• Es posible modificar la formulación de la recursión para se eviten las llamadas en espera

• Ejemplo: factorial iterativo


• Secuencia de llamadas:

Factorial iterativo

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

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


mi-length iterativo

• ¿Cómo sería la versión iterativa de mi-length?


mi-length iterativo

• ¿Cómo sería la versión iterativa de mi-length?

(define (mi-length-iter lista) (mi-length-iter-aux lista 0))

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


Procesos iterativos

• La recursión resultante es menos elegante

• Se necesita una parámetro adicional en el que se van acumulando los resultados parciales

• La última llamada a la recursión devuelve el valor acumulado

• El proceso resultante de la recursión es iterativo en el sentido de que no deja llamadas en espera ni incurre en coste espacial


Tail recursion

• A este tipo de recursión se le denomina tail recursion (definición en Wikipedia)

• Se puede realizar una implementación eficiente de la ejecución del proceso, eliminando la pila de la recursión


Fibonacci iterativo

• Cualquier programa recursivo se puede transformar en otro que genera un proceso iterativo

• En general, las versiones iterativas son menos intuitivas y más difíciles de entender y depurar

• Ejemplo: Fibonacci iterativo


Fibonacci iterativo

• Cualquier programa recursivo se puede transformar en otro que genera un proceso iterativo

• En general, las versiones iterativas son menos intuitivas y más difíciles de entender y depurar

• Ejemplo: Fibonacci iterativo

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

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


Memoization

• Una alternativa que mantiene la elegancia de los procesos recursivos y la eficiencia de los iterativos es la memoization (enlace en la Wikipedia)

• Si miramos la traza de (fibonacci 4) podemos ver que el coste está producido por la repetición de llamadas; por ejemplo (fibonacci 3) se evalúa 2 veces

• En programación funcional la llamada a (fibonacci 3) siempre va a devolver el mismo valor

• Podemos guardar el valor devuelto por la primera llamada en alguna estructura (una lista de asociación, por ejemplo) y no volver a realizar la llamada a la recursión las siguientes veces


Triángulo de Pascal


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


Triángulo de Pascal


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

Pascal (_,0) = Pascal (x,x) = 1 Pascal (fila, columna) = Pascal (fila-1,columna-1) + Pascal (fila-1, columna)



• En Scheme:

Triángulo de Pascal. Versión recursiva




• En Scheme:

Triángulo de Pascal. Versión recursiva

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



Triángulo de Pascal. Versión iterativa

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

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

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



Sesión 11: Procedimientos y estructuras recursivas (3)


Hoy veremos...




• Tail Recursion (recursión por la cola)

• Expresiones S



Referencias

• Capítulo 1.2.1, 1.2.2 Abelson & Sussman: Linear Recursion and Iteration, Tree Recursion


Repaso: ¿cómo modificar una lista en programación funcional?

• En programación funcional no es posible modificar una lista. Siempre hay que construir una nueva. Se puede añadir elementos a una lista ya existente.

(define (cuadrado lista) (if (null? lista) '() (cons (cuadrado (car lista)) (cuadrado (cdr lista)))))


Repaso: ¿cómo modificar una lista en programación funcional?

• En programación funcional no es posible modificar una lista. Siempre hay que construir una nueva. Se puede añadir elementos a una lista ya existente.

(define (cuadrado lista) (if (null? lista) '() (cons (cuadrado (car lista)) (cuadrado (cdr lista)))))

(define (mi-map proc lista) (if (null? lista) '() (cons (proc (car lista)) (mi-map proc (cdr lista)))))


Listas de asociación

• Una lista de asociación es una lista cuyos elementos son parejas de la forma (clave, valor)

• Scheme define la función assq que busca una pareja por su clave

• Ejemplos:

(define l-assoc (list (cons 'a 1) (cons 'b 2) (cons 'c 3)))(assq 'a l-assoc)(assq 'b l-assoc)(assq 'c l-assoc)(assq 'd l-assoc)(cdr (assq 'c l-assoc))


Implementación de funciones sobre listas de asociación

• Implementación de my-assq:

• Implementación de add-pair:

• ¿Cómo haríamos delete-pair? ¿Y modify-pair?






(define (my-assq x lista) (cond ((null? lista) #f) ((equal? (caar lista) x) (car lista)) (else (my-assq x (cdr lista)))))






(define (my-assq x lista) (cond ((null? lista) #f) ((equal? (caar lista) x) (car lista)) (else (my-assq x (cdr lista)))))

(define (add-pair key value lista) (if (not (my-assq key lista)) (cons (cons key value) lista) (error "ya existe la clave")))


Expresiones-S originales

• Introducidas originalmente 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.

• En su definición original matemática las expresiones-S se escriben utilizando la notación del punto:

• Con la misma notación una lista se define de la siguiente forma:

• El dato atómico NIL es el fin de lista

- Un dato atómico es una expresión-S- Si e1 y e2 son expresiones-S, la expresión (e1 . e2) también es una expresión-S

(a1 a2 ... an) = (a1 . (a2 . ( ... (an . NIL) ...)))


Expresiones-S de McCarthy

• Las siguientes expresiones son expresiones-s de McCarthy:

• Las siguientes expresiones no son expresiones-S de McCarthy:





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





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

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


Notación ampliada de las expresiones-S

• La definición de la expresión-S original se ha extendido, eliminando la notación del punto y refiriéndose a expresiones con un número balanceado de paréntesis:

• Esta es la definición que vamos a usar a partir de ahora

• En Scheme se implementan como listas

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


Expresiones-S en Scheme

• Cualquier expresión de Scheme es una expresión-s

• No todas las expresiones-s son expresiones de Scheme

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


Las expresiones-S definen estructuras jerárquicas

• Las expresiones-s pueden representan una estructura de niveles

• Los datos de las listas representan las hojas:

• Otro ejemplo:

((1 2 3) 4 5)

1 2 3

4 5

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

+ y z

x 12 y 5

let


Definición recursiva y funciones de manejo

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


Definición recursiva y funciones de manejo

• Funciones para trabajar con expresiones-S: Una expresión-s es una lista, utilizaremos para construirlo y recorrerlo las funciones definidas sobre listas:

• list y quote: construcción

• cons: añadir elemento a la cabeza

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

• cdr: devuelve el resto (siempre una lista)

• null?: comprueba si es lista vacía

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


Función hoja?

• 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

• (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


cuenta-hojas-exp


cuenta-hojas-exp

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


niveles-exp


niveles-exp

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





Hoy veremos...





• Expresiones S



Referencias



Funciones sobre expresiones-S

• (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


Función hoja?

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


pertenece-exp?


pertenece-exp?

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


cuadrado-exp


cuadrado-exp

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


map-exp


map-exp

(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

• Definición recursiva:

• En la asignatura no nos preocupa cuáles son los datos del árbol, ni su ordenación; sólo la estructura

- Un árbol binario es una estructura que contiene un dato, un hijo izquierdo y un hijo derecho (ambos árboles binarios)- Un árbol vacío es un árbol binario


Barrera de abstracción

• Llamamos barrera de abstracción al conjunto de funciones que permiten trabajar con una abstracción y aislan su implementación

• Las 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

• 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.

• Otros nombres alternativos: capa de una aplicación, interfaz, API (Application Programming Interface)


Barrera de abstracción de árboles binarios


Funciones de la barrera de abstracción de árboles binarios

• (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


Ejemplo

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


Implementación

• Implementación de la estructura de datos: un árbol binario es una lista con 3 elementos: el dato de la raíz, el árbol que forma el hijo izquierdo y el árbol que forma el hijo derecho


• Los árboles binarios son expresiones-s

• ¿Cuál es la expresión-s del árbol anterior?

Implementación de las funciones

(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

• (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): añade (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


to-list-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)))))


member-bt?

• Se utiliza en árboles binarios ordenados


member-bt?


(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



insert-bt


(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


insert-list-bt

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


list-to-bt


list-to-bt

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





Hoy veremos...





• Expresiones S

• Árboles binarios y árboles genéricos


Referencias


• Capítulo 6.6 Programming Language Pragmatics: Recursion


Árboles binarios


• En la asignatura no nos preocupa cuáles son los datos del árbol, ni su ordenación; sólo la estructura

- Un árbol binario es una estructura que contiene un dato, un hijo izquierdo y un hijo derecho (ambos árboles binarios)- Un árbol vacío es un árbol binario


Funciones de la barrera de abstracción de árboles binarios

• (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


insert-bt

• Devuelve un nuevo árbol binario en el que se ha añadido un número (se aplica a árboles binarios ordenados)


insert-bt

• Devuelve un nuevo árbol binario en el que se ha añadido un número (se aplica a árboles binarios ordenados)

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


• Devuelve un árbol binario ordenado resultado de añadir una lista de números a un árbol binario inicial

insert-list-bt


• Devuelve un árbol binario ordenado resultado de añadir una lista de números a un árbol binario inicial

insert-list-bt

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


• Construye un árbol binario ordenado a partir de una lista de números

list-to-bt


• Construye un árbol binario ordenado a partir de una lista de números

list-to-bt

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


Árboles genéricos


• La lista de árboles hijos puede ser vacía.

• No usamos el concepto de árbol-vacio, un árbol o nodo hoja es un árbol cuya lista de hijos es una lista vacía.

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


Ejemplo


Barrera de abstracción de árboles genéricos

• 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

• Bosque: lista de árboles (devueltos por la función hijos-tree)


Implementación de las funciones

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


Ejemplo

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


Los árboles genéricos son expresiones-s

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

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

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

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


Funciones sobre árboles genéricos

• Funciones:

• (to-list-tree 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 sus datos.

• Todas comparten un patrón similar de recursión mutua


to-list-tree

(to-list-tree '(* (+ (5) (* (2) (3)) (10)) (- (12)))) (* + 5 * 2 3 10 - 12)


to-list-tree

(to-list-tree '(* (+ (5) (* (2) (3)) (10)) (- (12)))) (* + 5 * 2 3 10 - 12)

(define (to-list-tree tree) (if (null? (hijos-tree tree)) (list (dato-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)))))


cuadrado-tree (versión 1)

(cuadrado-tree '(2 (3 (4) (5)) (6))) (4 (9 (16) (25)) (36))



(cuadrado-tree '(2 (3 (4) (5)) (6))) (4 (9 (16) (25)) (36))

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



(cuadrado-tree '(2 (3 (4) (5)) (6))) (4 (9 (16) (25)) (36))



(cuadrado-tree '(2 (3 (4) (5)) (6))) (4 (9 (16) (25)) (36))

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


map-tree

(map-tree (lambda (x) (+ x 1)) '(2 (3 (4) (5)) (6)))(3 (4 (5) (6)) (7))


map-tree

(map-tree (lambda (x) (+ x 1)) '(2 (3 (4) (5)) (6)))(3 (4 (5) (6)) (7))

(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-bosque f (cdr bosque)))))


Ejercicios

• (niveles-tree tree): devuelve la profundidad del árbol genérico

• (pertenece-tree? tree elem): devuelve verdadero si elem es algún dato del árbol

• (mismo-dato-tree? tree dato): devuelva verdadero si existe algún nodo en el árbol que tenga el mismo dato que uno de sus hijos directos (no nieto ni sobrino) y falso si no existe.

• (nodos-niveles-tree tree): devuelve una lista con el número de nodos en cada nivel del árbol


Documents

Tema 4: Procedimientos y estructuras recursivas · Tema 4: Procedimientos y estructuras recursivas Sesión 9: Recursión (1) martes 8 de marzo de 2011 En este tema veremos... •Diseño