Download Procedimientos y estructuras recursivas

Tema 4: Procedimientos y estructuras recursivas
Sesión 11: Procedimientos y estructuras recursivas (3)
martes 15 de marzo de 2011
Hoy veremos...
• Diseño de procedimiento recursivos
• Recursión mutua
• Coste espacial de la recursión
• Tail Recursion (recursión por la cola)
• Expresiones S
• Árboles binarios y genéricos
martes 15 de marzo de 2011
Referencias
• Capítulo 1.2.1, 1.2.2 Abelson & Sussman: Linear Recursion and Iteration, Tree
Recursion
martes 15 de marzo de 2011
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)))))
martes 15 de marzo de 2011
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)))))
martes 15 de marzo de 2011
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))
martes 15 de marzo de 2011
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?
martes 15 de marzo de 2011
Implementación de funciones sobre listas de
asociación
• Implementación de my-assq:
(define (my-assq x lista)
(cond
((null? lista) #f)
((equal? (caar lista) x) (car lista))
(else (my-assq x (cdr lista)))))
• Implementación de add-pair:
• ¿Cómo haríamos delete-pair? ¿Y modify-pair?
martes 15 de marzo de 2011
Implementación de funciones sobre listas de
asociación
• Implementación de my-assq:
(define (my-assq x lista)
(cond
((null? lista) #f)
((equal? (caar lista) x) (car lista))
(else (my-assq x (cdr lista)))))
• Implementación de add-pair:
(define (add-pair key value lista)
(if (not (my-assq key lista))
(cons (cons key value)
lista)
(error "ya existe la clave")))
• ¿Cómo haríamos delete-pair? ¿Y modify-pair?
martes 15 de marzo de 2011
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:
- 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
• Con la misma notación una lista se define de la siguiente forma:
(a1 a2 ... an) = (a1 . (a2 . ( ... (an . NIL) ...)))
• El dato atómico NIL es el fin de lista
martes 15 de marzo de 2011
Expresiones-S de McCarthy
• Las siguientes expresiones son expresiones-s de McCarthy:
• Las siguientes expresiones no son expresiones-S de McCarthy:
martes 15 de marzo de 2011
Expresiones-S de McCarthy
• Las siguientes expresiones son expresiones-s de McCarthy:
(A . B)
(A . (B . C))
((A . B) . (C . D))
(A. ((A . B) . (C . D)))
• Las siguientes expresiones no son expresiones-S de McCarthy:
martes 15 de marzo de 2011
Expresiones-S de McCarthy
• Las siguientes expresiones son expresiones-s de McCarthy:
(A . B)
(A . (B . C))
((A . B) . (C . D))
(A. ((A . B) . (C . D)))
• Las siguientes expresiones no son expresiones-S de McCarthy:
(A . B . C)
(A)
(() . B)
martes 15 de marzo de 2011
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:
(= 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 definición que vamos a usar a partir de ahora
• En Scheme se implementan como listas
martes 15 de marzo de 2011
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)))
martes 15 de marzo de 2011
Las expresiones-S definen estructuras jerárquicas
• Las expresiones-s pueden representan una estructura de niveles
• Los datos de las listas representan las hojas:
((1 2 3) 4 5)
4 5
1 2 3
• Otro ejemplo:
(let ((x 12)
(y 5))
(+ x y)))
martes 15 de marzo de 2011
let
+
x
12 y
5
y
z
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
martes 15 de marzo de 2011
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
• 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
martes 15 de marzo de 2011
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)))
martes 15 de marzo de 2011
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
martes 15 de marzo de 2011
cuenta-hojas-exp
martes 15 de marzo de 2011
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))))))
martes 15 de marzo de 2011
niveles-exp
martes 15 de marzo de 2011
niveles-exp
(define (niveles-exp exp)
(cond
((null? exp) 0)
((hoja? exp) 0)
(else (max (+ 1 (niveles-exp (car exp)))
(niveles-exp (cdr exp))))))
martes 15 de marzo de 2011