RECURSIVIDAD

EQUIPO 1 Integrantes: CARLOS ALBERTO NGEL NGEL ANTONIO MARCOS MOSSO ALEJANDRO SILVA JIMNEZ RAL MORENO ESPINOZA DANIEL ESPINOZA BAUTISTA EVA SEGURA BLAS JOHNNY AYVAR DAZ

1. Introduccin
Contenido de la exposicin El objetivo de la exposicin es explicar de manera breve y precisa como funciona la recursividad dentro del mbito de la programacin, conociendo en si su significado, cuando es necesario utilizarlo y para que nos sirve, cuales son sus ventajas y desventajas, entre otras que se vern a lo largo de la exposicin.

1. Introduccin
Manejo de la recursividad (contenido)
Tcnica de programacin Tipos de recursividad Cuenta con ciertas caractersticas distintivas

RECURSIVIDAD

PROCEDIMIENTOS RECURSIVOS

Recursividad simple Recursividad mltiple Recursividad anidada Recursividad cruzada o indirecta

Aplicando la recursividad
EJEMPLOS

2. Recursividad
Qu es la recursividad?

La recursividad tambin conocida como recursin es un concepto muy amplio, con muchas variantes y aparece en numerosas actividades de la vida diaria.
La recursividad como tcnica de programacin puede ser usada para implementar estructuras de repeticin (ciclos) de una manera distinta. Permitiendo que un bloque de instrucciones se ejecute n veces. La recursin es recurso muy poderoso que permite expresar soluciones simples y naturales a cierto tipo de problemas. Es importante considerar que no todos los problemas son naturalmente recursivos, algunos si lo son y otros no.

En Java los mtodos pueden llamarse a s mismos. Si dentro de un mtodo existe la llamada a s mismo decimos que el mtodo es recursivo.

2. Recursividad
Un ejemplo muy claro y sencillo de recursividad es la artesana rusa llamada muecas de Matrushka.

2. Recursividad
Caractersticas Las funciones recursivas se componen de: Caso base: una solucin simple para un caso particular. La secuenciacin, iteracin condicional (if-else) y seleccin (switch) son estructuras de control que se pueden considerar para resolver el caso base.

Caso recursivo: una solucin que involucra volver a utilizar la funcin original, con parmetros que se acerquen mas al caso base. Pasos en el caso recursivo:
1. 2. 3. El procedimiento se llama a si mismo El problema se resuelve, resolviendo el mismo problema pero de menor tamao. La manera en la cual el tamao del problema disminuye asegura que el caso base eventualmente se alcanzara.

2. Recursividad
Verificacin de procesos recursivos

Mtodo de las tres preguntas

La pregunta Caso-Base: Existe una salida no recursiva o caso base del subalgoritmo? Adems, el subalgoritmo funciona correctamente para ella? La pregunta Ms-pequeo: Cada llamada recursiva se refiere a un caso ms pequeo del problema original? La pregunta Caso-General: es correcta la solucin en aquellos casos no base?

2. Recursividad
Escritura de programas recursivos

1.-Obtencin de una definicin exacta del problema 2.-Determinar el tamao del problema completo que hay que resolver Parmetros en la llamada inicial 3.-Resolver el(los) casos bases o triviales (no recursivos). 4.-Resolver el caso general en trminos de un caso ms pequeo (llamada recursiva).

Algo muy importante a tener en cuenta cuando usemos la recursividad es que es necesario asegurarnos que llega un momento en que no hacemos ms llamadas recursivas. Si no se cumple esta condicin el programa nunca terminar.

2. Recursividad
Por que escribir programas recursivos?

Son mas cercanos a la descripcin matemtica. Generalmente mas fciles de analizar Se adaptan mejor a las estructuras de datos recursivas. Los algoritmos recursivos ofrecen soluciones estructuradas, modulares y elegantemente simples.

2. Recursividad
Cundo usar recursividad?

Para simplificar el cdigo. Cuando un problema es casi irresoluble con las estructuras iterativas Cuando la solucin de un problema se puede hallar solucionando el mismo problema pero con un caso de menor tamao. Cuando la estructura de datos es recursiva ejemplo : rboles.
Cundo no usar recursividad?
Cuando los mtodos usen arreglos largos. Cuando el mtodo cambia de manera impredecible de campos. Cuando las iteraciones sean la mejor opcin.

2. Recursividad
Tipos de recursividad Podemos distinguir dos tipos de recursividad:
Directa: Cuando un subprograma se llama a si mismo una o mas veces directamente. Indirecta: Cuando se definen una serie de subprogramas usndose unos a otros, es decir, el subprograma llama a otro subprograma, y este en algn momento, llama nuevamente al primero.

Procedimientos Recursivos
Recursividad Simple: Aquella en cuya definicin slo aparece una llamada recursiva. Se puede transformar con facilidad en algoritmos iterativos.

Recursividad Mltiple: Se da cuando hay ms de una llamada a s misma dentro del cuerpo de la funcin, resultando ms difcil de hacer de forma iterativa.

Procedimientos Recursivos
Recursividad Anidada: En algunos de los argumentos de la llamada recursiva hay una nueva llamada a s misma.

int Ack( int n, int m ) { if(n==0 ) return(m+1); else if(m==0) return(Ack(n-1,1)); return(Ack(n-1, Ack(n,m-1))); }

Procedimientos Recursivos
Recursividad cruzada o indirecta: Son algoritmos donde una funcin provoca una llamada a s misma de forma indirecta, a travs de otras funciones.
Ej: Par o Impar: int par( int nump ) { if(nump==0) return(1); return( impar(nump-1)); } int impar( int numi ) { if(numi==0) return(0); return( par(numi-1)); }

Consideraciones sobre procedimientos recursivos

Condiciones de limitacin. Debe designar un procedimiento recursivo para probar al menos una condicin que pueda poner fin a la recursividad. Uso de la memoria. La aplicacin tiene una cantidad de espacio limitada para las variables locales.

Consideraciones sobre procedimientos recursivos

Eficacia. Casi siempre se puede sustituir un bucle por la recursividad.

Recursividad mutua. Si dos procedimientos se llaman mutuamente, el rendimiento puede ser muy deficiente o incluso puede producirse un bucle infinito.

Consideraciones sobre procedimientos recursivos

Llamadas con parntesis. Cuando un procedimiento Function se llama a s mismo de manera recursiva, debe agregar parntesis detrs del nombre del procedimiento, aun cuando no exista una lista de argumentos. De lo contrario, se considerar que el nombre de la funcin representa al valor devuelto por sta.

Consideraciones sobre procedimientos recursivos

Pruebas Si escribe un procedimiento recursivo, debe probarlo minuciosamente para asegurarse de que siempre cumple ciertas condiciones de limitacin.

Torres de Hani
Una forma de resolver la colocacin de la torre es fundamentndose en el disco ms pequeo, en este caso el de hasta arriba. El movimiento inicial de este es hacia la varilla auxiliar. El disco nmero dos por regla, se debe mover a la varilla nmero tres. Luego; el disco uno se mueve a la varilla tres para que quede sobre el disco dos. A continuacin se mueve el disco que sigue de la varilla uno, en este caso el disco nmero tres, y se coloca en la varilla dos. Finalmente el disco nmero uno regresa de la varilla tres a la uno (sin pasar por la dos) y as sucesivamente. Es decir, el truco est en el disco ms pequeo.

Mediante Recursividad.
Este problema se suele plantear a menudo en mbitos de programacin, especialmente para explicar la recursividad. Si numeramos los discos desde 1 hasta n, y llamamos X a la primera pila de discos (origen), Z a la tercera (destino) e Y a la intermedia (auxiliar) y a la funcin le llamaramos hanoi (origen, auxiliar, destino), como parmetros, la funcin recibira las pilas de discos. El algoritmo de la funcin sera el siguiente:
1. Si origen == {0}: mover el disco 1 de pila origen a la pila destino (insertarlo arriba de la pila destino); terminar. 2. Si no: hanoi({0...n-1},destino, auxiliar) //mover todas las fichas menos la ms grande (n) a la varilla auxiliar 3. mover disco n a destino //mover la ficha grande hasta la varilla final 4. hanoi (auxiliar, origen, destino) //mover todas las fichas restantes, {0...n-1}, encima de la ficha grande (n) 5. terminar

Palndromos Un palndromo es una cadena que se lee (se escribe, en este caso) igual de izquierda a derecha que de derecha a izquierda. Escribir una funcin que determine cuando una cadena es o no un palndromo.

Solucin
esttica bool palindrome (Cad c, int limIzq, int limDer) si limIzq > limDer entonces regresa verdadero sino si c [limIzq] = c [limDer] entonces regresa palindrome (c, limIzq+1, limDer-1) sino regresa falso fin
22

Ejemplo: Serie de Fibonacci

Valores: 0, 1, 1, 2, 3, 5, 8...
Cada trmino de la serie suma los 2 anteriores. Frmula recursiva

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

Caso base: Fib (0)=0; Fib (1)=1 Caso recursivo: Fib (i) = Fib (i -1) + Fib(i -2)
public static int fib(int n){ if (n <= 1) return n; //condicin base else return fib(n-1)+fib(n-2); //condicin recursiva }
23

Ejemplo: Serie de Fibonacci

Traza del clculo recursivo Fib(3)

return

Fib(2)

Fib(1) return 1

return Fib(1) + Fib(0) return 1

24

return 0

Trampas sutiles: Cdigo ineficiente.

public int fib (int n) { if (n < 2) return 1; else return fib (n-2) + fib ( n-1); } public int fib (int n) { int f1 = 1, f2 = 1, nuevo; while (n > 2) { nuevo = f1 + f2; f1 = f2; f2 = nuevo; n--; } return f2; } fib (100) toma tan slo
unos microsegundos en dar el resultado

fib (100) toma 50 aos en dar el resultado

25

Serie fibonacci Iteracin vs recursin

70 60 50 40 30 20 10 0 0 -10
26

iteraciones recursividad

10

20

30

40

50

60

EJEMPLO: FACTORIAL

import javax.swing.*; public class Factorial { public static void main (String [] args) { String n=""; int fac=1,i=1,num; n=JOptionPane.showInputDialog("Ingrese un numero"); num=Integer.parseInt(n); if (num==0||num==1){ System.out.print("El facrotial de "+num+"es"+fac); } else { if (num>1) { while(num>=i) { fac=fac*i; i++; } System.out.print("El factorial es "+fac); } else{ System.out.print("Error numero tiene que ser mayor o igual a cero"); } } }
}