Recursion

Information about Recursion

Published on January 7, 2008

Author: Clown

Source: authorstream.com

Content

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!

Related presentations


Other presentations created by Clown

nano technology presentation
30. 08. 2007
0 views

nano technology presentation

TC2000 Presentation AAII
22. 04. 2008
0 views

TC2000 Presentation AAII

chapter 28 notes
17. 04. 2008
0 views

chapter 28 notes

dacorogna
13. 04. 2008
0 views

dacorogna

CH6Slides
09. 04. 2008
0 views

CH6Slides

WHERE DOES WEATHER COME FROM
07. 04. 2008
0 views

WHERE DOES WEATHER COME FROM

ISSJS
30. 03. 2008
0 views

ISSJS

PeakOil
27. 03. 2008
0 views

PeakOil

Scales and Questionnaire Tips
05. 11. 2007
0 views

Scales and Questionnaire Tips

sasaki
17. 06. 2007
0 views

sasaki

Political Cartoons
17. 06. 2007
0 views

Political Cartoons

principles of restoration
17. 06. 2007
0 views

principles of restoration

Revolutionary War Powerpoint
28. 02. 2008
0 views

Revolutionary War Powerpoint

4 How to never get sick again
13. 12. 2007
0 views

4 How to never get sick again

03 RFID
29. 02. 2008
0 views

03 RFID

ch 08 international issues
27. 09. 2007
0 views

ch 08 international issues

MHP in Germany sto v1
12. 10. 2007
0 views

MHP in Germany sto v1

Wireless Broadband Korea Kim
11. 09. 2007
0 views

Wireless Broadband Korea Kim

JimBasney
11. 09. 2007
0 views

JimBasney

Grade 105 Presentation
02. 10. 2007
0 views

Grade 105 Presentation

Dongxian He APAN 2004
11. 10. 2007
0 views

Dongxian He APAN 2004

OWASP Denver Nov 06 presentation
30. 08. 2007
0 views

OWASP Denver Nov 06 presentation

2004 religion Killen Shibley
30. 08. 2007
0 views

2004 religion Killen Shibley

allied partnerships 170505051319
30. 08. 2007
0 views

allied partnerships 170505051319

Satellite Broadcast
30. 08. 2007
0 views

Satellite Broadcast

vslive2005 keynote
28. 11. 2007
0 views

vslive2005 keynote

ADSL QoS
29. 11. 2007
0 views

ADSL QoS

RestaurantsKitchens
07. 12. 2007
0 views

RestaurantsKitchens

Othello 1
01. 11. 2007
0 views

Othello 1

LITERACY CENTERS FOR COACHES
05. 11. 2007
0 views

LITERACY CENTERS FOR COACHES

TKaM jeopardy
05. 11. 2007
0 views

TKaM jeopardy

HR XML Seminaire 16 11 2005
30. 08. 2007
0 views

HR XML Seminaire 16 11 2005

Mangenot1 2
02. 11. 2007
0 views

Mangenot1 2

PDC Review Jay 041118
26. 11. 2007
0 views

PDC Review Jay 041118

ks4 where energy
18. 12. 2007
0 views

ks4 where energy

aula voip
28. 12. 2007
0 views

aula voip

Chapter 7
28. 11. 2007
0 views

Chapter 7

Web CT Student Orient
10. 12. 2007
0 views

Web CT Student Orient

ch7S07govt2302
01. 01. 2008
0 views

ch7S07govt2302

Philadelphia FryODiesel
07. 01. 2008
0 views

Philadelphia FryODiesel

Hafner Eco Eng pres1
03. 01. 2008
0 views

Hafner Eco Eng pres1

psy203s authoritarian
30. 08. 2007
0 views

psy203s authoritarian

MMS Spoofing
30. 08. 2007
0 views

MMS Spoofing

WTFD New
01. 10. 2007
0 views

WTFD New

Presentación Cilca 2005
14. 11. 2007
0 views

Presentación Cilca 2005

rtbbntalk
15. 11. 2007
0 views

rtbbntalk

Chapter32
24. 12. 2007
0 views

Chapter32

Homeland Security Congressional
05. 01. 2008
0 views

Homeland Security Congressional

CNOMMeetingICC2006
21. 11. 2007
0 views

CNOMMeetingICC2006

airforce camp brief 1
23. 12. 2007
0 views

airforce camp brief 1

favourites
26. 06. 2007
0 views

favourites

Presentation Atelier Bangkok2
31. 12. 2007
0 views

Presentation Atelier Bangkok2

kerala piravi06
26. 06. 2007
0 views

kerala piravi06

jim quinn
26. 06. 2007
0 views

jim quinn

ioc report
26. 06. 2007
0 views

ioc report

Good Movies
26. 06. 2007
0 views

Good Movies

Generation Gap Trivia
26. 06. 2007
0 views

Generation Gap Trivia

gates
26. 06. 2007
0 views

gates

Fulbright Movies
26. 06. 2007
0 views

Fulbright Movies

food and menus
26. 06. 2007
0 views

food and menus

lecture32
07. 10. 2007
0 views

lecture32

Astra Sales Kit 3 1 06
03. 01. 2008
0 views

Astra Sales Kit 3 1 06

KALEB
26. 06. 2007
0 views

KALEB

milestone6 action
27. 11. 2007
0 views

milestone6 action

game consoles edit
26. 06. 2007
0 views

game consoles edit

303lec13
30. 08. 2007
0 views

303lec13

Fabric Spade Amalgam Chief
26. 06. 2007
0 views

Fabric Spade Amalgam Chief

FY2006 Tourism Media Plan
26. 06. 2007
0 views

FY2006 Tourism Media Plan

F303 Class 18
30. 08. 2007
0 views

F303 Class 18

political humor
17. 06. 2007
0 views

political humor

regional dialects
17. 06. 2007
0 views

regional dialects

Quantifying Quality MASTER
17. 06. 2007
0 views

Quantifying Quality MASTER

PS270Lect14
17. 06. 2007
0 views

PS270Lect14

prosestyles
17. 06. 2007
0 views

prosestyles

2091ppt
14. 12. 2007
0 views

2091ppt

rosary
17. 06. 2007
0 views

rosary

rhetorical devices
17. 06. 2007
0 views

rhetorical devices

Research Paper
17. 06. 2007
0 views

Research Paper

Relationships Presentation
17. 06. 2007
0 views

Relationships Presentation

relationships
17. 06. 2007
0 views

relationships

Polyamory 101class
17. 06. 2007
0 views

Polyamory 101class

Hobbes and Locke
30. 08. 2007
0 views

Hobbes and Locke

fastook no movies
26. 06. 2007
0 views

fastook no movies

En Jean Delion Stigma
02. 01. 2008
0 views

En Jean Delion Stigma

Forbrugeren 2008 1
26. 06. 2007
0 views

Forbrugeren 2008 1

FairTrade
16. 11. 2007
0 views

FairTrade

dyna202 5509
05. 11. 2007
0 views

dyna202 5509

recipes
05. 12. 2007
0 views

recipes

NatureAreaTrees
30. 08. 2007
0 views

NatureAreaTrees

CRAY
11. 09. 2007
0 views

CRAY

enum 6
11. 09. 2007
0 views

enum 6

05 ncs courses
12. 03. 2008
0 views

05 ncs courses

20020913 Moon Soo Kang
11. 09. 2007
0 views

20020913 Moon Soo Kang

epomodule
08. 11. 2007
0 views

epomodule

goetz vortragenergie2302
22. 11. 2007
0 views

goetz vortragenergie2302

The Black Power 000
30. 08. 2007
0 views

The Black Power 000

Security Engineering In Vista
30. 08. 2007
0 views

Security Engineering In Vista

FA05 cs294 5 lecture 6 final
20. 11. 2007
0 views

FA05 cs294 5 lecture 6 final

etherb
01. 01. 2008
0 views

etherb

SDE Presentation
30. 08. 2007
0 views

SDE Presentation

AFuelsCall1 032305
26. 02. 2008
0 views

AFuelsCall1 032305

11th meeting Shuji Shimizu
09. 10. 2007
0 views

11th meeting Shuji Shimizu

2 Fleet Manegement
23. 11. 2007
0 views

2 Fleet Manegement

Biophysics GYoon
04. 01. 2008
0 views

Biophysics GYoon