Ciencias de la Computación FAMAF

Herramientas de usuario

Herramientas del sitio

Traza: • 2016-1 • taller07_5
introalg:taller08_3

Diferencias

Muestra las diferencias entre dos versiones de la página.

Enlace a la vista de comparación

Próxima revisión		Revisión previa
introalg:taller08_3 [2008/03/18 18:22] – creado lauraintroalg:taller08_3 [2025/11/15 13:47] (actual) – editor externo 127.0.0.1
Línea 26: Línea 26:
  
 En esta función, si //n// es negativo, se corta la recursividad, y además, para cualquier valor de //n//, sabemos que en algún momento vamos a llegar a un valor negativo, ya que en cada aplicación del paso recursivo se decrementa el valor de n. En esta función, si //n// es negativo, se corta la recursividad, y además, para cualquier valor de //n//, sabemos que en algún momento vamos a llegar a un valor negativo, ya que en cada aplicación del paso recursivo se decrementa el valor de n.
 +
 +Entonces, los programas recursivos tienen que cumplir dos requisitos: 
 +  - tratar un número indeterminado de elementos (como en la inducción matemática)
 +  - terminar en algún momento (a diferencia de la inducción matemática)
 +
 +Para garantizar que se cumplen estos dos requisitos, los programas o funciones recursivos tienen que tener las siguientes tres propiedades:
 +  - la función se llama a sí misma por lo menos en uno de los casos de su definición (caso(s) recursivo o inductivo),
 +  - la función NO se llama a sí misma por lo menos en uno de los casos de su definición (caso(s) base), y
 +  - la condición de aplicación del caso recursivo se modifica cada vez que se aplica éste, de forma que eventualmente no se cumple más la condición y se llega al caso base.
 +
 +El primer requisito garantiza que la función puede tratar un número indeterminado de elementos, mientras que los dos siguientes requisitos garantizan que la función va a terminar en algún momento.
  
  
Línea 113: Línea 124:
 Veamos ahora otro ejemplo, con la función //duplicar.xs//, //duplicar :: [Int] -> [Int]// que dada una lista multiplica por 2 cada uno de sus elementos (ej.: //duplicar [2,4,8] = [4,8,16]//).  Veamos ahora otro ejemplo, con la función //duplicar.xs//, //duplicar :: [Int] -> [Int]// que dada una lista multiplica por 2 cada uno de sus elementos (ej.: //duplicar [2,4,8] = [4,8,16]//). 
  
-Veamos varias formas en que la función estaría **MAL** definida:+Recordemos los requisitos básicos de las funciones recursivas: 
 +  - la función se llama a sí misma por lo menos en uno de los casos de su definición (caso(s) recursivo o inductivo), 
 +  - la función NO se llama a sí misma por lo menos en uno de los casos de su definición (caso(s) base), y 
 +  - la condición de aplicación del caso recursivo se modifica cada vez que se aplica éste, de forma que eventualmente no se cumple más la condición y se llega al caso base. 
 + 
 +Veamos varias formas en que la función estaría **MAL** definida, porque se incumplen alguno de los requisitos anteriores:
  
 <code> <code>
Línea 132: Línea 148:
   [20,20,30]   [20,20,30]
  
-En este caso, la función **no se llama a sí misma**, así que sólo se aplicaría a la cabeza de la lista, y no a todo el resto. +En este caso, la función **no se llama a sí misma**, así que sólo se aplicaría a la cabeza de la lista, y no a todo el resto. Por lo tanto, incumple el requisito número 1. Corregimos este error.
-Corregimos este error.+
  
 <code> <code>
Línea 148: Línea 163:
   [20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20 ...   [20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20 ...
  
-En este caso, el caso recursivo no modifica su condición de aplicación, así que nunca va a llegar al caso base y por lo tanto caerá en un bucle infinito.+En este caso, el caso recursivo no modifica su condición de aplicación, así que nunca va a llegar al caso base y por lo tanto caerá en un bucle infinito. En este caso se está incumpliendo el requisito número 3, que requiere que la condición de aplicación del caso recursivo se modifique cada vez que se aplica éste, de forma que eventualmente no se cumple más la condición y se llega al caso base. En este caso, la lista no se modifica, no se achica, no se consume su cabeza en cada ocasión, y por eso nunca se llega a una lista vacía, que es la condición de aplicación del caso base.
  
 La función //duplicar.xs// estaría bien definida de la siguiente forma: La función //duplicar.xs// estaría bien definida de la siguiente forma:
introalg/taller08_3.1205875358.txt.gz · Última modificación: (editor externo)