Presentacin de PowerPoint

ALGORITMOS Y ESTRUCTURAS DE DATOS RecursividadProf. Lizardo Silva Ubaldo AED-LSU1AED - LSUAgendaRecursin Cmo funciona la Recursin ?Las Torres de HanoiAlgoritmos Recursivos

2EDA - LSURecursinLa recursin es una tcnica de programacin en la que un mtodo se llama a si mismo.

La recursin permite definir un objeto (funciones, problemas, estructuras de datos) en trminos de s mismo.

Un procedimiento/funcin que se llama a s mismo es recursivo.

Un objeto recursivo es aquel que forma parte de si mismo. 3EDA - LSURecursinEjemplos: f(0) = 0 y f(x) = 2 f(x-1) + x2

3! = 3 * 2!

Son funciones que se definen en trminos de si misma.

4EDA - LSURecursinLa recursividad puede ser Directa: Cuando el procedimiento se llama a si mismo.

Proc. P

Llamada a P5EDA - LSURecursinIndirecta Cuando la llamada no es directamente a si mismo

Llamada a QLlamada a PProc. PProc. QLlamada a QLlamada a VLamada a PProc. PProc. QLlamada a QProc. V6EDA - LSURecursinPara obtener una solucin se deben cumplir las siguientes condiciones:

Caso base (Estado base, estado bsico).- Es el valor que permite obtener una solucin directa, es la parte que no es recursiva. Es necesario que exista para que la funcin recursiva termine. Progresin.- Para los casos que deben resolverse recursivamente, la llamada recursiva siempre debe tender al caso base78Ejemplo: Factorial de nPor definicin n! = 1*2*3**(n-1)*n con 0! = 1 y 1! = 13! = 3*2! 2! = 2*1! 1! = 1*0! Caso base0! = 1 Generalizando: n! = 1 si n= 0 n*(n-1)! si n > 0RecursinEDA - LSU8EDA - LSURecursin

910Funcion factorial (n)si n = 0entonces resultado = 1sino resultado = n * Factorial(n-1)FsiRetornar resultado Fin funcionEjemploEDA - LSU1011 int factorial(int n){ int resultado; if(n==0) resultado=1; else resultado = n*factorial(n-1); return resultado; }EjemploEDA - LSU111112int factorial(int n){ int resultado; if(n==0) resultado=1; else resultado = n*factorial(n-1); return resultado; }Ejemplo int factorial(int n){ int resultado; if(n==0) resultado=1; else resultado = n*factorial(n-1); return resultado; }int factorial(int n){ int resultado; if(n==0) resultado=1; else resultado = n*factorial(n-1); return resultado; }int factorial(int n){ int resultado; if(n==0) resultado=1; else resultado = n*factorial(n-1); return resultado; }EDA - LSU121213La recursinPermite crear algoritmos claros y concisosEs costosa en tiempo de ejecucin y espacio usadoLa recursividad se puede simular usando algoritmos iterativos.

RecursinEDA - LSU1314Regla de diseo para funciones recursivasSuponga que todas las llamadas recursivas funcionan

Es importante porque al disear rutinas recursivas no necesitamos conocer los detalles del funcionamiento interno, siempre suponemos que funciona correctamenteComo funciona la RecursividadEDA - LSU15La recursin tiene como principal problema el costo oculto de su funcionamiento interno (control de puntos de llamadas, control de puntos de retorno, valores de retorno, etc.)Como funciona la RecursividadEDA - LSUEDA - LSUPaso N PilaFactorial 0 4 14 4 4 * fact(3) 2 3 4, 33 * fact(2) 3 2 4, 3, 22 * fact(1) 4 1 4, 3, 2, 11 * fact(0) 5 0 4, 3, 2, 11 6 1 4, 3, 21 * fact(0) = 1*1 = 1 7 2 4, 32 * fact(1) = 2*1 = 2 8 3 4 3 * fact(2) = 3*2 = 6 9 4 4 * fact(3) = 4*6 = 24

Ejemplo161617Internamente se utiliza una estructura tipo pila para guardar valores de variables y constantes locales del programa o subprograma que efecta la llamada.

De esta manera, una vez concluida la ejecucin, se puede continuar la ejecucin recuperando los valores necesarios de la pila.Como funciona la RecursividadEDA - LSU1718Se guarda una referencia a la siguiente instruccin a ejecutar.

Al retornar se toma la imagen del tope de la pila y se contina operando.

Esto se repite hasta que la pila est vaca. Como funciona la RecursividadEDA - LSU1819Metodo Factorial (n)fact =1mientras n > 0 fact =fact * n n =n - 1fmientrasretornar factFin_metodo

La alternativa iterativaEDA - LSU19EDA - LSUfuncin Impar(N) si n = 0 entonces Impar = falso sino Impar = Par(N - 1)finfuncinfuncin Par(N) si n = 0 entonces Par = falso sino Par = Impar(N - 1)Fin_funcin Recursividad Indirecta20EDA - LSUEs un juego matemtico que consiste en tres varillas verticales y un nmero indeterminado de discos que determinarn la complejidad de la solucin. No hay dos discos iguales y estn colocados de mayor a menor tamao en una varilla, no se puede colocar ningn disco mayor sobre uno menor a l en ningn momento. Las Torres de Hanoi 21EDA - LSUEl juego consiste en pasar todos los discos de la varilla A hacia la varilla C, colocados de mayor a menor ascendentemente

Juego: http://www.uterra.com/juegos/torre_hanoi.htmLas Torres de Hanoi

22EDA - LSULa recursividad de cola, se presenta cuando se usa solo una llamada recursiva en cada extremo del mtodo o modulo.En este caso la llamada recursiva es la ultima sentencia del mtodo y adems es la nica llamada recursiva.

Recursividad de Cola23EDA - LSUEjemplo: public int fact(int n) { if (n == 0) return 1; else return fact(n - 1) * n; }

Recursividad de Cola24EDA - LSULa recursividad anidada, se presenta cuando el mtodo se define en trminos de si mismo y adems cuando se utiliza esta llamada como un parmetro. Ejemplo:

Recursividad Anidada

25EDA - LSUCalcular la potencia de un numeroInvierta un numeroConvertir un numero de base 10 a base 2

Ejercicios26EDA - LSUConstruir el pseudocodigo para el siguiente casofi(x,y)= 0 si i = 0fi(x,y) = - xy+1 + yx-2- xy+3+yx-4-. Si i> 0

f4(x,y) = f3(x,y) + yx-4f3(x,y) = f2(x,y) - xy+3f2(x,y) = f1(x,y) + yx-2f1(x,y) = f0(x,y) - xy+1f0(x,y) = 0Ejercicios27EDA - LSUmetodo funcionxy(i,x,y) si i = 0 entonces funcionxy = 0 sino si (i mod 2) = 0 entonces funcionxy=funcionxy(i-1,x,y)+yx-i sino funcionxy=funcionxy(i-1,x,y)-xy+i fsifsifmetodo Ejercicios28