martes, 12 de enero de 2010

UNIDAD 4 RECURSIVIDAD


4.1 Definicion Recursividad
4.2 Procedimientos Recursivos.
4.3 Mecanica Recursión.
4.4 Transformacion Algoritmos Recursivos a Iterativos
4.5 Recursividad en Diseño
4.6 Complejidad Algoritmos Recursivos

4.1 Definición Recursividad
Capacidad que tiene los métodos de invocarse así mismos, esta es una potente herramienta en la informática.
Con esta herramienta muchos algoritmos pueden simplificarse significativamente.


4.2 Procedimientos Recursivos.
La recursividad es una técnica de programación importante. Se utiliza para realizar una llamada a una funcion desde la misma funcion. 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 parrafo 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 es un concepto importante en informatica. Muchos algoritmos se pueden describir mejor en terminos de recursividad.

Supongamos que P es un procedimiento que contiene una sentencia de Llamada a si mismo o una sentencia de Llamada a un segundo procedimiento que puede eventualmente llamar de vuelta al procedimiento original P. Entonces P se dice que es u procedimiento recursivo. Como el progrma no ha de continuar ejecutandose indefinidamente, un procedimiento recursivo ha de tener las dos siguientes propiedades:
(1) Debe existir un cierto criterio, llamado criterio base, por el que el procedimiento no se llama asi mismo.
(2) Cada vez que el procedimiento se llame a si mismo(directa o inderectamente), debe estar mas cerca del criterio base.
Un procedimiento recursivo con estas dos propiedades se dice que esta bien definido.
Similarmente, una funcion se dice que esta definida recursivamente si la definicion de la funcion se refiere a si misma. De nuevo, para que la definicion no sea circular, debe tener las dos siguientes propiedades:
(1) Debe haber ciertos argumentos, llamados valores base, para los que la funcion no se refiera a si misma.
(2) Cada vez que la funcion se refiera a si misma, el argumento de la funcion debe acercarse mas al valor base.
Una funcion recursiva con estas dos propiedades se dice tambien que esta bien definida.
Tipos.
Podemos distinguir dos tipos de recursividad:
Directa: Cuando un subprograma se llama a si mismo una o mas veces directamente. Indirecta: Cuando se definen una serie de subprogramas usándose unos a otros.
Características.
Un algoritmo recursivo consta de una parte recursiva, otra iterativa o no recursiva y un acondición de terminación. La parte recursiva y la condición de terminación siempre existen. En cambio la parte no recursiva puede coincidir con la condición de terminación. Algo muy importante a tener en cuenta cuando usemos la recursividad es que es necesario asegurarnos que llega un momento en que no hacemos más llamadas recursivas. Si no se cumple esta condición el programa no parará nunca.
Ventajas e inconvenientes. La principal ventaja es la simplicidad de comprensión y su gran potencia, favoreciendo la resolución de problemas de manera natural, sencilla y elegante; y facilidad para comprobar y convencerse de que la solución del problema es correcta. El principal inconveniente es la ineficiencia tanto en tiempo como en memoria, dado que para permitir su uso es necesario transformar el programa recursivo en otro iterativo, que utiliza bucles y pilas para almacenar las variables.


4.3 Mecánica Recursión.

La mecánica de la recursividad está basada en una “pila”. Cuando un módulo recursivo se está ejecutando se crea en la memoria de la computadora una pila donde se almacenan los valores de los parámetros y de las variables locales del módulo. Si el módulo es función también se guarda en la pila el valor que adquiere la misma.
Para cada llamada del módulo se almacenan en la pila los nuevos valores de los parámetros y de las variables locales, creándose un nuevo “registro de activación”. De tal forma que, la pila de recursión está formada por registros de activación. Al terminar una llamada al módulo, es decir, cuando se cumple la definición base, se libera (sale) el registro de activación que se encuentra en el tope de la pila. De esta forma es como puede “recordar” qué valores tenían los parámetros y las variables locales en la llamada anterior.
Si observamos el proceso que seguimos para calcular 4! vemos que el valor de n fue cambiando conforme fuimos entrando en recursión y que al salir de recursión necesitábamos recordar el valor que tenía n en la expresión anterior. Esto quiere decir que los valores que fue adquiriendo n fueron entrando a la pila.
No sólo debe recordar los valores que tenían los parámetros y las variables locales al realizarse la correspondiente llamada al módulo sino que también tiene que recordar qué instrucción debe realizar al terminar esa llamada. De tal forma que los registros de activación están compuestos básicamente de:

1. Instrucción a la que debe regresar el control una vez terminada la ejecución actual del módulo.
2. Todos los parámetros y variables locales del módulo.
3. Si el módulo recursivo es una función el valor que adquiere la misma, ya que éste se debe regresar.
Para hacer la representación de la pila de recursión numeramos las instrucciones a las que debe regresar el control una vez terminada la ejecución del módulo recursivo y estos valores son los que ponemos en la pila.

4.4 Transformación Algoritmos Recursivos a Iterativos
El concepto de recursividad va ligado al de repetición. Son recursivos aquellos algoritmos que, estando encapsulados dentro de una función, son llamados desde ella misma una y otra vez, en contraposición a los algoritmos iterativos, que hacen uso de ciclos while, do-while, for, etc.
Algo es recursivo si se define en términos de sí mismo (cuando para definirse hace mención a sí mismo). Para que una definición recursiva sea válida, la referencia a sí misma debe ser relativamente más sencilla que el caso considerado.
Ejemplo: definición de nº natural:
→ el N º 0 es natural
→ El Nº n es natural si n-1 lo es.
En un algoritmo recursivo distinguimos como mínimo 2 partes:
a). Caso trivial, base o de fin de recursión:

Es un caso donde el problema puede resolverse sin tener que hacer uso de una nueva llamada a sí mismo. Evita la continuación indefinida de las partes recursivas.
b). Parte puramente recursiva:
Relaciona el resultado del algoritmo con resultados de casos más simples. Se hacen nuevas llamadas a la función, pero están más próximas al caso base.
4.5 Recursividad en Diseño
Un procedimiento recursivo es aquel que se llama a si mismo, para poder funcionar tiene que tener una condición de salida que de el numero de veces que se va a llamar a si mismo el procedimiento.
La recursividad en diseño se refiere a la manera de cómo representar los procedimientos recursivos al momento de diseñar los programas.
Dependiendo del método que utilicemos para diseñar la representación grafica de la recursividad va a ser diferente sin embargo el procedimiento va a ser similar ya que el fin es el mismo poner una condición que nos diga si llamamos al método o que nos mande terminarlo.
En un diagrama seria algo así:


4.6 Complejidad Algoritmos Recursivos
Un algoritmo recursivo es un algoritmo que se define en términos de sí mismo. Son implementados en forma de subprogramas (funciones, subrutinas, procedimientos, etc) de tal forma que dentro de un subprograma recursivo hay una o más llamadas a él mismo.
FUNCIÓN Factorial(n)
INICIO
SI (n<2) factorial =" 1;" factorial =" n">

Bibliografía

Consulta a libros:

Autores:·

Alfred V. Aho·

John E. Hopcroft·

Jefrey D. Ullman

Libro:

Estructura De Datos Y Algoritmos

Editorial: Addison-Wesley Iberoamericana

Edición: Revisada

REFERENCIAS DE INTERNET

http://arco.esi.uclm.es/~david.villa/pensar_en_C++/products/vol1/ch03s02s09.html

http://www.programacionfacil.com/estructura_de_datos/recursividad

http://www.programacionfacil.com/estructura_datos_csharp/procedimientos_recursivos

http://www.programacionfacil.com/estructura_datos_csharp/procedimientos_recursivos

http://cursos.itam.mx/akuri/2006/Algor%EDtmica/recur1.pdf

http://www.programacionfacil.com/estructura_datos_csharp/recursividad_en_diseno

FECHA DE CONSULTA 05 DE ENERO DEL 2010

1 comentario: