clase7 3

750080M:
Fundamentos de
Programación
Universidad del Valle
Escuela de Ingeniería de
Sistemas y Computación
Clase 8
Recursión y Listas

Recursión

Definición??
Recursión: Ver Recursión.

RecursiónRecursión se presenta cuando una función se
llama a sí misma.
Poderoso Mecanismo para realizar procesos
repetitivos.
Los programas son más compactos y sencillos.
Las Funciones realmente llaman a una“copia” de sí
mismas.
Muy útil, especialmente para tipos dinámicos de
datos.

Tres Características de la
Recursión
1. La Función se llama a sí misma.
2. Existe una condición de terminación.
3. Cada vezse acerca más a la
condición de terminación.

Cómo se procesa una lista?
Respecto a las listas, su manejo se apoya en la
recursión.
•

Se dispone de una condición de parada que
permite detener elprocesamiento
la lista vacía (empty)

•

Se dispone de una operación que
paulatinamente aproxima a la condición de
parada.
(rest …)

Procesando una lista de números
Definición del Problema: Escribir unafunción sum-list
que a partir de una lista de números determine la suma
de los números presentes en la lista.

La Guía de Diseño
;;Análisis y Definición de Datos:
;; Una lista-de-números consistede:
;; 1) la lista vacía, empty, o
;; 2) (cons n lon) donde n es un
;;
número y lon es una lista-de-números.

La Guía de Diseño

;Data Analysis & Definitions:
;;Análisis y Definición de Datos:

;; Unalista-de-números consiste de:
;; 1) la lista vacía, empty, o
;; 2) (cons n lon) donde n es un
;;
número y lon es una lista-de-números.

Esta definición de datos es recursiva!.

;; Contrato: sum-list:lista-de-números Æ número
;; Propósito: Esta función suma todos los números
;;

presentes en la lista de entrada.

;;Ejemplos: (sum-list (cons 1 (cons 2 (cons 3 empty))))
;;

debe producir 6

;;(sum-list (cons 3 (cons 4 (cons –5 empty))))

;;

debe producir 2

El Bosquejo

El bosquejo se convierte en un
componente crítico para el diseño. El
bosquejo permite orientar el uso de la
recursión...