domingo, 17 de enero de 2016

Algoritmos - 3 de 5



5.4 Algoritmos recursivos

Se dice que un objeto es recursivo cuando el propio objeto está compuesto parcialmente por sí mismo. Los sistemas recursivos tienen una importancia particular para realizar ciertas definiciones matemáticas. Un ejemplo lo encontramos en la definición del factorial de un número. La función factorial para los números naturales puede ser expresada de la manera siguiente:


Esta es la expresión recursiva del factorial de un número, frente a la iterativa, expresada en la ecuación (5.2)

Los sistemas recursivos no se encuentran sólo en imaginario mundo de las matemáticas, sino que también en la más prosaica realidad, como puede verse al enfrentar dos espejos o al mirar una coliflor o un helecho. Poder establecer una expresión recursiva implica poder definir una serie infinita de objetos mediante la inicialización de un número finito de objetos. Desde el punto de vista informático esto abre posibilidades que dan vértigo, ya que se pueden describir un número infinito de operaciones mediante un programa finito, aunque, al contrario que los programas que contienen bucles, no presente repeticiones de código explícitas. Los algoritmos recursivos, sin embargo, son particularmente adecuados cuando el problema a resolver, o la función matemática a computar o la estructura de datos a ser procesada está definido en términos recursivos. En general un programa recursivo P es función (Π) de una serie de instrucciones Si distintos de P y de P mismo:


La herramienta necesaria y suficiente para poder expresar programas de manera recursiva en un determinado lenguaje de programación es que el lenguaje de programación admita funciones, procedimientos o subrutinas (como prefiera llamarse). 
Cuando una función contiene una llamada explícita a sí misma, se dice entonces que hay una recursividad directa. Cuando, por el contrario, una función no realiza una llamada directa a sí misma, sino que lo hace a través de otra función, se dice que tiene una recursividad indirecta.


Ejemplo 10. Obtención del factorial de un número N recursivamente

Anteriormente se determinó el factorial de un número N de manera iterativa según la fórmula:


Y acabamos de ver cómo también puede expresarse de manera recursiva según esta otra forma:


La cual define el factorial de un número como el producto de ese número con el factorial del número anterior; salvo el factorial de 0, que es 1 por definición. El diagrama de flujo del algoritmo para calcular el factorial de un número de manera recursiva es el siguiente:


Hay que observar que en el diagrama de flujo no hay un retroceso en la línea del programa, sino que lo que aparece es una nueva llamada al propio programa (Factorial) cada vez que se trata de calcular el factorial de un número superior a 0. A su vez, esta llamada pide calcular el factorial del número anterior al que se encuentra en cada momento, por lo que llegará un momento en el que se tratará de calcular el factorial de 0. En este momento, debido a la bifurcación que hay, se determina el primer resultado, que es 1, y finaliza el programa en el que se está calculando el factorial de 0. Al finalizar este programa se continúa con el cálculo del factorial de 1, donde se establece el segundo resultado (1*1) y finaliza este segundo programa. A su vez vuelve a continuar el programa superior, que se corresponde con el cálculo del factorial de 2, y así continúa la ascensión sucesivamente hasta llegar a determinar el valor del factorial del número que se ha solicitado.


Ejemplo 11. Determinar recursivamente si un número N es o no primo 

Recordamos que un número entero N es primo si es mayor o igual a dos y sus únicos factores son el 1 y el propio número. En el Ejemplo 6 y en el Ejemplo 7 se estableció un método iterativo para determinar si un número cumple esta condición. Este método consiste en dividir al número entre todos los números naturales que hay entre el 2 y la raíz cuadrada del número a estudiar, observando si en algún caso la división era exacta.

De lo que ahora se trata es de seguir el mismo razonamiento anterior de manera recursiva. Para ello se va a plantear el diagrama de flujo en dos partes: la inicialización y el cálculo recursivo.

En la inicialización el usuario pasa el número que quiere saber si es primo, el cual queda guardado en la variable N. A continuación se guarda la raíz cuadrada de N en una variable global -K- y por último se inicializa el proceso recursivo en el que se chequea si es divisible N entre algún número natural comprendido entre el 2 y K. Para ello se utiliza una función auxiliar que llamaremos Mirar_si_es_divisible(N,k), la cual se utiliza en la inicialización para k=2. (Nótese que se está diferenciando entre K mayúscula y k minúscula).

Esta función auxiliar contendrá los pasos que hay que dar para determinar si N es divisible entre k. En caso de que no lo sea, realizará otra llamada recursiva a si misma para chequear si N es divisible entre k+1, hasta que suceda que, o bien k es superior a K -en cuyo caso N es primo- o bien N sea divisible por k -en cuyo caso N no es primo. 

El diagrama de flujo queda de la siguiente manera:




Ejemplo 12. El triángulo de Sierpinski

El triángulo de Sierpinski entra en el ámbito de los fractales. Fractal procede del adjetivo latino ’fractus’, que significa "interrumpido" o "irregular". 
La geometría del fractal fue utilizada por Benoît Mandelbrot en 1975 para describir ciertas formas complejas de la naturaleza como nubes, sistemas montañosos, galaxias, flores, ramificaciones arbóreas y bronquiales, rocas, cuencas hidrográficas, el sistema neuronal, las líneas costeras, esponjas,... y objetos matemáticos como el conjunto de Cantor o el triángulo de Sierpinski, cuyo comportamiento caía fuera del marco de la matemática tradicional.



El triángulo de Sierpinski es una construcción geométrica realizada mediante una sucesión de triángulos. La base del método está en que un triángulo puede dividirse en tres triángulos exactamente iguales. A su vez, cada uno de estos tres triángulos puede dividirse en otros tres triángulos exactamente iguales y así sucesivamente. De manera que el triángulo de Sierpinski es un triángulo formado a partir de una sucesión sucesiva de sucesivos triángulos que se suceden sucesivamente, formándose a partir de triángulos pequeños otros triángulos cada vez más grandes.



La manera adecuada para realizar esta construcción geométrica es mediante un sistema de dibujo recursivo. En la parte inicial del proceso se indica el orden del triángulo de Sierpinski, donde el orden es el número de subdivisiones triangulares con las que se divide el triángulo mayor. Posteriormente se procede a dibujar los triángulos según el orden indicado.

Para dibujar los triángulos se va a establecer una subrutina propia con la que se dibujará un triángulo mediante tres variables (X,Y,h). La variables X, Y se corresponden con la posición del vértice superior del triángulo y h se corresponde con la altura o la base del triángulo, como puede verse en la Figura 5.3. Obsérvese que en la Figura 5.3, las proporciones no se mantienen, ya que aunque está dibujado como un triángulo equilátero, es un isósceles. La subrutina para dibujarlo recibirá el nombre de Dibujar_triangulo(x,y,h).


La inicialización la realizaremos dentro de una rutina principal a la que llamaremos Triangulo_Sierpinski(N), donde N es el orden del triángulo. En esta rutina se inicializarán las coordenadas X, Y del primero de los triángulos que va a ser dibujado. Por real decreto vamos a hacer que el punto de origen esté en la posición (0,0) -punto A0 de la Figura 5.4-. Siguiendo el mismo criterio, se asigna una longitud inicial a h de una unidad. Por último esta rutina iniciará una subrutina a la que llamaremos triangulo(N,x,y,h). Esta subrutina es quien contendrá las instrucciones para ir dibujando los triángulos recursivamente.


Básicamente la subrutina triangulo(N,X,Y,h) se va a limitar a localizar el lugar en el que ha de ser dibujado cada uno de los triángulos, así como de determinar el tamaño que tendrán los triángulos. Como se ha dicho en la introducción al ejemplo, cada triángulo se compone de otros tres triángulos más pequeños. En concreto, un triángulo de altura h se compone de otros tres triángulos de altura h/2, como puede verse en la Figura 5.5. De forma que el triángulo que tiene su vértice superior en la posición Ai tiene una altura h y está formado por tres triángulos de altura h/2 que tienen su vértice superior en las posiciones Ai+1, Bi+1 y Ci+1. Con este esquema queda planteado el sistema recursivo ya que cada vez que se ejecuta la subrutina triangulo(N,X,Y,h), esta se llama a si misma 3 veces - triangulo(N-1,X,Y,h)- para elaborar un triángulo de orden menor, modificando las posiciones X, Y según el lugar donde debe encontrarse el vértice superior de cada triángulo y reduciendo h a la mitad.



Cuando el orden del triángulo a dibujar es 0, detienen las llamadas recursivas. En ese momento se procede a dibujar el triangulo y finaliza el hilo de esa subrutina. La evolución del dibujo de un triángulo de Sierpinski de orden 3 según el esquema planteado es la siguiente:



Asimismo, el diagrama de flujo para dibujar el triángulo de Sierpinski de la manera que acaba de ser planteada es el siguiente:





Espero haber ayudado en algo. Hasta la próxima oportunidad!











  

No hay comentarios:

Publicar un comentario

       

Etiquetas

Academy (23) Accediendo a datos con ADO .NET (31) Acceso a la red (30) Algoritmo (34) Algoritmos en JAVA (2) Ampliación de clases (2) APRENDA A PROGRAMAR COMO SI ESTUVIERA EN PRIMERO - Autores : IKER AGUINAGA (3) APRENDA A PROGRAMAR COMO SI ESTUVIERA EN PRIMERO - Autores : IKER AGUINAGA (10) Aprendiendo a desarrollar en Windows 8 (5) Aprendiendo UML en 24 Horas (Autor : Joseph Schmuller ) (30) Arquitectura (29) Arquitectura del Computador (3) Arquitectura del Computador - Historia de la informática (1) Asignación de direcciones IP (18) Aspectos fundamentales de bases de datos (5) Auditoría de la dirección (2) Auditoría de Sistemas (3) Auditoría Informática - Un enfoque práctico - Mario G . Piattini y Emilio del Peso (7) Avanzado (23) Base de Datos (67) Básico (23) Bios (29) Business Productivity Online Suite - BPOS (3) Capa de Red (22) Capa de Transporte (16) Capítulo 1 - Documentos HTML5 (6) Capítulo 10. API Web Storage (2) Capítulo 11. API IndexedDB (4) Capítulo 12. API File (1) Capítulo 2. Estilos CSS y modelos de caja (7) Capítulo 3. Propiedades CSS3 (4) Capítulo 4. Javascript (6) Capítulo 5. Video y audio (6) Capítulo 6. Formularios y API Forms (8) Capítulo 7. API Canvas (5) Capítulo 8. API Drag and Drop (2) Capítulo 9. API Geolocation (2) CCNA1 v5.0 (195) CCNA1 v6.0 (23) CCNA2 v5.0 (26) CCNA3 v5.0 (25) CCNA4 v5.0 (23) CD-ROM (3) Chapter 1 How does Xamarin.Forms fit in? (7) Chapter 2 Anatomy of an app (5) Cisco (297) Cloud Computing (3) CNNA v5.0 Routing & Switching (216) CNNA v6.0 Routing & Switching (2) Codigo (2) Computadora (32) Configuración (29) Configuración de un sistema operativo de red (21) Control (29) Creación de tipos de datos y tablas (3) Creación y Administración de bases de datos (3) Creando la Interface de la Aplicación Windows (50) Creating Mobile Apps with Xamarin.Forms (13) Cuenta (29) Curso (32) Curso Aprendiendo a Programar (25) Datos (3) Desarrollando en Windows 8 - AVANZADO (2) Desarrollando en Windows 8 - BÁSICO (3) Desarrollando en Windows 8 - INTERMEDIO (2) Desarrollo (2) Desarrollo .Net (21) Desarrollo avanzado de Windows Store Apps usando C# (1) Desarrollo basado en conceptos de Ingeniería de Software para Visual Studio (2) DESARROLLO DE APLICACIONES WINDOWS CON MICROSOFT .NET (37) DESARROLLO DE APLICACIONES WINDOWS CON MICROSOFT .NET (Autor: Luis Dueñas Huaroto) (29) Desarrollo en Microsoft Visual Studio (44) Desarrollo en Microsoft Visual Studio - AVANZADO (15) Desarrollo en Microsoft Visual Studio - BÁSICO (14) Desarrollo en Microsoft Visual Studio - INTERMEDIO (18) Desarrollo en Windows Phone 8 (13) Diagnostico (4) Diagrama (3) Diagramas de actividades (2) Diagramas de colaboraciones (2) Diagramas de secuencias (2) Digital (2) Diplomado (2) Disco (29) Disco Duro (4) Diseño de aplicaciones de Windows 8 en HTML 5 (7) Dispositivos Electrónicos (11) Doctorado (2) Ejemplos (3) Ejemplos de algoritmos (27) El camino hacia el CSS3 (3) El diseño web flexible (6) El elemento de diseño Canvas (3) El enfoque de los sistemas (3) El flujo de un programa (2) El gran libro de HTML5 - CSS3 y Javascript - Autor: Juan Diego Gauchat (55) El principio de organicidad (7) Electrónica (2) Elementos de un sistema (5) Empresas (2) Entrada y salida (4) Entropía y neguentropía (7) Estrategia (2) Estructura de un programa Java (12) Estructuras de almacenamiento (10) Estructuras de control (6) Estructuras de las tablas en SQL Server (2) Estructuras fundamentales de los datos (2) Ethernet (21) Evolución y Familias de los Microprocesadores (15) Exámen (23) Exploración de la red (23) Extensión de clases (4) Facebook (4) Familia Intel (15) Forefront (8) Función (3) Funciones de una red (12) Funciones de una red informática (1) Fundamentos de C# para absolutos principiantes (17) Fundamentos de programación en Java (50) Generaciones de la computadora (5) Gestión (3) Gestión de riesgos - Auditoría de Sistemas (1) GONZALO MARTÍNEZ (1) Grupos Facebook (1) Harvard (29) Historia de las computadoras (11) HTML5 y CSS3 - Autor: Christophe Aubry (99) HTML5 y CSS3 aplicadal texto (7) HTML5 y CSS3 para los formularios (15) Imágenes (2) Implementación de Windows 7 (11) Información (31) Informática (29) Ingeniería (4) Instalar (29) Inteligencia (2) Inteligencia de Negocios con SQL Server (3) Intermedio (23) Internet (29) Internet Explorer 9 (3) Introducción a ASP.NET 5 (8) Introducción a Java (7) Introducción a jQuery (8) Introducción a la Auditoría de Sistemas (2) Introducción a la teoría general de sistemas (Oscar Johansen Bertoglio) (39) Introducción a Networking (2) Introducción a Window Forms (5) Introducción al acceso a datos con ADO .NET (9) Investigación de Operaciones (12) Java (52) Jump Start de consultas en las bases de datos de Microsoft SQL Server 2012 (8) La definición de un Sistema (6) La evolución del HTML y del CSS (3) La nueva sintaxis HTML5 (12) LA QUINTA DISCIPLINA en la práctica (Autor : Peter Senge) (28) Las animaciones en CSS3 (5) Las transformaciones CSS3 (11) Las transiciones con CSS3 (8) Licenciamiento Microsoft (3) Local Area Network (LAN) - Red de Area Local (2) Lógico (2) Los elementos de la estructura en html5 (9) Los elementos multimedia: audio y vídeo (2) Los estilos de caja en CSS3 (13) Los nuevos selectores de CSS3 (6) Maestría (2) Mantenimiento de Mouse y Teclado (2) Manual de Microsoft SQL Server - Full Transact SQL (68) Manual de soporte técnico para escuelas sobre windows 7 (42) Marco Teorico de Investigación de Operaciones (6) Medios de Almacenamiento (11) Medios de Networking (2) Mejorando la Interface de las Aplicaciones Windows (26) Memoria Tipos y Clases (5) Método (2) Metodología (1) Microsoft (324) Microsoft Lync 2010 (7) Microsoft Silverlight 4.0 (2) Microsoft Virtual Academy (356) Modelo (2) Modelo OSI y TCP-IP (2) Modelos con poco grado de dificultad de Programación Lineal - Investigación de Operaciones (13) Modelos con razonable grado de dificultad de Programación Lineal - Investigación de Operaciones (10) Modelos de desafio de Programación Lineal - Investigación de Operaciones (5) Modelos difíciles de Programación Lineal - Investigación de Operaciones (5) Modelos Fáciles de Programación Lineal - Investigación de Operaciones (13) Modelos lineales con solver (3) Modulo (23) Movimiento (2) Mozilla (29) MS SQL Server (77) MS Virtualization para Profesionales VMware - Gestión (3) MS Virtualization para Profesionales VMware- Plataforma (4) MVA (263) Negocio (2) Nivel Avanzado Desarrollo .Net (6) Nivel Básico Desarrollo .Net (11) Nivel Intermedio Desarrollo .Net (8) Normas técnicas peruanas y su evolución - Auditoría de Sistemas (1) Nube Privada - Avanzado (6) Nube Privada - Básico (6) Nube Privada - Intermedio (6) Office 365 (3) Optimización de Escritorio (10) Optimización de Escritorio - Avanzado (4) Optimización de Escritorio - Básico (3) Optimización de Escritorio - Intermedio (3) ORACLE 10g - ADMINISTRACIÓN Y ANÁLISIS (3) Oracle 10g y el Grid Computing (3) Organización aleatoria y secuencial (1) Partes principales de la Mainboard (12) Perceptron (2) Perfil (2) Periféricos de Entrada / Salida (15) Pesi (2) PHP y MySQL - Manual de aprendizaje para crear un sitio web - Autor : Olivier ROLLET (79) Plan (2) Plataforma (29) PMBOK (24) PMBOK - Guía de los fundamentos para la dirección de proyectos (24) PMBOK - INFLUENCIA DE LA ORGANIZACIÓN Y CICLO DE VIDA DEL PROYECTO (6) PMBOK - Introducción (11) PMBOK - PROCESOS DE LA DIRECCIÓN DE PROYECTOS (5) Prevención - Herramientas e Instrumentos de Medida (9) Principios básicos de enrutamiento y switching (169) Proceso (2) Proceso de auditoría de sistemas informáticos (2) Programación en Android - Auor : Salvador Gómez Oliver (46) Programación paso a paso de C# - Autor : Nacho Cabanes (16) Protocolos y comunicaciones de red (17) Proyecto (2) Qué es un sistema (4) Red de Área Local Inalámbrica (WLAN) (4) Redes (30) Redes inalámbricas - WIRELESS - Conocimiento general (15) Redes neuronales (2) Redes y Comunicaciones (45) Reparación de Fuentes - UPS - Estabilizadores (10) Reparación de Impresoras (9) Reparación de Monitores (16) Router (29) Seguridad en la Nube (3) Seminario (23) Server (24) Sharepoint 2010 - Nivel Básico (6) Sharepoint 2010 - Niveles Avanzados (18) Sharepoint 2010 - Niveles Avanzados - Básico (8) Sharepoint 2010 - Niveles Avanzados - Intermedio (9) Sinergia y recursividad (4) Sistema (33) Sistema de Cableado Estructurado (9) Software (30) SOLUCIÓN GRÁFICA DE MODELOS DE PROGRAMACIÓN LINEALES - INVOPE (8) Soporte a Infraestructura (3) SQL (38) SQL Azure - Introducción (3) Subsistemas de control (4) Tablas (4) Tarjeta Principal del Sistema (10) Tarjetas de Interfaces (7) Tecnología (31) Tecnologías LAN (1) TEORÍA GENERAL DE SISTEMAS (1) Tic (2) Tipo (2) TML5 y CSS3 - Autor: Christophe Aubry (12) Trabajando con el Formulario (7) Un diseño HTML5/CSS3: dConstruct 2011 (3) Un diseño HTML5/CSS3: FlipThru (2) Un diseño HTML5/CSS3: The Cat Template (2) Usando Controles Windows Forms (12) Usando Herramientas de Datos de Visual Studio (6) Ventas (2) Virtualización Hyper - V Nivel Básico (5) Virtualización Hyper - V Nivel Intermedio (5) What’s New in Windows 8.1 Security (4) Window (29) Windows 7 Segunda Fase - AVANZADO (4) Windows 7 Segunda Fase - BÁSICO (6) Windows 7 Segunda Fase - INTERMEDIO (4) Windows 8 - Vista Previa (4) Windows 8.1 To Go (2) Windows Azure (3) Windows Phone 7 (2) Windows Server 2008 R2 (3) Windows Server 2012 - Gestión y Automatización (3) Windows Server 2012 R2 Essentials (7) Windows Server 2012: Almacenamiento (5) Windows Server 2012: Identidad y Acceso (4) Windows Server 2012: Revisión Técnica (7) Xamarin (1)

Páginas vistas en total según Google