trabajo desarrollo 3 RECURSIVIDAD - liz rodriguez

Vista previa del material en texto

MINISTERIO DEL PODER POPULAR PARA LA EDUCACIÓN UNIVERSITARIA
AROA – MUN. BOLÍVAR- YARACUY
Aroa, 04 de Julio de 2012.
MINISTERIO DEL PODER POPULAR PARA LA EDUCACIÓN UNIVERSITARIA
AROA – MUN. BOLÍVAR- YARACUY
Introducción
El concepto de recursión aparece en varias situaciones de la vida cotidiana, aunque en muchas no sabemos que estamos en presencia de él, por ejemplo, sacar fotocopias de fotocopias o tomar una fotografía a otra fotografía.
Se trata de un concepto muy amplio, por ejemplo, se encuentra reflejado cuando se leen relatos que describen relatos (“La Historia Interminable”, “Las Mil y Una Noches”), cuando se ven películas que hacen referencia a otras películas (“La Rosa Purpura del Cairo”, “La Mujer del Teniente Francés”, “La Noche Americana”), jugando con las muñecas rusas en cuyo interior hay otras muñecas o, cuando se realizan comentarios entre paréntesis , dentro de otros comentarios entre paréntesis. Es muy habitual en la literatura y en los juegos matemáticos que la recursividad se aproxime mucho a una paradoja.
Es un método poderoso usado en inteligencia artificial, su poder es que algunos conceptos complejos pueden expresarse en una forma simple.
Las fórmulas recursivas pueden aplicarse a situaciones tales como prueba de teoremas, solución de problemas combinatorios, algunos acertijos, etc.
La recursión como herramienta de programación permite definir un objeto por ejemplo: una estructura de datos -en términos de sí mismo. Un caso concreto de recursión son las listas circulares, en donde una lista se llama a sí misma.
Un ejemplo clásico en matemática es el factorial de un número, potencia o la serie de Fibonacci.
Recursividad
La recursividad es una técnica de programación importante. Se utiliza para realizar una llamada a una función desde la misma función. Como ejemplo útil se puede presentar el cálculo de números factoriales. Él factorial de 0 es, por definición, 1. Los factoriales de números mayores se calculan mediante la multiplicación de 1 * 2 *…. incrementando el número de 1 en 1 hasta llegar al número para el que se está calculando el factorial. 
El siguiente párrafo muestra una función, expresada con palabras, que calcula un factorial:
“Si el número es menor que cero, se rechaza. Si no es un entero, se redondea al siguiente entero. Si el número es cero, su factorial es uno. Si el número es mayor que cero, se multiplica por él factorial del número menor inmediato.” 
Para calcular el factorial de cualquier número mayor que cero hay que calcular como mínimo el factorial de otro número. La función que se utiliza es la función en la que se encuentra en estos momentos, esta función debe llamarse a sí misma para el número menor inmediato, para poder ejecutarse en el número actual. Esto es un ejemplo de recursividad. 
La recursividad y la iteración (ejecución en bucle) están muy relacionadas, cualquier acción que pueda realizarse con la recursividad puede realizarse con iteración y viceversa. Normalmente, un cálculo determinado se prestará a una técnica u otra, sólo necesita elegir el enfoque más natural o con el que se sienta más cómodo. 
Claramente, esta técnica puede constituir un modo de meterse en problemas. Es fácil crear una función recursiva que no llegue a devolver nunca un resultado definitivo y no pueda llegar a un punto de finalización. Este tipo de recursividad hace que el sistema ejecute lo que se conoce como bucle “infinito”. 
Para entender mejor lo que en realidad es el concepto de recursión veamos un poco lo referente a la función Fibonacci. 
 1 x ≤ 2
Fib (x) = 
 fib(x − 2) + fib(x − 2) x > 2
 
La función de Fibonacci proviene del bucólico problema de la multiplicación de conejos. Supongamos que partimos de una pareja de conejos recién nacidos, y queremos calcular cuantas parejas de conejos forman la familia al cabo de n meses si:
· Los conejos nunca mueren.
· Un conejo puede reproducirse al comienzo del tercer mes de vida.
· Los conejos siempre nacen en parejas macho-hembra. Al comienzo de cada mes, cada pareja macho-hembra, sexualmente madura, se reproduce en exactamente un par de conejos macho-hembra.
Para un n pequeño, por ejemplo 6, la solución se puede obtener fácilmente a mano:
Mes 1: 1 pareja, la inicial
Mes 2: 1 pareja, ya que todavía no es sexualmente madura.
Mes 3: 2 parejas; la original y una pareja de hijos suyos.
Mes 4: 3 parejas; la original, una pareja de hijos suyos nacidos ahora y la pareja de hijos suyos nacidos en el mes anterior.
Mes 5: 5 parejas; la original, una pareja de hijos suyos nacidos ahora, las dos parejas nacidas en los meses 3 y 4, y una pareja de hijos de la pareja nacida en el mes 3.
Mes 6: 8 parejas; las 5 del mes anterior, una pareja de hijos de la original, una pareja de hijos de la nacida en el mes 3 y una pareja de hijos nacida en el mes 4.
Si deseamos saber el número de parejas al cabo de n meses, para un n cualquiera, podemos construir un algoritmo recursivo fácilmente a partir de la siguiente relación:
 1 n ≤ 2
 Parejas (n) = 
 Parejas(n − 1) + Parejas(n − 2) n > 2
En esta relación Parejas(n − 1) son las parejas vivas en el mes n − 1, y Parejas(n − 2) son las parejas que nacen en el mes n a partir de las que había en el mes n − 2.
La serie de números Parejas (1), Parejas (2), Parejas(3),. . . es conocida como la Serie de Fibonacci, la cual modela muchos fenómenos naturales. El crecimiento de esta función, como demuestra la su aproximación:
 (
2
)y (k) ≈ 1/√5( 1+√5 )k , es exponencial. Los valores de yk coinciden (en su 
 
parte entera redondeada desde k = 1 con los de f(k)).
1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1.597, 2.584, 4.181, 6.765, 10.946, 17.711, 28.657, 46.368, 75.025, 121.393, 196.418, 317.811, 514.229, 832.040, 11346,269 . . . son solo los valores alcanzado hasta el termino 30.
En forma de algoritmo recursivo la función de Fibonacci sería:
1 int fib(int n) {
2 if (n<=2)
3 return 1;
4 else
5 return fib(n-1)+fib(n-2);
6 }
Recursión versus Iteración
Tanto la iteración como la recursión se basan en estructura de control: la iteración utiliza una estructura repetitiva y la recursión una estructura de selección. La iteración utiliza explícitamente una estructura repetitiva mientras que la recursión consigue la repetición mediante llamadas repetitivas a funciones.
La iteración termina si la condición del bucle no se cumple, mientras que la recursión termina cuando se reconoce un caso base.
La recursión puede presentar desventajas ante la iteración ya que se invoca repetidas veces al mecanismo de llamada de funciones y se necesita un tiempo mayor para realizar cada llamada.
La razón por la cual se puede elegir u optar por usar recursividad es que existen muchos problemas complejos que poseen naturaleza recursiva y, en consecuencia, son más fáciles de implementar.
Ejemplo Iterativo
/*
 * iterativo.c
 *
 * Julio César Brizuela <brizuelaalvarado@gmail.com> 2009
 *
 * para el wikilibro "Programación en C"
 * bajo licencia FDL, adaptado del Dominio Público
 */
 #include <stdio.h>
 
long factorial(int numero);
 int main(int argc, char** argv)
{
 int contador = 0;
 /* calcula el factorial de 0 a 10 */
 for ( contador = 0; contador <= 10; contador++ )
 printf("%d! = %ld\n", contador, factorial( contador ));
 return 0;
}
 /* funcion factorial iterativa */
long factorial( int numero )
{
 long resultado = 1;
 int i = 0;
 
 /* declaracion de la función factorial iterativa */
 for ( i = numero; i >= 1; i-- )
 resultado *= i;
 
 return resultado;
}
Ejemplo Recursivo
/*
 * recursivo.c
 *
 * Julio César Brizuela<brizuelaalvarado@gmail.com> 2009
 *
 * para el wikilibro "Programación en C"
 * bajo licencia FDL, adaptado del Dominio Público
 */
 #include <stdio.h>
long factorial(int numero);
int main(int argc, char** argv)
{
 int contador = 0;
 /* calcula el factorial de 0 a 10 */
 for ( contador = 0; contador <= 10; contador++ )
 printf("%d! = %ld\n", contador, factorial( contador ));
 return 0;
}
/* función factorial recursiva */
long factorial( int numero )
{ 
 if ( numero <= 0 ) /* caso base */
 return 1; /* casos bases: 0! = 1 y 1! = 1 */
 else /* llamada recursiva */
 return numero * factorial( numero - 1 ); /* llamada a la función factorial */
}
Utilidades
La Recursividad es un método poderoso usado en inteligencia artificial. De igual manera las fórmulas recursivas pueden aplicarse a situaciones tales como prueba de teoremas, solución de problemas combinatorios, algunos acertijos y como herramienta de programación permite definir un objeto por ejemplo: una estructura de datos -en términos de sí mismo.
El empleo de algoritmos recursivos tiene asociado un mayor empleo de memoria (uso de la pila) y un mayor tiempo de ejecución (tiempo que se emplea en apilar/desapilar) que sus equivalentes soluciones algorítmicas no recursivas.
Otra cuestión a tener en cuenta es que, al igual que en los algoritmos no recursivos, hay distintas descripciones recursivas para solucionar un mismo problema. Cada uno de estos algoritmos realizara mayor o menor numero de operaciones si se comparan entre si. En el caso de los algoritmos recursivos, hay que ser especialmente cuidadoso con esto, puesto que fácilmente se pueden obtener algoritmos con un gran número de llamadas, que se traduzcan en programas muy lentos.
 A la vista de las definiciones y ejemplos expuestos, puede parecer que el estudio de la recursividad en Algorítmica no tiene más que un interés anecdótico. Pero eso realmente no es así. Es cierto que en el empleo de la recursividad hay que tener un especial cuidado para que no se solucionen muchas veces los mismos subproblemas, y también es cierto que, en general, los algoritmos recursivos son algo más lentos en ejecución que sus equivalentes versiones no recursivas. No obstante, el empleo de la recursividad para exponer soluciones algorítmicas presenta muchas ventajas:
Expresividad es decir, para muchos problemas la descripción recursiva suele ser mas elegante y sencilla de escribir (lo que mejora la legibilidad), mientras que su descripción no recursiva puede resultar mas difícil de realizar.
Facilidad de Análisis ya que permite el uso de formulas de recurrencias para analizar el coste en operaciones de los algoritmos.
Corrección ya que la definición recursiva de un algoritmo permite utilizar el mecanismo de inducción matemática para demostrar su corrección formal.
De hecho, estas tres ventajas han convertido a la recursividad en una gran herramienta de programación: el uso de la recursividad es frecuente en la descripción léxica y sintáctica de los lenguajes de programación (C, Python, Pascal, etc.), en el funcionamiento de las estructuras de control de otros lenguajes de programación orientados a la denominada Inteligencia Artificial (Lisp o Prolog). Además, muchas estructuras de datos se definen de forma muy simple recursivamente, como ocurre en el caso de las listas, colas, árboles.
Otro ejemplo típico de uso extensivo de la recursividad es el fijar algunos esquemas de programación para determinado tipo de problemas, como son los esquemas de ramificación y poda (branch & bound), divide y vencerás (divide & conquer) o vuelta atrás (backtracking).
Esto puede provocar un conflicto a la hora de solucionar un problema, en cuanto a decidirnos entre solucionarlo mediante un algoritmo recursivo, con sus ventajas formales (legibilidad, análisis del coste y corrección), o mediante un algoritmo iterativo, con sus ventajas prácticas (velocidad de ejecución). La decisión a adoptar depende de cada caso. Pero las ventajas que aporta son tantas
que muchos programadores han tratado de desarrollar soluciones iterativas a ciertas “elegantes” versiones recursivas. Fruto de este estudio se han desarrollado distintos métodos para poder convertir un algoritmo recursivo en iterativo sin perder la expresividad de la versión recursiva. Estos métodos, denominados transformaciones recursivo-iterativas, se apoyan en la estructura de control iterativa (while) y se suelen basar en la “simulación” de las llamadas recursivas, almacenando de forma iterativa tanto los parámetros como las variables intermedias en una pila, para que, posteriormente, una vez que se llega a la condición de salida del bucle (que coincidirá con la condición de parada recursiva), se puedan ir recuperando los datos almacenados.
Ordenamiento Rápido (Quicksort)
Esta es probablemente la técnica más rápida conocida. Fue desarrollada por C.A.R. Hoare en 1960. El algoritmo original es recursivo, pero se utilizan versiones iterativas para mejorar su rendimiento (los algoritmos recursivos son en general más lentos que los iterativos, y consumen más recursos). El algoritmo fundamental es el siguiente: 
· Eliges un elemento de la lista. Puede ser cualquiera. Lo llamaremos elemento de división. 
· Buscas la posición que le corresponde en la lista ordenada.
· Acomodas los elementos de la lista a cada lado del elemento de división, de manera que a un lado queden todos los menores que él y al otro los mayores. En este momento el elemento de división separa la lista en dos sublistas (de ahí su nombre). 
· Realizas esto de forma recursiva para cada sublista mientras éstas tengan un largo mayor que 1. Una vez terminado este proceso todos los elementos estarán ordenados. 
Una idea preliminar para ubicar el elemento de división en su posición final sería contar la cantidad de elementos menores y colocarlo un lugar más arriba. Pero luego habría que mover todos estos elementos a la izquierda del elemento, para que se cumpla la condición y pueda aplicarse la recursividad. Reflexionando un poco más se obtiene un procedimiento mucho más efectivo. Se utilizan dos índices: i, al que llamaremos contador por la izquierda, y j, al que llamaremos contador por la derecha. El algoritmo es éste: 
· Recorres la lista simultáneamente con i y j: por la izquierda con i (desde el primer elemento), y por la derecha con j (desde el último elemento). 
· Cuando lista[i] sea mayor que el elemento de división y lista[j] sea menor los intercambias. 
· Repites esto hasta que se crucen los índices. 
· El punto en que se cruzan los índices es la posición adecuada para colocar el elemento de división, porque sabemos que a un lado los elementos son todos menores y al otro son todos mayores (o habrían sido intercambiados). 
Al finalizar este procedimiento el elemento de división queda en una posición en que todos los elementos a su izquierda son menores que él, y los que están a su derecha son mayores. 
Pseudocódigo en C.
	Tabla de variables
	Nombre
	Tipo
	Uso
	lista
	Cualquiera
	Lista a ordenar
	inf
	Entero
	Elemento inferior de la lista
	sup
	Entero
	Elemento superior de la lista
	elem_div
	El mismo que los elementos de la lista
	El elemento divisor
	temp
	El mismo que los elementos de la lista
	Para realizar los intercambios
	i
	Entero
	Contador por la izquierda
	j
	Entero
	Contador por la derecha
	cont
	Entero
	El ciclo continua mientras cont tenga el valor 1
 
 Nombre Procedimiento: OrdRap
 Parámetros: 
 lista a ordenar (lista) 
 índice inferior (inf) 
 índice superior (sup)
 
 
 // Inicialización de variables
 1. elem_div = lista[sup];
 2. i = inf - 1;
 3. j = sup;
 4. cont = 1;
 
 // Verificamos que no se crucen los límites
 5. if (inf >= sup)
 6. retornar;
 
 // Clasificamos la sublista
 7. while (cont)
 8. while (lista[++i] < elem_div);
 9. while (lista[--j]> elem_div);
 10. if (i < j)
 11. temp = lista[i];
 12. lista[i] = lista[j];
 13. lista[j] = temp;
 14. else
 15. cont = 0;
 
 // Copiamos el elemento de división
 // en su posición final
 16. temp = lista[i];
 17. lista[i] = lista[sup];
 18. lista[sup] = temp;
 
 // Aplicamos el procedimiento
 // recursivamente a cada sublista
 19. OrdRap (lista, inf, i - 1);
 20. OrdRap (lista, i + 1, sup);
 
Nota: La primera llamada debería ser con la lista, cero (0) y el tamaño de la lista menos 1 como parámetros. 
3. Un ejemplo
Esta vez voy a cambiar de lista ;-D 
5 - 3 - 7 - 6 - 2 - 1 - 4 
Comenzamos con la lista completa. El elemento divisor será el 4: 
5 - 3 - 7 - 6 - 2 - 1 - 4 
Comparamos con el 5 por la izquierda y el 1 por la derecha. 
5 - 3 - 7 - 6 - 2 - 1 - 4 
5 es mayor que cuatro y 1 es menor. Intercambiamos: 
1 - 3 - 7 - 6 - 2 - 5 - 4 
Avanzamos por la izquierda y la derecha: 
1 - 3 - 7 - 6 - 2 - 5 - 4 
3 es menor que 4: avanzamos por la izquierda. 2 es menor que 4: nos mantenemos ahí. 
1 - 3 - 7 - 6 - 2 - 5 - 4 
7 es mayor que 4 y 2 es menor: intercambiamos. 
1 - 3 - 2 - 6 - 7 - 5 - 4 
Avanzamos por ambos lados: 
1 - 3 - 2 - 6 - 7 - 5 - 4 
En este momento termina el ciclo principal, porque los índices se cruzaron. Ahora intercambiamos lista[i] con lista[sup] (pasos 16-18): 
1 - 3 - 2 - 4 - 7 - 5 - 6 
Aplicamos recursivamente a la sublista de la izquierda (índices 0 - 2). Tenemos lo siguiente: 
1 - 3 - 2 
1 es menor que 2: avanzamos por la izquierda. 3 es mayor: avanzamos por la derecha. Como se intercambiaron los índices termina el ciclo. Se intercambia lista[i] con lista[sup]: 
1 - 2 - 3 
Al llamar recursivamente para cada nueva sublista (lista[0]-lista[0] y lista[2]-lista[2]) se retorna sin hacer cambios (condición 5.).Para resumir te muestro cómo va quedando la lista: 
Segunda sublista: lista[4]-lista[6] 
7 - 5 - 6 
5 - 7 - 6 
5 - 6 - 7 
Para cada nueva sublista se retorna sin hacer cambios (se cruzan los índices). 
Finalmente, al retornar de la primera llamada se tiene el arreglo ordenado: 
1 - 2 - 3 - 4 - 5 - 6 - 7 
Optimizando
Estas son algunas optimizaciones que pueden mejorar bastante el rendimiento de quicksort: 
· Hacer una versión iterativa: Para ello se utiliza una pila en que se van guardando los límites superior e inferior de cada sublista. 
· No clasificar todas las sublistas: Cuando el largo de las sublistas va disminuyendo, el proceso se va encareciendo. Para solucionarlo sólo se clasifican las listas que tengan un largo menor que n. Al terminar la clasificación se llama a otro algoritmo de ordenamiento que termine la labor. El indicado es uno que se comporte bien con listas casi ordenadas, como el ordenamiento por inserción por ejemplo. La elección de n depende de varios factores, pero un valor entre 10 y 25 es adecuado. 
· Elección del elemento de división: Se elige desde un conjunto de tres elementos: lista[inferior], lista[mitad] y lista[superior]. El elemento elegido es el que tenga el valor medio según el criterio de comparación. Esto evita el comportamiento degenerado cuando la lista está prácticamente ordenada. 
Análisis del algoritmo
· Estabilidad: No es estable. 
· Requerimientos de Memoria: No requiere memoria adicional en su forma recursiva. En su forma iterativa la necesita para la pila. 
· Tiempo de Ejecución: 
· Caso promedio. La complejidad para dividir una lista de n es O(n). Cada sublista genera en promedio dos sublistas más de largo n/2. Por lo tanto la complejidad se define en forma recurrente como: 
f(1) = 1 
f(n) = n + 2 f(n/2) 
La forma cerrada de esta expresión es: 
f(n) = n log2n 
Es decir, la complejidad es O(n log2n). 
· El peor caso ocurre cuando la lista ya está ordenada, porque cada llamada genera sólo una sublista (todos los elementos son menores que el elemento de división). En este caso el rendimiento se degrada a O(n2). Con las optimizaciones mencionadas arriba puede evitarse este comportamiento. 
Ventajas: 
· Muy rápido 
· No requiere memoria adicional. 
Desventajas: 
· Implementación un poco más complicada. 
· Recursividad (utiliza muchos recursos). 
· Mucha diferencia entre el peor y el mejor caso. 
La mayoría de los problemas de rendimiento se pueden solucionar con las optimizaciones mencionadas arriba (al costo de complicar mucho más la implementación). Este es un algoritmo que se puede utilizar en la vida real. Es muy eficiente. 
Búsqueda Binaria Recursiva
La búsqueda binaria puede ser también fácilmente implementada de modo recursivo. Si el vector está ordenado en orden ascendente, el algoritmo es el siguiente:
1) Si buscamos un elemento en un vector de tamaño cero podemos concluir que el elemento no está en éste.
2) Si el elemento que ocupa la posición central del vector coincide con el buscado, lo hemos encontrado en la posición central.
3) Si el elemento buscado es menor que el que ocupa la posición central del vector, buscar en la mitad izquierda del segmento.
4) En otro caso, buscar en la mitad derecha del segmento.
El siguiente subprograma implementa esta búsqueda recursiva:
PROCEDURE BuscarBinaria ( A : ARRAY OF ELEMENTO;
Elemento : ELEMENTO ) : INTEGER;
PROCEDURE BuscarEn (A : ARRAY OF ELEMENTO;
Elemento : ELEMENTO;
Primero, Ultimo : CARDINAL ) : INTEGER;
CONST
NOENCONTRADO = -1;
VAR
Central : CARDINAL;
BEGIN
IF Primero > Ultimo THEN
RETURN NOENCONTRADO
ELSE
Central := (Primero + Ultimo)D IV 2;
IF A[Central] = Elemento THEN
RETURN Central
ELSIF A[Central] > Elemento THEN
RETURN BuscarEn(A, Elemento, Primero, Central-1)
ELSE
RETURN BuscarEn(A, Elemento, Central+1, Ultimo)
END
END
END BuscarEn;
BEGIN
RETURN BuscarEn(A, Elemento, 0, HIGH(A))
END BuscarLineal;
En este caso, el tamaño del segmento donde realizar la búsqueda queda reducido a la mitad en cada llamada recursiva. Las mismas consideraciones de eficiencia estudiadas para la búsqueda lineal recursiva son aplicables a este algoritmo.
CONCLUSIÒN
	La Recursividad es una Técnica de programación importante, que tiene su origen en ciertos cálculos matemáticos, consiste en describir los cálculos o acciones de una manera auto alusiva, es decir, resolver problemas describiéndoles en términos de ejemplares más sencillos de sí mismos. 
La técnica de Recursividad presenta ventajas y desventajas: entre las primeras es que ofrece soluciones claras a problemas complejos y en desventaja es que puede ser ineficiente, debe seleccionarse cuando realmente sea necesaria su aplicación.
Cuando trabajamos con la Recursividad debemos igualmente comprender el concepto ordenamiento rápido (quicksort en inglés) es un algoritmo basado en la técnica de divide y vencerás, que permite, en promedio, ordenar n elementos en un tiempo proporcional a n log n. El algoritmo original es recursivo, pero se utilizan versiones iterativas para mejorar su rendimiento (los algoritmos recursivos son en general más lentos que los iterativos, y consumen más recursos). 
De igual manera en cuanto al algoritmo de búsqueda binaria es un método de búsqueda de un dato en un vector de datos ordenado dividiendo el vector en dos tras cada pasada. Se usa recursión en este algoritmo porque tras cada pasada se crea un nuevo vector dividiendo en original en dos. La subrutina de búsqueda binaria se llama entonces de forma recursiva, cada vez con un vector de menor tamaño. El tamaño del vector se ajusta normalmente cambiando el índice inicial y final. 
BIBLIOGRAFÍA
Páginas electrónicas consultadas:
· http://www.lcc.uma.es/ 
· http://es.wikipedia.org/ 
· http://www.geocities.com/ 
· http://c.conclase.net/