Recursividad

INSTITUTO TECNOLOGICO DE JIQUILPAN

TEMAS A EXPONER:

1.3.3. Recursividad

1.3.4. Manejo de información

1.3.3. RECURSIVIDAD

INTRODUCCION

El área de la programación es muy amplia y con muchos detalles. Los programadores necesitan ser capaces de resolver todos los problemas que se les presente a través del computador aun cuando en el lenguaje que utilizan no haya una manera directa de resolver los problemas. En el lenguaje de programación , así como en otros lenguajes de programación, se puede aplicar una técnica que se le dio el nombre de recursividad por su funcionalidad. Esta técnica es utilizada en la programación estructurada para resolver problemas que tengan que ver con el factorial de un número, o juegos de lógica.

DEFINICIONES:

 La recursividad es un concepto fundamental en matemáticas y en computación.

 Es una alternativa diferente para implementar estructuras de repetición (ciclos).

 Se puede usar en toda situación en la cual la solución pueda ser expresada como una secuencia de movimientos, pasos o transformaciones gobernadas por un conjunto de reglas no ambiguas.

EJEMPLO: CALCULAR EL FACTORIAL DE UN NUMERO

Escribe un programa que calcule el factorial (!) de un entero no negativo. He aquí algunos ejemplos de factoriales:

• 0! = 1

• 1! = 1

• 2! = 2 è 2! = 2 * 1!

• 3! = 6 è 3! = 3 * 2!

• 4! = 24 è 4! = 4 * 3!

5! = 120 è 5! = 5 * 4!

SOLUCIÓN

Aquí podemos ver la secuencia que toma el factorial

1 si N = 0 (base)

N ! =

N * (N – 1) ! si N > 0 (recursión)

Un razonamiento recursivo tiene dos partes: la base y la regla recursiva de construcción. La base no es recursiva y es el punto tanto de partida como de terminación de la definición.

EJEMPLO:

Torres de hanoi (juego de lógica)

 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.

 El propósito del enigma es lograr apilar los cincos aros, en el mismo orden, pero en el hasta 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 se resolvería el caso en que hubiera un aro?

¿Cómo se resolvería el caso en que hubiera 2 aros?

¿Cómo se resolvería el caso de 3 aros?

Resolviendo el problema de las Torres de Hanoi

 Entonces, por

...