ii. recursividad

RECURSIVIDAD Página 1

La recursividad es una técnica de programación importante. Se utiliza para realizar una llamada a una función desde la misma función. Como ejemplo útil se puede presentar el cálculo de números factoriales.

2011

INSTITUTO TECNOLOGICO DE TAPACHULA

http://www.monografias.com/trabajos7/caes/caes.shtml

http://www.monografias.com/trabajos7/mafu/mafu.shtml

INSTITUTO TECNOLOGICO DE TAPACHULA

CATEDRÁTICO: ING. ROSEL MUÑOS LÓPEZ

MATERIA: ESTRUCTURA DE DATOS

UNIDAD II.- RECURSIVIDAD

ALUMNOS: EMMANUEL DE JESUS ROBLES

GONZALEZ EDUARDO BARTOLON ORTIZ EDI ALBERTO MORALES CRUZ

CARRERA: ING. SISTEMAS COMPUTACIONALES

TAPACHULA DE CORDOBA Y ORDOÑEZ

A 10 DE SEPTIEMBRE DE 2011.


INDICE

ContenidoINTRODUCCION:

EJEMPLO SIMILAR DE LO QUE ES LA RECURSIVIDAD:.....................................................................5

RECURSIVIDA DEFINICION:.............................................................................................................5

TIPOS DE RECURSIVIDAD SEGÚN SU COMPLEJIDAD.......................................................................9

FUNCIÓN RECURSIVA...................................................................................................................10

ASIGNACION ESTATICA Y DINAMICA DE LA MEMORIA................................................................11

CÓMO FUNCIONAN LOS ALGORITMOS RECURSIVOS...................................................................12

DISEÑO DE ALGORITMOS RECURSIVOS........................................................................................13

PROPIEDADES DE ALGORITMOS RECURSIVOS:.............................................................................14

EJEMPLO PROGRAMA QUE CALCULA EL FACTORIAL....................................................................14

EJEMPLO DE RECURSIVIDAD DE LA SERIE FIBONACCI.................................................................17

CADENAS RECURSIVAS O RECURSIVIDAD INDIRECTA...................................................................19

PROBLEMA DE LAS TORRES DE HANÓI:........................................................................................22

RESOLUCIÓN DE UN PROBLEMA DE LAS TORRES DE HANOI........................................................24

“Dividir para vencer”...................................................................................................................25

CÓDIGO FUENTE DE PROGRAMA DE LAS TORRES DE HANÓI.......................................................25

RECURSION VS. ITERACIÓN..........................................................................................................26

ANÁLISIS DE COMPLEJIDAD EN RECURSIVIDAD............................................................................27

RECURSIVIDAD ARBOLES..............................................................................................................28

RECURSIVIDAD EN ORDENACIÓN RÁPIDA (QUICKSORT)..............................................................28

Ejemplos de recursividad.............................................................................................................33

BIBLIOGRAFÍA...............................................................................................................................45


Presionar tecla Ctrl + click sobre el tema que desea ver.

INTRODUCCIÓN

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 Java, 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. Las asignaciones de memoria pueden ser dinámicas o estáticas y hay diferencias entre estas dos y se pueden aplicar las dos en un programa cualquiera.

El método recursivo es un método que se llama así mismo directa o indirectamente. Existen dos clases de recursividad que son: recursión directa que es el proceso de por el que un método se llama así mismo desde el propio cuerpo del método, y la recursión indirecta implica más d un método.

La recursividad indirecta implica que la existencia de dos métodos: uno() y dos (). Entonces desde el main () llama a uno (), y a continuación uno () llama a dos (). En alguna parte del proceso dos () llama a uno (), una segunda llamada a uno (). Esta acción es recursión indirecta, por eso es recursiva, ya que uno () ha sido llamado dos veces, sin retornar nunca a su llamadora.


http://www.monografias.com/Computacion/Programacion/

http://www.monografias.com/trabajos13/memor/memor.shtml

http://www.monografias.com/trabajos15/logica-metodologia/logica-metodologia.shtml

http://www.monografias.com/trabajos15/metodos-creativos/metodos-creativos.shtml

http://www.monografias.com/trabajos35/concepto-de-lenguaje/concepto-de-lenguaje.shtml

http://www.monografias.com/trabajos16/desarrollo-del-lenguaje/desarrollo-del-lenguaje.shtml

http://www.monografias.com/trabajos15/computadoras/computadoras.shtml

http://www.monografias.com/trabajos15/calidad-serv/calidad-serv.shtml#PLANT

EJEMPLO SIMILAR DE LO QUE ES LA RECURSIVIDAD:

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.

RECURSIVIDA DEFINICION:

Es una alternativa diferente para implementar estructuras de repetición (ciclos). Los módulos se hacen llamadas recursivas.

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.

Un método recursivo es aquel que se llama a sí mismo, bien directamente o bien a través de otro método.

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

Recursividad es una técnica de programación importante. Se utiliza para realizar una llamada a una función desde la misma función. Recursividad y la iteración (ejecución en bucle) están muy relacionadas, cualquier acción que pueda realizarse con la recursividad puede realizarse con iteración y viceversa.

La recursión en los subprogramas puede darse de dos maneras diferentes:


a) Directa: el subprograma se llama directamente a sí mismo. Por ejemplo, un subprograma y en alguna parte de el aparece una llamada a sí mismo.

b) Indirecta: el subprograma llama a otro subprograma, y este a su vez llama al primero. Por ejemplo, el subprograma P llama al subprograma Q y este a su vez invoca al primero (fig. 1). También se da la recursión indirecta cuando el subprograma llama a otro y este a un tercero. Una vez ejecutado, el control regresa al subprograma que lo llamo; lo mismo sucede en todos sus niveles. Por ejemplo, el subprograma P que llama al subprograma Q, y este llama al subprograma V. Cuando V concluye, el control regresa a Q, y al terminar este, el control se transfiere a P (fig.2)


Llamada a P

Subprograma P

Llamada a Q

Subprograma P

Subprograma Q

Llamada a P

Subprograma P

Subprograma Q

Subprograma V

Llamada a Q

Llamada a V

Fig. 1

Fig. 2

Es fácil crear una función recursiva que no llegue a devolver nunca un resultado definitivo y no pueda llegar a un punto de finalización. Este tipo de recursividad hace que el sistema ejecute lo que se conoce como bucle "infinito".

public class Recurividad // se declara la clase {

static int método(int a) // este es un método recursivo donde su parámetro a adquiere el valor de x.

{a++; // se incrementa la variable a.return método(a); // este es el llamado al método así mismo donde no tiene fin

}public static void main(string arg []) // este es el metodo main donde java ejecuta los

programas{

int x; // declaracion de una variable local x del método main.x=Integer.parseInt(JOptionPane.showInputDialog(null,”introduaca numero”));

// pedimos el valor de x.metodo(x); // se manda a llamar al método statico.

}}


Los parámetros y variables locales toman nuevos valores en cada llamada (no se trabaja con los anteriores). Un procedimiento o función se dice recursivo si durante su ejecución se invoca directa o indirectamente a sí mismo. Esta invocación depende al menos de una condición que actúa como condición de corte que provoca la finalización de la recursión.

Un algoritmo recursivo consta de:

1- Al menos un caso trivial o base, es decir, que no vuelva a invocarse y que se ejecuta cuando se cumple cierta condición, y

2- el caso general que es el que vuelve a invocar al algoritmo con un caso más pequeño del mismo.

public class Recurividad // se declara la clase {

static int método(int a) // este es un método recursivo donde su parámetro a adquiere el valor de x.

{If(a==0) // este es una sentencia de control para finalizar la recursividad{

a--; // se le resta 1 al valor de la variable a .// a este se le denomina caso base por qué no se vuelve a invocar al

mismo método.}Else{

return método(a); // este es el llamado al método así mismo donde no tiene fin

// También se le denomina caso GENERAL por que se llama así mismo}

}public static void main(string arg []) // metodo main donde java ejecuta los programas{

int x; // declaracion de una variable local x del método main.x=Integer.parseInt(JOptionPane.showInputDialog(null,”introduaca numero”));

// pedimos el valor de x.metodo(x); // se manda a llamar al método statico.

}}


TIPOS DE RECURSIVIDAD SEGÚN SU COMPLEJIDAD

1. Recursión lineal: Un método recursivo es lineal, si como máximo tiene una llamada recursiva por rama del condicional, de manera que la cantidad de llamadas recursivas puede calcularse como una función lineal que dependerá de la velocidad con la cual progresa hacia el caso base. Ésta a su vez la subdividimos en:

1. Recursión por la cola: es cuando la llamada recursiva se hace al final del método, no quedan operaciones pendientes sobre los datos, de manera que no hace falta representar con una pila las variables de cada llamada, y el método recursivo lo podríamos transformar tranquilamente en un bucle iterativo.

2. Recursión no por la cola: es cuando después de ejecutar todas las llamadas recursivas el método debe realizar una operación pendiente para completar el proceso.

2. Recursión no lineal: Un método recursivo es no lineal, si hay más de una llamada recursiva por rama del condicional.

1. Recursión en cascada: es cuando en cada rama hay más de una llamada a la función recursiva, su complejidad en término de llamadas recursivas será una función exponencial de la profundidad del árbol de las llamadas.

2. Recursión anidada: es cuando alguna llamada recursiva recibe como parámetro a una llamada recursiva, su complejidad en término de llamadas recursivas resultará mucho más difícil de calcular.

3. Recursión mutua: se da cuando dos funciones son recurrentes entre sí.


FUNCIÓN RECURSIVA

Las funciones recursivas se componen de:

Caso base: una solución simple para un caso particular (puede haber más de un caso base). La secuenciación, iteración condicional y selección son estructuras válidas de control que pueden ser consideradas como enunciados.

NOTA: Regla recursiva Las estructuras de control que se pueden formar combinando de manera válida la secuenciación, iteración condicional y selección también son válidos.

Caso recursivo: una solución que involucra volver a utilizar la función original, con parámetros que se acercan más al caso base. Los pasos que sigue el caso recursivo son los siguientes:

1. El procedimiento se llama a sí mismo.2. El problema se resuelve, resolviendo el mismo problema pero

de tamaño menor.3. La manera en la cual el tamaño del problema disminuye

asegura que el caso base eventualmente se alcanzará.


ASIGNACION ESTATICA Y DINAMICA DE LA MEMORIA

Uso de la memoria en Tiempo de ejecución.

Al ejecutar una aplicación Java, la memoria usada por la aplicación se divide en distintas zonas:

Fig. 3 Esquema en el que se divide la memoria en un programa recursivo.

Programas:

En una zona de memoria se cargan los bytecodes correspondientes a las clases que forman parte de la aplicación.

Zona estática.

Donde se almacenan las variables de clase (declaradas con static) Datos compartidos (datos globales). Datos que han de mantenerse más allá de la duración de la invocación de

un método o de la vida de un objeto.Pila.

Es una colección lineal, dinámica y homogénea, en la que los elementos se insertan y se extraen por el mismo extremo. También conocida como estructura LIFO (Last In, First Out).

Operaciones:Crear pilaMeter SacarDestruir pilaEstar vacía


CÓMO FUNCIONAN LOS ALGORITMOS RECURSIVOS

Para entender cómo funciona la recursividad es necesario que tengamos presente las reglas y los tipos de pasaje de parámetros provistos en JAVA.

Se descompone el problema en problemas de menor complejidad (algunos de ellos de la misma naturaleza que el problema original).

Se resuelve el problema para, al menos, un caso base.

Se compone la solución final a partir de las soluciones parciales que se van obteniendo.

Ejemplo

static int potencia (int x, int n) { if(n==0) // Caso base return 1; else // Caso general return x * potencia(x, n-1); }


Proceso del programa para calcular la potencia de 53.

DISEÑO DE ALGORITMOS RECURSIVOS

1.- Resolución de problemas para los casos base:

Sin emplear recursividad. Siempre debe existir algún caso base.

2.- Solución para el caso general:

Expresión de forma recursiva. Puede incluirse pasos adicionales (para combinar las soluciones

parciales).

Siempre se debe avanzar hacia un caso base:Las llamadas recursivas simplifican el problema y, en última instancia, los casos base nos sirven para obtener la solución.

• Los casos base corresponden a situaciones que se pueden resolver con facilidad.

• Los demás casos se resuelven recurriendo, antes o después, a alguno(s) de los casos base.

De esta forma, podemos resolver problemas complejos que serían muy difíciles de resolver directamente.


PROPIEDADES DE ALGORITMOS RECURSIVOS:

Un requisito importante para que sea correcto un algoritmo recursivo es que no genere una secuencia infinita de llamadas así mismo. Claro que cualquier algoritmo que genere tal secuencia no termina nunca.

Una función f se debe llamar así mismo y no debe de contener ningún bucle repetitivo (while, do while o for).

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.

Si en esta salida no puede calcularse ninguna función recursiva. Cualquier caso de definición recursiva o invocación de un algoritmo recursivo tiene que reducirse a la larga a alguna manipulación de uno o casos más simples no recursivos.

La recursividad es una técnica de programación importante. Se utiliza para realizar una llamada a una función desde la misma función. Como ejemplo útil se puede presentar el cálculo de números factoriales. Él factorial de 0 es, por definición, 1. Los factoriales de números mayores se calculan mediante la multiplicación de 1 * 2 *..., incrementando el número de 1 en 1 hasta llegar al número para el que se está calculando el factorial.

EJEMPLO PROGRAMA QUE CALCULA EL FACTORIAL.


PSEUDOCÓDIGO FACTORIALInicio Variables N,Fact,aux. Imprimir "Introduce el número: " Leer N aux= n-1. fact=n Hacer fact=fact * aux. Hasta que aux=1 Imprimir "El factorial de ", n, "es:", factFin.

Factorial calculado de forma recursiva:

Static int factorial (int n) { Int resultado;

if (n==0) // Caso base resultado=1; else // Caso general resultado=n*factorial(n-1); return resultado; }

EJEMPLO FACTORIAL DEL NUMERO 4


Prueba de escritorio y código.

Esta es la definición recursiva de la función factorial, ya que se define en términos de sí misma. La primera regla de la definición, o caso base, establece la condición de terminación. Las definiciones recursivas nos permiten definir un conjunto infinito de objetos mediante una sentencia finita.


public int factorial (int n)

{

if (n<=0)

{

return 1;

}

else

{

return n*factorial(n-1);

}

}

return 4* factorial ( 4 – 1);


4 3 2 1 0



return 1;

1

1

2

6

24

EJEMPLO DE RECURSIVIDAD DE LA SERIE FIBONACCI

SERIE FIBONACCI1, 1, 2, 3, 5, 8, 13, 21, 34, . . . . . .N

¿Qué relación tiene la serie fibonacci?

Esta serie tiene como relación la suma de 2 números, la cual comienza con una suma simple de c=a+b(1+0=1) después se toma el elemento b (0) y se suma con el resultado (1) y así sucesivamente, ejemplo:

Una sucesión de Fibonacci es aquella cuya ley de recurrencia es:

an = an-1 + an-2

Es decir, cada término de la sucesión se obtiene sumando los dos anteriores. Para empezar a construirla necesitamos, por tanto, dos números de partida, a1 y a2. De esta forma, a3 sería a2 + a1 ; a4 sería a3 + a2 y así sucesivamente.

La más conocida es la que tiene a1 = 1 y a2 = 1, cuyos términos son:

1 1 2 3 5 8 13 21 34 55 89 144 233 377 ...

Números cuales todos son los que son conocidos como Números de Fibonacci.

Los términos de cualquier sucesión de Fibonacci tienen la particularidad de que el cociente entre dos términos consecutivos se aproxima al Número de Oro (1.6180339887499...), es decir, el límite de los cocientes an+1/an tiende al Número de Oro cuando n tiende a infinito.


http://4.bp.blogspot.com/-7seql5fOBAA/Tg7AVTvKnYI/AAAAAAAAACc/an_s-U14bTQ/s1600/fibonacci.jpg

Fórmula recursiva

fibonacci(n) = fibonacci (n - 1) + fibonacci (n - 2)

Caso base: Fib (0)=0; Fib (1)=1Caso recursivo: Fib (i) = Fib (i -1) + Fib(i -2)

public static int fib(int n){

if (n <= 1) return n; //condición base

else return fib(n-1)+fib(n-2); //condición recursiva}


Y nos muestra en pantalla:

CADENAS RECURSIVAS O RECURSIVIDAD INDIRECTA

Una función recursiva no necesita llamarse a sí misma de manera directa. En su lugar, puede hacerlo de manera indirecta.

Pueden incluirse más de dos rutinas en una cadena recursiva. Así, una rutina a puede llamar a b, que llama a c, ..., que llama a z, que llama a a. Cada rutina de la cadena puede potencialmente llamarse a sí misma y, por lo tanto es recursiva. Por supuesto, el programador debe asegurarse de que un programa de este tipo no genere una secuencia infinita de llamadas recursivas.

Son algoritmos donde una función provoca una llamada a sí misma de forma indirecta, a través de otras funciones.


Ejemplo recorrido para Fibonacci del número 3

Una función recursiva no necesita llamarse a sí misma de manera directa. En su lugar, puede hacerlo de manera indirecta como en el siguiente ejemplo:

a (formal parameters) b (formal parameters)

{ {

. .

b (arguments); a (arguments);

. .

} /*fin de a*/ } /*fin de b*/

La recursividad indirecta es aquella que se llama asi mismo pero también puede llamar a otro método recursivo dentro del primero método, como en el ejemplo anterior el método a llama el método b dentro de su estructura y el método b llama al método a también dentro de su estructura. Claro que un método recursivo también tienen que ser finito.

Conclusión:

Cuando un procedimiento incluye una llamada a sí mismo se conoce como recursión directa.

Cuando un procedimiento llama a otro procedimiento y éste causa que el procedimiento original sea invocado, se conoce como recursión indirecta.

NOTA: Cuando un procedimiento recursivo se llama recursivamente a si mismo varias veces, para cada llamada se crean copias independientes de las variables declaradas en el procedimiento.


Un ejemplo de recursividad indirecta es el de calcular si un número es primo o no.

public class Primo { static int z=1; static int pri(int q) { z++; if(z<x) return sec(q); else return 0; } static int sec(int y) { if(y%z==0) return 1; else return pri(y); } public static void main(String arg[]) { int x; x=Integer.parseInt(JOptionPane.showInputDialog(null,"Introdusca Numero")); if(pri(x)==0) JOptionPane.showMessageDialog(null,"El Numero ES Primo"); else JOptionPane.showMessageDialog(null,"El Numero NO es Primo"); }}

En el código anterior la clase primo está constituida por dos métodos recursivos los cuales son pri(int q) con parameto entero q y el segundo es sec(int y) con parámetro y, que al momento de ejecutarlo, en el main se crea una variable local x la cual nos pide un valor, después de asignarle un valor entero a x entrasmos una condición en la cuan dentro de la condición mandamos a llamar al primero método (pri(x)) el cual le pasamos el valor de x y q lo recibe y dentro del primer método hay otra condición si es verdadera manda a llamar al segundo método (sec(q)) al cual le pasamos el valor de q y dentro del segundo método madamos a llamar el primer método y asi sucesivamente hasta que la recursividad llegue a su fin y nos devuelva un valor.

PROBLEMA DE LAS TORRES DE HANÓI:


Este problema es uno de los ejemplos clásicos de recursividad.

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 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?

PASANDO DIRECTAMENTE EL ARA DE A A C.


¿CÓMO SE RESOLVERÍA EL CASO EN QUE HUBIERA DOS 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 tres aros?

RESOLUCIÓN DE UN 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).


“Dividir para vencer”

Muchas veces es posible dividir un problema en subproblemas más pequeños, generalmente del mismo tamaño, resolver los subproblemas y entonces combinar sus soluciones para obtener la solución del problema original.

Dividir para vencer es una técnica natural para las estructuras de datos, ya que por definición están compuestas por piezas. Cuando una estructura de tamaño finito se divide, las últimas piezas ya no podrán ser divididas.

CÓDIGO FUENTE DE PROGRAMA DE LAS TORRES DE HANÓI.

public class Torres{ static int contador=0,discos=0; String cadena=" "; public int moverdisco(int a, int b) { cadena=cadena+"Mover Disco de la Torre (("+a+")) Hacia la torre (("+b+"))\n"; JOptionPane.showMessageDialog(null,cadena); contador++; return 0; } public int movertorre(int n, int desde, int hacia, int piv) { if(n<2) { moverdisco(desde,hacia); } else { movertorre(n-1,desde,piv,hacia); moverdisco(desde,hacia); movertorre(n-1,piv,hacia,desde); } return 0; } public static void main(String args []) { Torres chale=new Torres(); discos=Integer.parseInt(JOptionPane.showInputDialog(null,"Numero de Discos","TORRES DE HANOI", JOptionPane.INFORMATION_MESSAGE)); JOptionPane.showMessageDialog(null,"Se Resolverá para "+discos+" Disco (s)","TORRE DE HANOI",JOptionPane.INFORMATION_MESSAGE); chale.movertorre(discos,1,3,2); JOptionPane.showMessageDialog(null,"Resuelto en "+contador+" movimiento(s) ","TORRES DE HANOI",JOptionPane.INFORMATION_MESSAGE); }}


RECURSION VS. ITERACIÓN

RepeticiónIteración: ciclo explícitoRecursión: repetidas invocaciones a métodoTerminaciónIteración: el ciclo termina o la condición del ciclo falla.Recursión: se reconoce el caso base.

En ambos casos podemos tener ciclos infinitosConsiderar que resulta más positivo para cada problemala elección entre eficiencia (iteración) o una buena ingeniería de software, La recursión resulta normalmente más natural.

Las principales cuestiones son la claridad y la eficiencia de la solución.

En general: Una solución no recursiva es más eficiente en términos de tiempo y espacio de computadora.

La solución recursiva puede requerir gastos considerables, y deben guardarse copias de variables locales y temporales.

Aunque el gasto de una llamada a una función recursiva no es peor, esta llamada original puede ocultar muchas capas de llamadas recursivas internas.

El sistema puede no tener suficiente espacio para ejecutar una solución recursiva de algunos problemas.

Una solución recursiva particular puede tener una ineficiencia inherente. Tal ineficiencia no es debida a la elección de la implementación del

algoritmo; más bien, es un defecto del algoritmo en sí mismo. Un problema inherente es que algunos valores son calculados una y otra

vez causando que la capacidad de la computadora se exceda antes de obtener una respuesta.

La cuestión de la claridad en la solución es, no obstante, un factor importante.

En algunos problemas una solución recursiva es más simple y más natural de escribir, como se observa en las siguientes funciones.

En algunos casos una solución recursiva es más simple y más natural de escribir.


ANÁLISIS DE COMPLEJIDAD EN RECURSIVIDAD

• El análisis de complejidad de tiempo y espacio de algoritmos recursivos depende de dos factores:

– La profundidad (el número de niveles) de las llamadas recursivas hechas antes de llegar a la terminación. A mayor profundidad, mayor espacio y tiempo de ejecución.

– La cantidad de recursos consumidos en cada nivel de la recursión.

• La ejecución de un programa se puede diagramar trazando la ruta de ejecución y creando una jerarquía con la llamada inicial en el tope.

• El diagrama resultante puede utilizarse para analizar el tiempo y el espacio del algoritmo.


RECURSIVIDAD ARBOLES

Los arboles representan las estructuras dinámicas y no lineales más interesantes más interesantes de la computación. Las estructuras balanceadas o AVL en la estructura de datos más eficiente para trabajar en la memoria rápida de la computación. Por otra parte, la estructura de datos Arboles-B, representa la estructura de datos más eficiente para trabajar en memoria secundaria – dispositivos de almacenamiento secundario-.

Los árboles son una estructura inherentemente recursiva y todas las operaciones que se realizan en árboles se deben programar en forma recursiva. A diferencia de otras estructuras en las cuales las operaciones se pueden implementar tanto en forma recursiva como en forma iterativa, independiente de las diferencias que se pueden observar en cuanto a eficiencia en los árboles se puede trabajar en forma recursiva.

RECURSIVIDAD EN ORDENACIÓN RÁPIDA (QUICKSORT)

El algoritmo conocido como Quicksort (ordenación rápida), recibe su nombre de su autor, Tony Hoare.

La idea del algoritmo es simple, se basa en la división de particiones de la lista a ordenar. El método es, posiblemente, el más pequeño de código, más elegante, más interesante, más rápido y eficiente de los algoritmos de ordenación.


El método se basa en dividir los n elementos de la lista a ordenar en 3 partes o particiones: una partición izquierda, una partición central que solo contiene un elemento llamado pivote, y una partición derecha. La partición o división se hace de tal forma que todos los elementos de la primera sublista (partición izquierda) son menores que todos los elementos de la sublista (partición derecha). Las dos sublista se ordenan entonces independientemente.

La lista se divide en dos particiones (sublistas) eligiendo un elemento de la lista que se utiliza como pivote o elemento de partición. Si se elige una lista cualquiera con los elementos ordenados aleatoriamente, se puede elegir cualquier elemento de la lista como elemento pivote, por ejemplo, el primer elemento de la lista. Si la lista tiene algún orden parcial, que se conoce, se puede tomar otra decisión para el pivote. Idealmente, el pivote se debe elegir de modo que se divida la lista exactamente por la mitad, de acuerdo al tamaño relativo de las claves. Por ejemplo si se tiene una lista de elementos del 0 al 10, el pivote podrían ser el 5 o 6.


Una vez que el pivote ha sido elegido se utiliza para ordenar la lista en dos sublistas: una tiene todos los elemento menores que el pivote y la otra partición todos los mayores o iguales que el pivote. Estas dos listas parciales se ordenan recursivamente, utilizando el mismo algoritmo, es decir, se llama sucesivamente al propio algoritmo Quitsort. La lista final ordenada se consigue concatenando la primera sublista, el pivote y la segunda sublista, en ese orden, es una única lista.


ESTE PROGRAMA ES UN METODO DE ORDENAMIENTO RAPIDO CON RECURSIVIDAD TE ORDENA DE MENOR A MYOR DE UNA SERIE DE NUMEROS ENTEROS POSITIVOS.

public class Quicksort { public void captura() { int n, a[]; String c=""; n=Integer.parseInt(JOptionPane.showInputDialog(null,"Cuantos elementos a ordenar")); a=new int[n]; for(int x=0; x<n; x++) { a[x]=Integer.parseInt(JOptionPane.showInputDialog(null,"Introdusca el numero "+x));

if(x==n-1) quicksort(a,0,n-1); } c="Los numeros ordenados son\n"; for(int x=0; x<n; x++) { c=c+"Array["+x+"]="+a[x]+"\n"; } JOptionPane.showMessageDialog(null,""+c); }

void quicksort(int a[], int primero, int ultimo) { int i, j, central;

int pivote; central=(primero + ultimo)/2; pivote=a[central]; i=primero; j=ultimo; do { while (a[i]<pivote) { i++; } while (a[j]>pivote) { j--; } if(i<=j) { int tmp; tmp=a[i]; a[i]=a[j]; a[j]=tmp; i++; j--; } } while(i<=j); if(primero<j) quicksort(a,primero,j); if(i<ultimo) quicksort(a,i,ultimo); } public static void main(String ar[]) { Quicksort ob=new Quicksort();

ob.captura(); }}



Ejemplos de recursividad

PROGRAMA RECURSIVO QUE HACE EL LLENADO DE UN ARREGLO Y LO IMPRIME EN UNA SOLA VENTANA Y TAMBIEN LA IMPRIME POR ARREGLO.

public class Arreglo { static String a="",Llena[];; static int x,z=-1,tam; static String llena(int w) { if(w==0); else { z++; Llena[z]=JOptionPane.showInputDialog(null,"Introdusca Numero"); a=a+"Arreglo ["+z+"] = "+Llena[z]+"\n"; llena(w-1); } return a; } static void impri() { for(int s=0;s<tam;s++) { JOptionPane.showMessageDialog(null,"Arreglo ["+s+"] = "+Llena[s]); } } public static void main(String a[]) { tam=Integer.parseInt(JOptionPane.showInputDialog(null,"CUANTOS NUMERO DESEA AGREGAR")); Llena= new String [tam]; JOptionPane.showMessageDialog(null,"EL ARREGLO ES : \n\n"+llena(tam)); impri(); }}


CALCULA LAS COMBINACIONES MATEMATICAS nCr

public class Combinaciones_n_C_r { static int com(int n,int r) { if(r==0 || n==0) { return 1; } else { if(r==0) { return n; } else { return com(n-1,r)+com(n-1,r-1); } } } public static void main (String arg[]) { int a,b; a=Integer.parseInt(JOptionPane.showInputDialog(null,"Introduaca Numero N")); b=Integer.parseInt(JOptionPane.showInputDialog(null,"Introduaca Numero r")); JOptionPane.showInputDialog(null,"Combunatorio "+a+" C "+b+" = "+com(a,b)); }}


ESTE PROGRAMA IMPRIME HOLA 3 VECES Y LUEGO SE SALE DICIENDO SHAO.

public class Impre_Hola { void imp(int z) { if(z<3) { JOptionPane.showMessageDialog(null,"HOLA "); imp(z+1); } else JOptionPane.showMessageDialog(null,"SHAO"); } public static void main(String arg[]) { Impre_Hola o=new Impre_Hola(); o.imp(0); }}


ESTE PROGRAMA CALCULA EL MAXICO COMUN DIVISOR DE 2 NUMERO POSITIVOS.

public class MaxCD { static int MCD(int a, int b) { if(a!=b) { if(a>b) { a=a-b; } else { b=b-a; } return MCD(a,b); } return a; } public static void main(String arg[]) { MaxCD a=new MaxCD(); int p,q; p=Integer.parseInt(JOptionPane.showInputDialog(null,"Inttodusca primer numero")); q=Integer.parseInt(JOptionPane.showInputDialog(null,"Introdusca segundo numero")); JOptionPane.showMessageDialog(null,"el maximo comun divisor es: " +MCD(p, q)); }}


ESTE PROGRAMA CALCULA EL MAXIMO COMUN DIVISOR DE 2 NUMERO ENTEROS POSITIVOS (DIFERENTE LOGICA).

public class MaxComDiv { static int mcd(int m,int n) { if(n<=m && m%n==0) return n; else if(m<n) return mcd(n,m%n); else return mcd(n,m%n); } public static void main(String arg[]) { MaxComDiv o = new MaxComDiv(); int m,n; do { m=Integer.parseInt(JOptionPane.showInputDialog(null,"INTRODUSCA EL PRIMER NUMEO")); n=Integer.parseInt(JOptionPane.showInputDialog(null,"INTRODUSCA SEGUNDO NUMERO")); } while(n<=0 || m<=0); JOptionPane.showMessageDialog(null,"EL MAXIMO COMUN DIVISOR ES: "+mcd(m,n)); }}


ESTE PROGRAMA BUSCA EL MAYOR DE N NUMEROS ENTEROS.

public class Mayor_n { static int i=-1,tn,a[],x; public void cap() { tn=Integer.parseInt(JOptionPane.showInputDialog(null,"CUANTOS NUMERO")); a=new int [tn]; JOptionPane.showMessageDialog(null,"EL MAYOR ES "+mayor()); } static int mayor() { i++; if(i<tn) { a[i]=Integer.parseInt(JOptionPane.showInputDialog(null,"Intodusca Numero")); if(x<a[i]) { x=a[i]; return mayor(); } return mayor(); } return x; } public static void main(String arg[]) { Mayor_n o=new Mayor_n(); o.cap(); }}


ESTE PROGRAMA CALCULA EN MENOR DE N NUMERO POSITIVOS.

public class Menor_n { static int i=-1,tn,a[],x; public void cap() { tn=Integer.parseInt(JOptionPane.showInputDialog(null,"CUANTOS NUMERO")); a=new int [tn]; JOptionPane.showMessageDialog(null,"EL MENOR ES "+menor()); } static int menor() { i++; if(i<tn) { a[i]=Integer.parseInt(JOptionPane.showInputDialog(null,"Intodusca Numero")); if(i==0) { x=a[i]; return menor(); } else { if(x>a[i]) { x=a[i]; return menor(); } else { return menor(); } } } return x; } public static void main(String arg[]) { Menor_n o=new Menor_n(); o.cap(); }}

ESTE PROGRAMA CALCULA SI UN NUMERO ES PAR O IMPAR.


public class Par_Inpar { public int pi(int x) { if(x%2==0) { return 0; } else { return 1; } } public static void main(String arg[]) { int z; Par_Inpar p=new Par_Inpar(); z=Integer.parseInt(JOptionPane.showInputDialog(null,"INTRODUSCA NUMERO")); if(p.pi(z)==0) { JOptionPane.showMessageDialog(null,"EL NUMERO ES PAR"); } else { JOptionPane.showMessageDialog(null,"EL NUMERO NO PAR"); } }}

ESTE PROGRAMA CALCULA UN NUMERO ELEVADO A LA POTENCIA N ( XN )


public class Potencia_de_un_numero { static int potencia(int x,int y) { if(y==0) { return 1; } else { return x*potencia(x,y-1); } } public static void main(String arg[]) { int a,b; a=Integer.parseInt(JOptionPane.showInputDialog(null,"Introduaca Numero")); b=Integer.parseInt(JOptionPane.showInputDialog(null,"Introduaca Potencia")); JOptionPane.showInputDialog(null,"Resulatado "+a+" ^ "+b+" = "+potencia(a,b)); }}

ESTE PRORAMA CALCULA LA SUMA DE N NUMERO ENTEROS POSITIVOS.

public class Sum_n { int z; public int sum(int x) { z=Integer.parseInt(JOptionPane.showInputDialog(null,"Introdusca Nuemro"));


if(x==1) return z; else return z+ sum(x-1); } public static void main (String arg []) { int a; Sum_n ob= new Sum_n (); a=Integer.parseInt(JOptionPane.showInputDialog(null,"CUANTOS NUMEROS"));

JOptionPane.showMessageDialog(null,"LA SUMA ES: "+ ob.sum(a)); }}

ESTE PROGRAMA TE INPRIME EL ABECEDARIO EN MAYUSCULA DE LA A - Z

public class alfabeto { static String a=""; public static void main (String [] arg) { metodoA('Z'); JOptionPane.showMessageDialog(null,a); }


static void metodoA(char c) { if (c>='A') { metodoB(c); a=a+" "+c+" "; } } static void metodoB(char c) { metodoA(--c); }}

BIBLIOGRAFÍA


o Allen Weiss, Mark. Estructura de datos en Java. Addison Wesley. pp. 165-201.

o Joyanes, Aguilar Luis. Fundamentos de programación:Algoritmos, Estructura de datos y objetos. Mc Graw Hill. pp. 537-568.

o Cairo, Osvaldo. Estructura de datos. Mc Graw Hill. pp. 109-137.

o http://ocw.udem.edu.mx

o http://www.itescam.edu.mx/principal/sylabus/fpdb/recursos/r4886.PDF


http://ocw.udem.edu.mx/

ii. recursividad

Documents