Recursividad
La recursividad es una técnica de programación elemental que permite que una función pueda llamarse asimismo desde la misma función. Se puede utilizar la recursividad como una alternativa a la iteración. La recursividad es una herramienta poderosa e importante en la resolución de problemas en programación.
Una solución recursiva es normalmente menos eficiente en términos de tiempo de computadora que una solución iterativa debido a las operaciones auxiliares que llevan consigo las llamadas suplementarias a las funciones: sin embargo, en muchas circunstancias el uso de la recursión permite a los programadores especificar las soluciones naturales, más lógicas, elegantes, sencillas, que serían, en caso contrario difícil de resolver.
Cada vez que se llama a una función, se crea un juego de variables locales, de este modo, si la función hace una llamada a sí misma, se guardan sus variables y parámetros, usando la pila, y la nueva instancia de la función trabajará con su propia copia de las variables locales. Cuando esta segunda instancia de la función retorna, recupera las variables y los parámetros de la pila y continúa la ejecución en el punto en que había sido llamada.
Por ejemplo 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.
Características
Generalmente, si la primera llamada al subprograma se plantea sobre un problema de tamaño u orden N, cada nueva ejecución recurrente del mismo se planteará sobre problemas, de igual naturaleza que el original, pero de un tamaño menor que N. De esta forma, al ir reduciendo progresivamente la complejidad del problema a resolver, llegará un momento en que su resolución sea más o menos trivial (o, al menos, suficientemente manejable como para resolverlo de forma no recursiva). En esa situación diremos que estamos ante un caso base de la recursividad.
Es frecuente que los algoritmos recurrentes sean más ineficientes en tiempo que los iterativos aunque suelen ser mucho más breves en espacio.
Ø No debe generar una secuencia infinita de llamadas así mismo, dicho de otro modo ha de existir al menos un caso base.
Ø Una función recursiva f debe definirse en términos que no impliquen a f al menos en un argumento o grupo de argumentos.
Ø Debe existir una "salida" de la secuencia de llamadas recursivas.
Ø Cada llamada recurrente se debería definir sobre un problema de menor complejidad (algo más fácil de resolver).
Tipos de Recursividad
Recursividad Simple: Aquella en cuya definición sólo aparece una llamada recursiva. Se puede transformar con facilidad en algoritmos iterativos. Recursividad Múltiple: Se da cuando hay más de una llamada a sí misma dentro del cuerpo de la función, resultando más difícil de hacer de forma iterativa.
Recursividad Anidada: En algunos de los argumentos de la llamada recursiva hay una nueva llamada a sí misma.
Recursividad cruzada o indirecta: Son algoritmos donde una función provoca una llamada a sí misma de forma indirecta, a través de otras funciones.
Aplicación
Se utiliza para realizar una llamada a una función desde la misma función. Hemos visto que la recursión es una técnica potente de programación para resolver, mediante soluciones simples y claras, problemas de gran complejidad.
Ejemplos de Implementación
La mayoría de los problemas pueden resolverse de una manera directa usando métodos no recursivos. Sin embargo, otros pueden resolverse de una manera más lógica y elegante mediante la recursión.
Volviendo a examinar la función factorial. El factor es, probablemente, un ejemplo fundamental de un problema que no debe resolverse de manera recursiva, dado que su solución iterativa es directa y simple. Sin embargo, examinaremos los elementos que permiten dar una solución recursiva. Antes que nada, puede reconocerse un gran número de casos distintos que se deben resolver. Es decir, quiere escribirse un programa para calcular 0!, 1!, 2! Y así sucesivamente. Puede identificarse un caso "trivial" para el cual la solución no recursiva pueda obtenerse en forma directa. Es el caso de 0!, que se define como 1. El siguiente paso es encontrar un método para resolver un caso "complejo" en términos de uno más "simple", lo cual permite la reducción de un problema complejo a uno más simple. La transformación del caso complejo al simple resultaría al final en el caso trivial. Esto significaría que el caso complejo se define, en lo fundamental, en términos del más simple.
Ejemplo de la sucesión de Fibonacci
En matemáticas, la sucesión de Fibonacci es la siguiente sucesión infinita de números naturales:
0,1,1,2,3,5,8,13,21,34,55,89,144...
El primer elemento es 0, el segundo es 1 y cada elemento restante es la suma de los dos anteriores:
A cada elemento de esta sucesión se le llama número de Fibonacci. Esta sucesión fue descrita en Europa por Leonardo de Pisa, matemático italiano del siglo XIII también conocido como Fibonacci.
El código en C++ que representa la función Fibonacci es el siguiente:
#include <iostream>
#include <cstdlib>
using namespace std;
int Fibonacci(int n);
int main(){
int valor;
system("clear");
cout << "Introduzca número a calcular: ";
cin >> valor;
cout << "\n El Fibonacci de " << valor << " es: " << Fibonacci(valor) << endl;
return 0;
}
int Fibonacci(int n){
if (n < 0){
cout << “No existe Fibonacci para numeros negativos.”;
} else if (n == 0) {
return 0;
} else if (n == 1) {
return 1;
}else
return Fibonacci(n-2) + Fibonacci(n -1);
}
Ejemplo de las Torres de Hanoi
Hay tres postes: A, B y C. En el poste A se ponen cinco discos de diámetro diferente de tal manera que un disco de diámetro mayor siempre queda debajo de uno de diámetro menor. El objetivo es mover los discos al poste C usando B como auxiliar. Sólo puede moverse el disco superior de cualquier poste a otro poste, y un disco mayor jamás puede quedar sobre uno menor. Considérese la posibilidad de encontrar una solución. En efecto, ni siquiera es claro que exista una.
Ahora se verá si se puede desarrollar una solución. En lugar de concentrar la atención en una solución para cinco discos, considérese el caso general de n discos. Supóngase que se tiene una solución para n – 1 discos y que en términos de ésta, se pueda plantear la solución para n – 1 discos.
El problema se resolvería entonces. Esto sucede porque en el caso trivial de un disco (al restar 1 de n de manera sucesiva se producirá, al final, 1) la solución es simple: sólo hay que mover el único disco del poste A a C. Así se habrá desarrollado una solución recursiva si se plantea una solución para n discos en términos de n – 1. Considérese la posibilidad de encontrar tal relación. Para el caso de cinco discos en particular, supóngase que se conoce la forma de mover cuatro de ellos del poste A al otro, de acuerdo con las reglas. ¿Cómo puede completarse entonces el trabajo de mover el quinto disco? Cabe recordar que hay 3 postes disponibles.
Supóngase que se supo cómo mover cuatro discos del poste A al C. Entonces, se pondrá mover éstos exactamente igual hacia B usando el C como auxiliar. Esto da como resultado la situación los cuatro primeros discos en el poste B, el mayor en A y en C ninguno. Entonces podrá moverse el disco mayor de A a C y por último aplicarse de nuevo la solución recursiva para cuatro discos para moverlo de B a C, usando el poste A como auxilia. Por lo tanto, se puede establecer una solución recursiva de las torres de Hanoi como sigue:
Para mover n discos de A a C usando B como auxiliar:
1. Si n = = 1, mover el disco único de A a C y parar.
2. Mover el disco superior de A a B n – 1 veces, usando C como auxiliar.
3. Mover el disco restante de A a C.
4. Mover los discos n – 1 de B a C usando A como auxiliar
Con toda seguridad este algoritmo producirá una solución completa por cualquier valor de n. Si n = = 1, el paso 1 será la solución correcta. Si n = = 2, se sabe entonces que hay una solución para n – 1 = = 1, de manera tal que los pasos 2 y 4 se ejecutaran en forma correcta. De manera análoga, cuando n = = 3 ya se habrá producido una solución para n – 1 = = 2, por lo que los pasos 2 y 4 pueden ser ejecutados. De esta forma se puede mostrar que la solución funciona para n = = 1, 2, 3, 4, 5,... hasta el valor para el que se desee encontrar una solución. Adviértase que la solución se desarrolló mediante la identificación de un caso trivial (n = = 1) y una solución para el caso general y complejo (n) en términos de un caso más simple (n – 1).
Ya se demostró que las transformaciones sucesivas de una simulación no recursiva de una rutina recursiva pueden conducir a un programa más simple para resolver un problema. Ahora se simulará la recursión del problema y se intentará simplificar la simulación no recursiva.
#include <iostream>
#include <cstdlib>
using namespace std;
int hanoi(int n, char origen, char destino, char auxiliar);
int main() {
int valor;
system("clear");
cout << "Introduzca numero a calcular: ";
cin >> valor;
hanoi(valor,'A','B','C');
return 0;
}
int hanoi(int n, char origen, char destino, char auxiliar){
if (n <= 1) {
cout << "\nmover disco 1 del poste "<< origen << " al poste " << destino << endl;
} else {
hanoi(n-1, origen, auxiliar, destino);
cout << "\nmover disco " << n << " del poste " << origen << " al poste "<< destino;
hanoi (n-1, auxiliar, destino, origen);
}
}
Pilas, colas y listas
Pilas
Una pila es una estructura de datos en la cual los elementos almacenados en la misma se agregan y se sacan del mismo lugar, llamado el tope de la pila. El tope es el único lugar a partir del cual se pueden acceder a los elementos de la estructura. Esta característica hace que el último elemento en ser insertado en la pila es el primero en salir. Este tipo de estructuras se denominan LIFO (Last In First Out).
Primitivas
Para utilizar el Tipo de Dato Abstracto (TDA) Pila, el mismo nos proveerá de una serie de procedimientos que nos permitirán acceder o agregar elementos. Los siguientes son los procedimientos básicos que debe contener una pila:
v P_Crear
v P_Vaciar
v P_Vacia
v P_Agregar
v P_Sacar
Los tipos que definiremos normalmente para manejar pilas serán casi los mismos que para manejar listas, tan sólo cambiaremos algunos nombres:
Es evidente, a la vista del gráfico, que una pila es una lista abierta. Así que sigue siendo muy importante que nuestro programa nunca pierda el valor del puntero al primer elemento, igual que pasa con las listas abiertas.
Teniendo en cuenta que las inserciones y borrados en una pila se hacen siempre en un extremo, lo que consideramos como el primer elemento de la lista es en realidad el último elemento de la pila.
Implementación
Para la implementación de la pila, es necesario que el tipo de dato contenga una referencia al nodo tope de la pila. Luego, cada nodo tendrá una referencia al nodo que le siguiente. De esta manera se formara una cadena con inicio en el nodo tope y que finaliza en el último elemento de la pila, cuyo nodo no referenciará a ningún elemento.
Implementación de pilas
Supongamos que queremos construir una pila para almacenar números enteros. Haremos pruebas intercalando varios "push" y "pop", y comprobando el resultado.
Algoritmo de la función push (o apilar)
Creamos un nodo para el valor que colocaremos en la pila.
Hacemos que nodo->siguiente apunte a Pila.
Hacemos que Pila apunte a nodo.
Operaciones
Operaciones de las Pilas Las operaciones que se pueden realizar con una pila son:
• PUSH (pila, elemento): Introduce un elemento en la pila. También se le conoce como poner o meter.
• POP (pila): Elimina un elemento de la pila. También se le conoce como sacar o quitar.
• VACIA(pila): Función booleana que indica si la pila está vacía o no.
La definición de una estructura de datos queda completa al incluir las operaciones que se pueden realizar en ella.
Aplicaciones
Las pilas son una estructura de datos muy usada en la solución de diversos tipos de problemas, en el área de la computación:
Llamadas a subprogramas
Tratamiento de expresiones aritméticas
Recursividad
Ordenación
Algoritmo de la función pop (o desapilar)
Hacemos que nodo apunte al primer elemento de la pila, es decir a Pila.
Asignamos a Pila la dirección del segundo nodo de la pila: Pila->siguiente.
Guardamos el contenido del nodo para devolverlo como retorno, recuerda que la operación pop equivale a leer y borrar.
Liberamos la memoria asignada al primer nodo, el que queremos eliminar.
Colas
Una cola es una estructura de datos en la cual los elementos almacenados en la misma se agregan al final y se sacan del principio de la cola. Esta característica hace que el primer elemento insertado en la cola es el primero en salir, como en cualquier cola de la realidad (en un banco, en el cine, en el colectivo). Este tipo de estructuras se denominan FIFO (First In First Out).
El nodo típico para construir pilas es el mismo que vimos en los capítulos anteriores para la construcción de listas y pilas:
Los tipos que definiremos normalmente para manejar colas serán casi los mismos que para manejar listas y pilas, tan sólo cambiaremos algunos nombres:
Es evidente, a la vista del gráfico, que una cola es una lista abierta. Así que sigue siendo muy importante que nuestro programa nunca pierda el valor del puntero al primer elemento, igual que pasa con las listas abiertas. Además, debido al funcionamiento de las colas, también deberemos mantener un puntero para el último elemento de la cola, que será el punto donde insertemos nuevos nodos.
Teniendo en cuenta que las lecturas y escrituras en una cola se hacen siempre en extremos distintos, lo más fácil será insertar nodos por el final, a continuación del nodo que no tiene nodo siguiente, y leerlos desde el principio, hay que recordar que leer un nodo implica eliminarlo de la cola.
Implementación
Las colas, al igual que las pilas, no existen como estructuras de datos estándar en lenguajes de programación, cola es una secuencia de elementos en la que la operación de inserción push se realiza por un extremo y la operación de extracción pop por el otro. También se le llama estructura FIFO (del inglés First In First Out), debido a que el primer elemento en entrar será también el primero en salir.
. Este tipo de estructura de datos se puede representar mediante el uso de:
Arreglos
Listas
Implementación Estática
Cuando se implementan con arreglos unidimensionales, es importante definir tamaño máximo para la cola y dos variables auxiliares. Una de ellas para que almacene la posición del primer elemento de la cola —FRENTE— y otra para que guarde la posición del último elemento de la cola —FINAL—.
Operaciones
Las operaciones básicas que pueden efectuarse son:
Insertar un elemento en la cola
Eliminar un elemento de la cola
Las inserciones se llevaran a cabo por el FINAL de la cola, mientras que las eliminaciones se harán por el FRENTE —recuerde que el primero en entrar es el primero en salir—.
Y las operaciones auxiliares:
Cola_vacía
Cola_llena
Algunas aplicaciones de las colas son:
Para modelar 'colas reales' en el mundo de las computadoras: Colas de impresión, Colas de tareas, Colas de procesos.
Simulaciones.
Búsqueda en anchura.
Listas
Una lista es una estructura de datos en la cual los elementos almacenados en la misma pueden ser agregados, borrados y accedidos sin restricciones, en cualquier punto de la estructura. A diferencia de las pilas y las colas, en las listas se pueden ver todos los elementos de la estructura, permitiendo realizar recorridos y consultas de los datos. De la estructura de una lista se distinguen dos elementos: el principio, a partir del cual se inician las búsquedas y recorridos; y el corriente, elemento de referencia en la lista, a partir del cual se realizan borrados, inserciones y modificaciones.
Implementación
El tipo de dato abstracto lista, contendrá dos referencias a nodos de la lista. La primera corresponderá al primer nodo de la lista. La otra hará referencia al elemento actual o corriente de la lista. Luego, los nodos de la lista se irán encadenando uno a uno hasta el último elemento. Hay que tener en cuenta que el elemento corriente puede ser cualquiera de la lista, y que ira variando según la primitiva que se utilice.
Listas abiertas
La forma más simple de estructura dinámica es la lista abierta. En esta forma los nodos se organizan de modo que cada uno apunta al siguiente, y el último no apunta a nada, es decir, el puntero del nodo siguiente vale NULL. En las listas abiertas existe un nodo especial: el primero. Normalmente diremos que nuestra lista es un puntero a ese primer nodo y llamaremos a ese nodo la cabeza de la lista. Eso es porque mediante ese único puntero podemos acceder a toda la lista. Cuando el puntero que usamos para acceder a la lista vale NULL, diremos que la lista está vacía.
El nodo típico para construir listas tiene esta forma:
Normalmente se definen varios tipos que facilitan el manejo de las listas, en C, la declaración de tipos puede tener una forma parecida a esta:
Es muy importante que nuestro programa nunca pierda el valor del puntero al primer elemento, ya que si no existe ninguna copia de ese valor, y se pierde, será imposible acceder al nodo y no podremos liberar el espacio de memoria que ocupa.
Listas circulares
Una lista circular es una lista lineal en la que el último nodo a punta al primero. Las listas circulares evitan excepciones en las operaciones que se realicen sobre ellas. No existen casos especiales, cada nodo siempre tiene uno anterior y uno siguiente.
En algunas listas circulares se añade un nodo especial de cabecera, de ese modo se evita la única excepción posible, la de que la lista esté vacía.
El nodo típico es el mismo que para construir listas abiertas:
Los tipos que definiremos normalmente para manejar listas cerradas son los mismos que para para manejar listas abiertas:
A pesar de que las listas circulares simplifiquen las operaciones sobre ellas, también introducen algunas complicaciones. Por ejemplo, en un proceso de búsqueda, no es tan sencillo dar por terminada la búsqueda cuando el elemento buscado no existe.
Por ese motivo se suele resaltar un nodo en particular, que no tiene por qué ser siempre el mismo. Cualquier nodo puede cumplir ese propósito, y puede variar durante la ejecución del programa.
Otra alternativa que se usa a menudo, y que simplifica en cierto modo el uso de listas circulares es crear un nodo especial de hará la función de nodo cabecera. De este modo, la lista nunca estará vacía, y se eliminan casi todos los casos especiales.
Listas doblemente enlazadas
Una lista doblemente enlazada es una lista lineal en la que cada nodo tiene dos enlaces, uno al nodo siguiente, y otro al anterior.
Las listas doblemente enlazadas no necesitan un nodo especial para acceder a ellas, pueden recorrerse en ambos sentidos a partir de cualquier nodo, esto es porque a partir de cualquier nodo, siempre es posible alcanzar cualquier nodo de la lista, hasta que se llega a uno de los extremos.
El nodo típico es el mismo que para construir las listas que hemos visto, salvo que tienen otro puntero al nodo anterior:
Para C, y basándonos en la declaración de nodo que hemos visto más arriba, trabajaremos con los siguientes tipos:
El movimiento a través de listas doblemente enlazadas es más sencillo, y como veremos las operaciones de búsqueda, inserción y borrado, también tienen más ventajas.
Lenguajes imperativos u orientados a objetos tales como C o C++ y Java, respectivamente, disponen de referencias para crear listas enlazadas.
Operaciones básicas de una lista.
• Recorrer los elementos hacia adelante
• Recorrer los elementos hacia atrás
• Insertar un nuevo elemento al principio
• Insertar un nuevo elemento al final
• Insertar un nuevo elemento antes de otro
• Insertar un nuevo elemento despues de otro
• Remover un elemento del principio
• Remover un elemento que esta antes que otro
• Remover un elemento que esta despues de otro
• Remover un elemento del principio
• Remover un elemento del final
Aplicaciones
Una lista puede usarse para distintas soluciones, como en el ejemplo que se mostrara a continuación es sobre las calificaciones alumnos, donde para no repetir tanto el nombre, matricula o calificación se implementó una lista donde se declaran dichas variables:
/*
Programa: ListaClase.c
Fecha: 10/09/2015
Proposito: Como costruir un tipo de dato propio mediante STRUCT
*/
#include <stdio.h>
#define MAX 3
typedef struct {
int matricula;
char nombre[40];
float calificacion;
} ALUMNOS;
int main(int argi, char** argc) {
ALUMNOS Lista[MAX];
int i;
for(i = 0; i < MAX; i++) {
printf("Matricula -> ");
scanf("%d", &Lista[i].matricula);
printf("Nombre -> ");
scanf(" %[^\n]", &Lista[i].nombre);
printf("Calificacion -> ");
scanf("%f", &Lista[i].calificacion);
}
system("cls");
printf("\n\n\n");
printf("\tMatricula Nombre Calificacion\n");
printf("\t========= ============================== ============\n");
for(i = 0; i < MAX; i++) {
printf("\t%9d %-30s %12.1f\n", Lista[i].matricula, Lista[i].nombre, Lista[i].calificacion);
}
printf("\n\n\n");
return 0;
}
Donde se nota la diferencia de espacio que usaría si se implementara de otra forma, además de que por ello, a diferencia de pilas y colas, podemos ver un dato cualquiera para ver, ya que en pilas y colas o vez el ultimo o el primero, no los del centro de ellos.
Aplicación de las listas enlazadas
Las listas enlazadas son usadas como módulos para otras muchas estructuras de datos, tales como pilas, colas y sus variaciones.
El campo de datos de un nodo puede ser otra lista enlazada. Mediante este mecanismo, podemos construir muchas estructuras de datos enlazadas con listas; esta práctica tiene su origen en el lenguaje de programación Lisp, donde las listas enlazadas son una estructura de datos primaria (aunque no la única), y ahora es una característica común en el estilo de programación funcional.
A veces, las listas enlazadas son usadas para implementar vectores asociativos, y estas en el contexto de las llamadas listas asociativas. Hay pocas ventajas en este uso de las listas enlazadas; hay mejores formas de implementar éstas estructuras, por ejemplo con árboles binarios de búsqueda equilibrados. Sin embargo, a veces una lista enlazada es dinámicamente creada fuera de un subconjunto propio de nodos semejante a un árbol, y son usadas más eficientemente para recorrer ésta serie de datos.
Ventajas
Como muchas opciones en programación y desarrollo, no existe un único método correcto para resolver un problema. Una estructura de lista enlazada puede trabajar bien en un caso pero causar problemas en otros. He aquí una lista con algunas de las ventajas más comunes que implican las estructuras de tipo lista. En general, teniendo una colección dinámica donde los elementos están siendo añadidos y eliminados frecuentemente e importa la localización de los nuevos elementos introducidos se incrementa el beneficio de las listas enlazadas.
Conclusiones
En este trabajo hablamos sobre la recursividad que es una función que se llama a sí misma.
El concepto de pilas y colas que estas son un tipo particular de listas y también listas que en general, una lista enlazada es una de las estructuras de datos fundamentales, y puede ser usada para implementar otras estructuras de datos. Consiste en la secuencia de nodos, en los que se guardan campos de datos arbitrarios y una o dos referencias, enlaces o punteros al nodo anterior o posterior. Y de ahí el significado de pilas y colas.
Fue una gran actividad ya que investigamos los conceptos antes mencionados y la relación que existe entre ellos y que así mismo forman una parte del gran mundo de las estructuras de datos en su forma más simple y fundamental.
DESCARGA LA PRESENTACION EN POWER POINT
BIBLIOGRAFÍA
Recursividad
· http://webdelprofesor.ula.ve/nucleotrujillo/jalejandro/Prog2/Unidad3.pdf
· http://algoritmicayaracuy.blogspot.mx/2009/11/recursividad.html
· http://es.slideshare.net/felipe190/complemento-a-recursividad
Pilas
· https://algo2.files.wordpress.com/2008/08/ayp2_listas_pilas_y_colas.pdf
· http://www.c.conclase.net/edd/?cap=002
· http://es.slideshare.net/diwal10/pilas-colas-y-listas-estructura-de-datos
Colas
· https://algo2.files.wordpress.com/2008/08/ayp2_listas_pilas_y_colas.pdf
· http://www.c.conclase.net/edd/?cap=003#inicio
· http://es.slideshare.net/diwal10/pilas-colas-y-listas-estructura-de-datos
Listas
· https://es.wikipedia.org/wiki/Lista_(inform%C3%A1tica)
· https://docs.google.com/document/d/1M2GNol0fb4DOGWwXIc9RCKJhNM8tH22WeY_t6LOlZMw/edit#
Abiertas
· http://www.c.conclase.net/edd/?cap=001#inicio
Circulares
· http://www.c.conclase.net/edd/?cap=004#inicio
Doblemente enlazadas
· http://www.c.conclase.net/edd/?cap=005#inicio
