Definición Un método es recursivo si esta parcialmente definido en términos de si mismo. Un método recursivo permite la definición de soluciones mas cortas y eficientes. Ejemplo: definición de la función factorial N! = 1 para N=0 o N=1 N! = N*(N-1)! para N>1
Tipos de recursión Directa. El método contiene al menos una llamada a si mismo. Indirecta. Existe una secuencia de llamadas a métodos donde al menos una de estas llega al método inicial. // recursión directa public static int factorial(int n) { if (n<=1) return 1; else return n*factorial(n-1); } // recursion indirecta public static int que(int n) { if (n <= 1) return n; else if (n mod 2 ==0) return magia((int)n/2); else return 1+magia(n*3+1); } public static int magia(int n) { if (n==1) return 1; else if ((n mod 2)==1) return que(n-1); else return que((int)n/2); }
Procedimientos recursivos Visualizar todos los archivos almacenados en un disco. Definir una expresión en la gramática de un lenguaje de programación. Mostrar a todos los miembros de una familia representados en un árbol genealógico. Sumar todos los elementos de una lista de datos. Etc.
Mecánica de recursión Un método recursivo contiene dos elementos básicos que son fundamentales para su funcionamiento. Caso Base: Existe al menos una solución para algún valor determinado. Progreso: Cualquier llamada a si mismo debe progresar (acercarse) a un caso base. Define los elementos básicos de los ejemplos de la lamina anterior.
Demostración por inducción matemática La inducción matemática es una técnica para demostrar teoremas. Esta técnica puede ser usada para demostrar que los algoritmos recursivos funcionan correctamente. Algunas aplicaciones son demostraciones de teoremas que cumplen los números enteros positivos.
Ejemplo La suma de los primeros n números enteros positivos esta dada por los siguientes elementos básicos: Caso base: 1 cuando n=1 Progreso: n+suma de los primeros n-1 enteros positivos // suma de enteros recursiva int suma(int n){ if (n==1) return 1; else return n+suma(n-1); }
Demostración por inducción matemática Demostrar el caso base: es obvio que cuando n=1 el resultado=1 Asumir la hipótesis como válida para todos los valores de n>1 Demostrar que la fórmula el valida para n+1 (Gp:) Fórmula matemática (Gp:) n i= n(n+1)/2 i=1 (Gp:) S 1(1+1)/2 1(2)/2 2/2 1 (Gp:) n i= n(n+1)/2 i=1 (Gp:) S (Gp:) n+1 i= i=1 (Gp:) S (Gp:) n n+1 + i i=1 (Gp:) S
(Gp:) n n+1 + i= (n+1) + n(n+1)/2 i=1 = n+1 + (n2 +n)/2 = (2n +2 + n2+ n)/2 = (n2 +3n +2)/2 = (n+1)(n+2)/2 (Gp:) S (Gp:) n+1 i= (n+1)(n+1+1)/2 i=1 = (n+1)(n+2)/2 (Gp:) S
Implementación de la recursión En muchos lenguajes de programación, las funciones, procedimientos o métodos recursivos se solucionan (ejecutan) mediante una pila de registros de activación. Un registro de activación de un método contiene el estado actual de todas las variables definidas en el.
Class SumaEnteros // suma de enteros recursiva static int suma(int n){ if (n==1) return 1; else return n+suma(n-1); } public static void main(String[] args){ System.out.println(“Suma de los primeros 5 numeros enteros ”+suma(5)); } } main() suma(5) suma(4) suma(3) suma(2) suma(1) Pila de registros de activación de los métodos
Demasiada recursión?? La ejecución de métodos recursivos consume tiempo y espacio además de limitar el valor de n para el cual se puede ejecutar el programa. La recursión debe evitarse si es posible usar un ciclo repetitivo. Una función recursiva para calcular los números de Fibonacci realizará una multitud de cálculos repetidos. // Funcion fibonacci public static int fib(int n) { if (n==1) return 0; else if (n==2) return 1; else return fib(n-1)+fib(n-2); } Construye el árbol de llamadas para fib(5)
Transformación de algoritmos recursivos a iterativos Cuando una función realiza una sola llamada recursiva, el árbol que representa su ejecución se muestra como una cadena donde cada vértice tiene un solo hijo. Este árbol puede convertirse en un programa iterativo que ahorra espacio y tiempo de ejecución. (Gp:) n (Gp:) n-1 (Gp:) n-2 (Gp:) n-3 (Gp:) 1 (Gp:) 2
El método para calcular los números de Fibonacci genera una estructura de árbol de dos hijos, no de una cadena. Soluciones para transformar el método: Solución 1. Mantener la información calculada hasta el momento y utilizarla si es necesario. Calcular y almacenar la información que no esta en la tabla Solución 2. Escribir un método iterativo que use variables temporales que “muevan” sus valores entre ellas para calcular nuevos números. (Gp:) 5 (Gp:) 4 (Gp:) 3 (Gp:) 3 (Gp:) 1 (Gp:) 2 (Gp:) 2 (Gp:) 1 (Gp:) 2
Ejemplo: Las torres de Hanoi Juego definido en el siglo XVII en Europa. Elementos: tres postes. n discos de diferentes tamaños. Reglas: Mover los n discos del poste A al poste C usando el poste B como intermediario. Solo se puede mover un disco a la vez. Ningún disco puede colocarse encima de otro más pequeño.
(Gp:) 3 (Gp:) 2 (Gp:) 1 (Gp:) Poste A Poste B Poste C (Gp:) 3 (Gp:) 2 (Gp:) 1 (Gp:) Poste A Poste B Poste C (Gp:) 3 (Gp:) 2 (Gp:) 1 (Gp:) Poste A Poste B Poste C (Gp:) 3 (Gp:) 2 (Gp:) 1 (Gp:) Poste A Poste B Poste C Como se puede mover el disco más grande? Mover primero los discos mas pequeños dejando libre el poste final. mueve (discos, inicio, ayuda, final){ if (discos > 0) { mueve(discos-1, inicio, final, ayuda) S.o.p(“mueve de “+inicio +” a ”+ayuda) mueve(discos-1, final, ayuda, inicio) } }
Ejercicio Cuantos movimientos de discos se requieren para: Mover 1 disco? Mover 2 discos? Mover 3 discos? Mover 4 discos? Mover n discos?
Ejercicio Cuantos movimientos de discos se requieren para: Mover 1 disco? Mover 2 discos? Mover 3 discos? Mover 4 discos? Mover n discos?
public class Hanoi{ static int contar =0; public static void mover (int disco, int a, int b, int c){ contar++; if (disco == 1) System.out.println("Mueve el disco "+disco +" del poste: "+a + " al poste: "+b); else{ mover(disco-1, a,c,b); System.out.println("Mueve el disco "+disco +" del poste: "+a + " al poste: "+b); mover(disco-1, c,b,a); } } public static void main(String[] args){ System.out.println("Inicia el movimiento de "+ 3 +" discos "); mover(3,1,3,2); System.out.println("Total de entradas a Mover "+contar); } } (Gp:) N=2 (Gp:) N=1 (Gp:) N=1 (Gp:) N=2 (Gp:) N=1 (Gp:) N=1 (Gp:) N=2 (Gp:) N=1 (Gp:) N=1 (Gp:) N=3 T(hanoi) = O(2n) S(hanoi) = O(n)
Analisis de complejidad 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.