Recursion

55 %
45 %
Information about Recursion
Education

Published on January 7, 2008

Author: Clown

Source: authorstream.com

1.2.3 Recursión:  1.2.3 Recursión Programación procedural:  Programación procedural La programación procedural es aquella que está formada por una secuencia de instrucciones llamadas enunciados. ¿Qué es la programación procedural?:  ¿Qué es la programación procedural? Estos enunciados pueden ser: Condicionales. Ciclos. Procedimientos. También es conocida como programación por bloques. ¿Qué es la programación procedural?:  ¿Qué es la programación procedural? Este tipo de programación se basa en la estrategia: divide y conquista. Es decir, separar un problema es una serie de pasos, y cada paso resolverlo por separado. Ejemplo de programación procedural:  Ejemplo de programación procedural Supongamos que se desea desarrollar una aplicación que lee de entrada 10 números enteros, y a estos valores los eleva al cuadrado, desplegando el resultado en pantalla. El problema anterior se puede dividir en los siguientes pasos...:  El problema anterior se puede dividir en los siguientes pasos... Paso 1. Leer los 10 datos. Paso 2. Elevar los 10 datos al cuadrado. Paso 3. Desplegar los 10 datos en pantalla. ¿Cómo mandaríamos ejecutar el código?:  ¿Cómo mandaríamos ejecutar el código? public static void main() { StdOut.println("inicia proceso“); leeArchivo("entrada.txt",datos,10); //PASO 1. elevaCuadrado(datos,10); //PASO 2. escribeArchivo("salida.txt",datos,10); //PASO 3. StdOut.println("proceso terminado“); } Paso 1 Paso 2 Paso 3 Programación recursiva:  Programación recursiva Un procedimiento que se llama a sí mismo, de modo directo o indirecto, se denomina recursión. Programación recursiva:  Programación recursiva La mejor manera de presentar la recursión como técnica de programación es por medio de un ejemplo. Ejemplo: Factorial:  Ejemplo: Factorial Tomaremos el caso del factorial de n, que es una función que indica el producto de los enteros positivos desde 1 hasta n. El factorial se representa con el signo !. Ejemplo: Factorial:  Ejemplo: Factorial Por ejemplo... 1! = 1 2! = 1 x 2 3! = 1 x 2 x 3 4! = 1 x 2 x 3 x 4 5! = 1 x 2 x 3 x 4 x 5 6! = 1 x 2 x 3 x 4 x 5 x 6 ... n! = 1 x 2 x 3 x 4x .... x n-1 x n Por ejemplo, el factorial de 5 es la multiplicación de 1*2*3*4*5 Ejemplo: Factorial:  Ejemplo: Factorial Incluso, podemos expresar dicha operación empezando desde n, y no desde 1, como se mostró en la diapositiva anterior: 1! = 1 2! = 2 x 1 3! = 3 x 2 x 1 4! = 4 x 3 x 2 x 1 5! = 5 x 4 x 3 x 2 x 1 n! = n x n-1 x .... x 5 x 4 x 3 x 2 x 1 Ejemplo: Factorial:  Ejemplo: Factorial Entonces podremos decir que: Es importante determinar un caso base, es decir un punto en el cual existe una condición por la cual no se requiera volver a llamar a la misma función. El factorial de un número n es igual al factorial de un número factorial anterior a él multiplicado por n. Excepto en el caso en que n sea 1, en dicho el resultado es 1. Factorial en programación procedural:  Factorial en programación procedural public int factorial(int n) { int acum = 1; for (int i = 1; i <= n; i++) { acum *= i; } return acum; } Si deseamos el factorial de 4, entonces mandamos ejecutar la función: int f = factorial(4); Factorial en programación recursiva:  Factorial en programación recursiva public int factorial(int n) { int x = 0; if ( n == 1) { return 1; } else { x = factorial(n - 1); return n * x; } } Por cada vez que una función se llama a sí misma, se crea una copia en memoria de ésta función. Este proceso se conoce como instanciación. Control de flujo en una función recursiva:  Control de flujo en una función recursiva Es importante comprender que cada instanciación (copia creada) de un procedimiento recursivo es única y tiene sus propios argumentos, variables locales, etc. Control de flujo en una función recursiva:  Control de flujo en una función recursiva public int factorial(int n) { int x = 0; if ( n == 1) { return 1; } else { x = factorial(n - 1); return n * x; } } …. int y = factorial(3); Ejemplo Matrushka:  Ejemplo Matrushka La Matrushka es una artesanía tradicional rusa. Es una muñeca de madera que contiene otra muñeca más pequeña dentro de sí. Esta muñeca, también contiene otra muñeca dentro. Y así, una dentro de otra. Ejemplo Matrushka:  Ejemplo Matrushka /** * <p> Esta clase fue diseñada con el fin de poner * en práctica el concepto de recursión </p> * * @author Pedro Pérez * @version 1.0 */ import java.awt.*; public class Matrushka { protected Color color; protected Matrushka siguiente; Ejemplo Matrushka:  Ejemplo Matrushka /** * Constructor de la clase. Da valores por omisión * a las variables de estado de la clase * */ public Matrushka() { color = Color.black; siguiente = null; } Ejemplo Matrushka:  Ejemplo Matrushka /** * Constructor de la clase. Recibe datos de entradas, * los cuales utiliza para darle valor inicial a las * variables de estado * * @param c Color que recibirá la Matrushka * @param m Siguiente Matrushka */ public Matrushka(Color c, Matrushka m) { color = c; siguiente = m; } Ejemplo Matrushka:  Ejemplo Matrushka /** * Mutator de la variable <code> color <\code> * * @param c Color que recibirá la Matrushka */ public void setColor(Color c) { color = c; } Ejemplo Matrushka:  Ejemplo Matrushka /** * Accesor de la variable <code> color <\code> * * @return el color de la Matrushka */ public Color getColor() { return color; } Ejemplo Matrushka:  Ejemplo Matrushka /** * Mutator de la variable <code> color <\code> * * @param m Siguiente Matrushka */ public void setSiguiente(Matrushka m) { siguiente = m; } Ejemplo Matrushka:  Ejemplo Matrushka /** * Accesor de la variable <code> siguiente <\code> * * @return el color de la Matrushka */ public Matrushka getSiguiente() { return siguiente; } } Ejemplo Matrushka:  Ejemplo Matrushka Supongamos que queremos hacer una función que nos indique cuántas Matrushkas tenemos. ¿Qué tenemos que hacer? Primero debemos de determinar el caso base: ¿Qué pasa si nuestra Matrushka no contiene ninguna otra? ¿Cuántas llevamos contadas? Repuesta: 1 ¿Qué sucede si nuestra Matrushka contiene otra dentro de ella, qué debemos de hacer? Respuesta: Debemos de seguir contando hasta que ya no haya más Matrushkas Ejemplo Matrushka:  Ejemplo Matrushka public int cuentaMatrushka(Matrushka m) { if (m.getSiguiente() == null) { return 1; } else { return 1 + cuentaMatrushka(m.getSiguiente()); } } Este es el caso base, cuando nuestra Matrushka no contiene a ninguna más Cuando nuestra Matrushka contiene a otra, debemos de seguir contando hasta que hallamos llegado al final Un ejemplo clásico de recursividad: Torres de Hanoi:  Un ejemplo clásico de recursividad: Torres de Hanoi Torres de Hanoi:  Torres de Hanoi Tenemos tres astas A, B y C, y un conjunto de cinco aros, todos de distintos tamaños. El enigma comienza con todos los aros colocados en el asta A de tal forma que ninguno de ellos debe estar sobre uno más pequeño a él; es decir, están apilados, uno sobre el otro, con el más grande hasta abajo, encima de él, el siguiente en tamaño y así sucesivamente. Torres de Hanoi:  Torres de Hanoi El propósito del enigma es lograr apilar los cincos aros, en el mismo orden, pero en el asta C. Una restricción es que durante el proceso, puedes colocar los aros en cualquier asta, pero debe apegarse a las siguientes reglas: Solo puede mover el aro superior de cualquiera de las astas. Un aro más grande nunca puede estar encima de uno más pequeño. ¿Cómo resolvemos el problema?:  ¿Cómo resolvemos el problema? Para encontrar cómo se resolvería este problema, debemos ir viendo cómo se resolvería cada caso. ¿Cómo se resolvería el caso en que hubiera un aro?:  ¿Cómo se resolvería el caso en que hubiera un aro? Pasando directamente el aro de A a C. A B C ¿Cómo se resolvería el caso en que hubiera 2 aros?:  ¿Cómo se resolvería el caso en que hubiera 2 aros? Colocando el más pequeño en el asta B, pasando el grande a el asta C y después moviendo el que está en B a C. ¿Cómo se resolvería el caso de 3 aros?:  ¿Cómo se resolvería el caso de 3 aros? ¿Cómo se resolvería el caso de 4? :  ¿Cómo se resolvería el caso de 4? Resolviendo el problema de las Torres de Hanoi:  Resolviendo el problema de las Torres de Hanoi Entonces, por lo que hemos podido ver, el programa podría definirse de la siguiente manera: Si es un solo disco, lo movemos de A a C. En otro caso, suponiendo que n es la cantidad de aros que hay que mover Movemos los n-1 aros superiores - es decir, sin contar el más grande- de A a B (utilizando a C como auxiliar). Movemos el último aro (el más grande) de A a C. Movemos los aros que quedaron en B a C (utilizando a A como auxiliar). ¿Cómo sería el código de las Torres de Hanoi?:  ¿Cómo sería el código de las Torres de Hanoi? public void torres(int n, char a, char b, char c) { //nombres de astas if (n == 1) { stdOut.println("mueve aro " + n + " del asta " + a + " hasta el asta " + c ); } else { torres(n-1, a, c, b); //Muevo de A a B, usando a C como auxiliar. stdOut.println ("mueve aro " + n + " del asta " + a + " hasta el asta " + c ); torres(n-1, b, a, c); //Muevo de B a C, usando a A como auxiliar. } } El primer parámetro indica el asta origen, el segundo parámetro el asta auxiliar y el tercero el asta destino. Caso base, i igual a 0. ¡Buen trabajo! :  ¡Buen trabajo! Ahora, a hacer tu tarea de esta sesión. ¡Éxito!

Add a comment

Related presentations

Related pages

Rekursion – Wikipedia

Der Aufruf kann dabei am Anfang (Head Recursion, siehe Infiniter Regress) oder am Ende (Tail Recursion oder Endrekursion) der Funktion erfolgen.
Read more

dict.cc | recursion | Wörterbuch Englisch-Deutsch

Übersetzung für recursion im Englisch-Deutsch-Wörterbuch dict.cc.
Read more

Recursion - Recursion

Ursula – RECURSION – RECords ON – URSI – takes you along into her unparalleled world of music. Taking first steps, discovering the world, doing ...
Read more

Recursion - Wikipedia, the free encyclopedia

Recursion is the process of repeating items in a self-similar way. For instance, when the surfaces of two mirrors are exactly parallel with each other, the ...
Read more

Recursion (computer science) - Wikipedia, the free ...

Recursion in computer science is a method where the solution to a problem depends on solutions to smaller instances of the same problem (as opposed to ...
Read more

Endrekursion – Wikipedia

... Funktionsgrenzen hinweg die Ausführung von endständigen Funktionen mit konstantem Speicherplatzverbrauch (proper tail recursion), ...
Read more

Recursion

Recursion. 494 likes · 1 talking about this. ... There is an elephant in my brain ...
Read more

Recursion - Learn You a Haskell for Great Good!

Recursion Hello recursion! We mention recursion briefly in the previous chapter. In this chapter, we'll take a closer look at recursion, why it's important ...
Read more

Recursion | Define Recursion at Dictionary.com

Recursion definition, the process of defining a function or calculating a number by the repeated application of an algorithm. See more.
Read more

recursion - Wiktionary

However, we have still not achieved our goal of devising a finite set of rules which will generate an infinite set of sentence structures. In ...
Read more