Recursión
Tabla de contenidos
.png)
1.
Sesión 2 (laboratorio): Recursión
1.1.
Factorial, potencia
Introducción
Vamos a comenzar viendo varios métodos recursivos clásicos para ilustrar su uso y funcionamiento. Una vez analizado el problema, implementaremos la solución con métodos iterativos y recursivos. Finalmente, comparemos el rendimiento de estos métodos.
Análisis del problema
Un ejemplo clásico de recursión lineal es el factorial de un entero no negativo n, representado como n!, el producto de los enteros positivos menores o iguales a n:
Otro ejemplo muy conocido es la función de potencia (potenciación), que se escribe an y se corresponde con una multiplicación repetida n veces de a:
La parte izquierda de las figuras esquematiza la versión iterativa de la resolución del problema, mientras que la parte derecha representa el método de solución recursivo. Antes de empezar a programar, utiliza 2 minutos de tu tiempo para analizar las figuras y las soluciones representadas.
Implementación de la solución
Ahora vamos a implementar en Java una clase capaz de calcular números factoriales y potencias sobre enteros. Para ello, utilizaremos una única clase con una serie de métodos cuyo código rellenaremos a lo largo del ejercicio. La estructura a seguir se muestra en el siguiente código:
public class Functions {
public static int iterativeFactorial(int n) {
/* code here */
}
public static int recursiveFactorial(int n) {
/* code here */
}
public static int iterativePower(int base, int exponent) {
/* code here */
}
public static int recursivePower(int base, int exponent) {
/* code here */
}
public static void main(String args[]) {
/* Code to test the methods */
/* Code to compare both the iterative and recursive results */
}
}
-
Descarga y analiza el código. Responde por escrito a las siguientes preguntas:
-
¿Qué sentido tiene utilizar aquí métodos estáticos? Nombra una clase del API de java que siga la misma estrategia de diseño.
-
¿Por qué no compila este código? Antes de continuar, resuelve el problema.
-
-
Implementa la solución iterativa para calcular números factoriales. Tendrás que implementar el método
iterativeFactorial, además de incluir en el métodomainel código de prueba correspondiente. -
Implementa ahora la solución recursiva para los números factoriales. Comprueba su funcionamiento incluyendo el código apropiado en el método
main. -
Repite los dos apartados anteriores para el caso del cálculo de potencias. No olvides comprobar su funcionamiento en el método
main. -
Habrás observado que tanto el factorial como la potencia alcanzan rápidamente resultados muy elevados, con lo que puede superarse el límite para el tipo de datos
int. ¿Cómo evitarías los problemas de desbordamiento? (responde por escrito a la pregunta) -
Compara los tiempos de ejecución para las soluciones iterativa y recursiva. Para ello, puedes utilizar el método
System.currentTimeMillis, que devuelve el tiempo en milisegundos (de hecho, devuelve la diferencia en milisegundos entre la hora actual y las 0 horas del 1 de enero de 1970; míralo en el API). Llama a este método justo antes y después de llamar al factorial o la potencia. El tiempo de ejecución será la diferencia entre ambos valores. ¿Hay diferencias notables entre implementaciones? Nota: una buena respuesta a esta pregunta estará dada en forma relativa (diferencia en %), no en tiempo absoluto.
Solución
1.2.
Serie de Fibonacci
Descripción
Se trata de un método recursivo clásico para ilustrar su uso y funcionamiento. La sucesión de Fibonacci es una serie infinita de números naturales que comienza con 0 y 1 y a partir de ahí cada elemento es la suma de los dos anteriores. Más información aquí. Implementa una clase Java que calcule la sucesión de Fibonacci, hasta un número dado.
Solución
La solución se puede ver en el siguiente fichero.
1.3.
Obtener el mayor de un array
Descripción
En este ejercicio lo que se pretende es que codifiques un algoritmo recursivo que devuelva el mayor de un array de enteros.
Solución
La solución se puede ver en el siguiente fichero.
1.4.
De entero a binario
En este ejercicio se programará una clase que deberá llamarse BinOperations y que implementará la interfaz Converter.java.
La funcionalidad que debe tener el método int2bin es la siguiente: recibe un entero y devuelve un String, que es la representación binaria del entero recibido como parámetro. La siguiente figura puede ayudar en el diseño de la solución:
Se debe poner especial cuidado en los siguientes puntos.
-
El método a implementar acepta un entero como parámetro y devuelve un objeto de tipo String.
-
Aunque existe una solución iterativa, el código implementado deberá hacer uso de la recursión.
-
El método no trabaja con los valores negativos de int, por lo que deberá limitar el rango de datos de entrada.
El siguiente código puede utilizarse como test para el método int2bin:
public class BinOperationsTest {
public static void main(String args[]) {
Converter c = new BinOperations();
System.out.println("int2bin(1) = " + c.int2bin(1));
System.out.println("int2bin(2) = " + c.int2bin(2));
System.out.println("int2bin(3) = " + c.int2bin(3));
System.out.println("int2bin(4) = " + c.int2bin(4));
System.out.println("int2bin(5) = " + c.int2bin(5));
System.out.println("int2bin(6) = " + c.int2bin(6));
System.out.println("int2bin(7) = " + c.int2bin(7));
System.out.println("int2bin(8) = " + c.int2bin(8));
System.out.println("int2bin(9) = " + c.int2bin(9));
System.out.println("int2bin(10) = " + c.int2bin(10));
System.out.println("int2bin(25) = " + c.int2bin(25));
System.out.println("int2bin(256) = " + c.int2bin(256));
System.out.println("int2bin(2344) = " + c.int2bin(2344));
}
}
Solución
.png)
2.
Actividades para casa
2.1.
Palíndromos
Descripción
Un palíndromo es una palabra, frase, número u otra secuencia de elementos que se lee igual de izquierda a derecha que de derecha a izquierda, normalmente permitiendo ignorar los signos de puntuación y acentos. Un ejemplo conocido es "nada, yo soy Adán". Si te fijas la secuencia de letras es la misma en cualquier sentido de lectura. Lo que se pretende es que codifiques un algoritmo recursivo que compruebe si una cadena de caracteres es palíndroma.
Solución
La solución se puede ver en el siguiente fichero.
2.2.
Pagos de la hipoteca
Este ejercicio consiste en calcular recursivamente los pagos de la hipoteca.
En el cálculo de la hipoteca, por el método francés, cuando el banco presta un capital (C), se exige que cada mes el cliente devuelva parte del capital adeudado en concepto de amortización, y además pague intereses por el capital que queda pendiente de devolver.
Así, cada mes (n) se paga una cuota mensual compuesta de intereses y amortización M(n) = I(n) + A(n). El interés que se paga cada mes I(n)=r/12 * Cp(n), es decir, el capital pendiente por la tasa de interés mensual.Y la amortización es la diferencia hasta la cuota mensual, fija. Al mes siguiente, el capital pendiente habrá disminuido (Cp(n+1) = Cp(n)-A(n)), y el mecanismo vuelve a empezar.
Programa la clase Mortgage, que tenga el método
int amortizationRecursive(int month, double capital, double rate, double fee)
Haz que el método escriba en pantalla el estado del préstamo cada mes:
"Month n: Remaining Capital=remCap(n) MonthlyPayment=M(n) Interests=I(n) Amortization=A(n)
Por ejemplo, para un préstamo inicial de 100.000 €, un interés anual del 3.5%, y una cuota de 500€, las últimas líneas deberían ser algo como:
Month 300 -> Rem. Capital=796,10 MonthlyPayment=500,00 Interests=2,32 Amortization=497,68
Month 301 -> Rem. Capital=298,42 MonthlyPayment=299,29 Interests=0,87 Amortization=298,42
Recuerda que el caso base sería que el capital pendiente sea menor o igual que 0. Contempla también el caso erróneo en que se estipule una cuota mensual menor que los intereses, pues en esa situación nunca se devolvería el préstamo
NOTA: en un a hipoteca real, como la que tenemos los ciudadanos comunes, se suele fijar el plazo y entonces se deduce la cuota, mientras que nosotros hemos fijado la cuota y deducido el plazo (comercialmente se parece más a una línea de crédito). Ten cuidado si intentas aplicar este conocimiento a tu vida real. Puedes encontrar más información por ejemplo aquí.
2.3.
Compresión usando ZIP
El objetivo de este ejercicio es crear un fichero ZIP de un directorio, recorriendo recursivamente su estructura para incluir los subdirectorios. Para ello, utilizaremos clases de la biblioteca estándar de Java que permiten comprimir ficheros aislados.
Como referencia, y para concentrarnos en los temas de recursividad, se proporciona el código necesario para comprimir con ZIP un fichero (ver fichero Compresor.java). El alumno debe centrarse en el desarrollo de la función dirFunc, que recorre la estructura del sirectorio dado y se apoya en la función zipFunc para las tareas de compresión.