Recursión

Tabla de contenidos

1. Sesión 2 (laboratorio): Recursión

1.1. Iteración contra Recursión
1.2. Obtener el mayor de un array
1.3. De entero a binario y de binario a entero

2.1. Palíndromos

1. Sesión 2 (laboratorio): Recursión

1.1. Iteración contra Recursión

En este ejercicio va a resolver una serie de problemas sencillos, utilizando para cada uno de ellos estrategias iterativas y recursivas. De esta manera podrá apreciar la diferencia entre ambas estrategias y aprender cuando merece la pena utilizar una u otra.

Apartado 1. ¿Cuántas velas de cumpleaños ha apagado en toda su vida?

Cada año apaga un número de velas en su tarta de cumpleaños igual a su número de años. Por lo tanto, el número total de velas que ha apagado en toda su vida, si tuviese 6 años sería:

count(6) = 1 + 2 + 3 + 4 + 5 + 6 = 21

Programe una clase Java llamada CandleCounterIterative que implemente la interfaz:

public interface CandleCounter {
    String getImplementationDescription();
    long count(long years);
}

El método getImplementationDescription debe retornar la string "Iterative". El método count debe retornar el número de velas sopladas por una persona a partir de su edad (que se pasa como parámetro). Este método debe ser implementado mediante iteración.

Puede probar su implementación utilizando la clase CandleCounterTest.java y comentando las dos últimas líneas del main (que usaremos más adelante).

A continuación se muestra un ejemplo de ejecución de la clase CandleCounterTest:

; java CandleCounterTest 
Testing Iterative:
    count(0): 0, OK
    count(1): 1, OK
    count(2): 3, OK
    count(6): 21, OK
    count(10): 55, OK
    count(1000): 500500, OK

Apartado 2. Contando velas recursivamente

Programe una clase Java llamada CandleCounterRecursive que implemente la interfaz anterior (CandleCounter).

En esta ocasión el método getImplementationDescription debe retornar la string "Recursive" y el método count debe implementarse recursivamente.

Dese cuenta que el número total de velas que ha apagado hasta este año son las que ha apagado este año (su edad) más las que apagó hasta el año pasado.

A continuación se muestra un ejemplo de ejecución de la clase CandleCounterTest, modificando el main para incluir la prueba de la implementación recursiva:

; java CandleCounterTest
Testing Iterative:
    count(0): 0, OK
    count(1): 1, OK
    count(2): 3, OK
    count(6): 21, OK
    count(10): 55, OK
    count(1000): 500500, OK
Testing Recursive:
    count(0): 0, OK
    count(1): 1, OK
    count(2): 3, OK
    count(6): 21, OK
    count(10): 55, OK
    count(1000): 500500, OK

Apartado 3. Contando velas eficientemente

En algunos casos, ni la solución iterativa (con bucles) ni la recursiva son las más eficientes. Por ejemplo, para el caso anterior, el número total de velas de cumpleaños que ha apagado en su vida se puede expresar sencillamente como:

count(n) = 1 + 2 + ... + n = Σⁿ_i=0 i

Solucione mediante sus conocimientos de cálculo la expresión anterior y programe una nueva clase CandleCounterEfficient.

En esta ocasión el método getImplementationDescription debe retornar la string "Efficient" y el método count debe implementarse sin usar recursión ni iteración, es decir, usando directamente la expresión calculada por usted mismo.

A continuación se muestra un ejemplo de ejecución de la clase CandleCounterTest, modificando el main para incluir la prueba de la implementación eficiente:

; java CandleCounterTest 
Testing Iterative:
    count(0): 0, OK
    count(1): 1, OK
    count(2): 3, OK
    count(6): 21, OK
    count(10): 55, OK
    count(1000): 500500, OK
Testing Recursive:
    count(0): 0, OK
    count(1): 1, OK
    count(2): 3, OK
    count(6): 21, OK
    count(10): 55, OK
    count(1000): 500500, OK
Testing Efficient:
    count(0): 0, OK
    count(1): 1, OK
    count(2): 3, OK
    count(6): 21, OK
    count(10): 55, OK
    count(1000): 500500, OK

Apartado 4. Contado bacterias

Algunos problemas se describen más fácilmente mediante recursión que mediante iteración.

Por ejemplo, la mayoría de las bacterias se reproducen mediante fisión binaria, es decir, si una bacteria tarda un día en reproducirse, cada día tendremos el doble de bacterias que el día anterior. Suponiendo que el primer día tenemos solo una bacteria (count(1) = 1), la cuenta de bacterias que tendremos el día 6 serán:

count(6) = 2 * count(5)
         = 2 * 2 * count(4)
         = 2 * 2 * 2 * count(3)
         = 2 * 2 * 2 * 2 * count(2)
         = 2 * 2 * 2 * 2 * 2 * count(1)
         = 2 * 2 * 2 * 2 * 2 * 1
         = 2 * 2 * 2 * 2 * 2
         = 2 * 2 * 2 * 4
         = 2 * 2 * 8
         = 2 * 16
         = 32

De manera similar al los tres apartados anteriores, implemente la interfaz:

public interface BacteriaCounter {
    String getImplementationDescription();
    long count(int days);
}

Proporcione tres implementaciones diferentes para esta interfaz, BacteriaCounterIterative, BacteriaCounterRecursive y BacteriaCounterEfficient, de forma similar a cómo lo hizo en los apartados anteriores.

Esta vez empieze programando la solución recursiva, luego la iterativa y finalmente la eficiente.

Puede probar su implementación utilizando la clase BacteriaCounterTest.java.

A continuación se muestra un ejemplo de ejecución de la clase BacteriaCounterTest:

; java BacteriaCounterTest 
Testing Iterative:
    count(1): 1, OK
    count(2): 2, OK
    count(3): 4, OK
    count(6): 32, OK
    count(10): 512, OK
    count(20): 524288, OK
Testing Recursive:
    count(1): 1, OK
    count(2): 2, OK
    count(3): 4, OK
    count(6): 32, OK
    count(10): 512, OK
    count(20): 524288, OK
Testing Efficient:
    count(1): 1, OK
    count(2): 2, OK
    count(3): 4, OK
    count(6): 32, OK
    count(10): 512, OK
    count(20): 524288, OK

Apartado 5. ¿Cuándo usar recursión frente a iteración?

Entre la comunidad científica, es un hecho generalmente aceptado que cualquier problema resoluble mediante recursión puede ser también resuelto mediante iteración y viceversa (tesis de Church-Turing) .

También es cierto que generalmente, y sin tener en cuenta optimizaciones del compilador, las soluciones recursivas son menos eficientes que las iterativas.

La combinación de estos dos hechos podría hacerle pensar que nunca merece la pena usar soluciones recursivas ya que sus equivalentes iterativas son mucho más interesantes. Sin embargo, esto no es siempre así.

Investige y discuta con su compañero cuándo merece la pena usar soluciones recursivas. Escriba de dos a tres párrafos explicando sus conclusiones.

Pista: Recuerde el planteamiento del problema cuando queríamos contar velas:

count(6) = 1 + 2 + 3 + 4 + 5 + 6 = 21

y compárelo con el planteamiento del problema cuando queríamos contar bacterias:

count(6) = 2 * count(5)
         = 2 * 2 * count(4)
         = 2 * 2 * 2 * count(3)
         = 2 * 2 * 2 * 2 * count(2)
         = 2 * 2 * 2 * 2 * 2 * count(1)
         = 2 * 2 * 2 * 2 * 2 * 1
         = 2 * 2 * 2 * 2 * 2
         = 2 * 2 * 2 * 4
         = 2 * 2 * 8
         = 2 * 16
         = 32

1.2. Obtener el mayor de un array

Programe una clase ArrayUtils que contenga un método estático public static int getMax(int numbers[]). Este método debe retornar el entero más grande del array que se le pasa como argumento. Implemente el método utilizando recursión.

Pista: la manera estándar de resolver estos problemas mediante recursión es seguir una estrategia de "divide y venceras", donde con cada llamada al método recursivo se procesan "porciones" más pequeñas del array.

Pista: ahorrese ineficiencias en su código evitando crear nuevos arrays para cada "porción" del array original. En lugar de ello, puede crear un método auxiliar que recibe el array orginal y una posición, la cual delimita la "porción" relevante en cada recursión.

Puede probar su implementación con la clase ArrayUtilsTest.java.

A continuación se muestra un ejemplo de ejecución de dicha clase:

; java ArrayUtils
Test 1: OK
Test 2: OK
Test 3: OK
Test 4: OK
Test 5: OK

1.3. De entero a binario y de binario a entero

Este ejercicio es una ampliación del ejercicio ya realizado en clase sobre la conversión entre números enteros y su representación binaria. Para ello, se programará una clase, que deberá llamarse BinOperations y que implementará la interfaz:

public interface BinConverter {
    public String int2bin(int n);
    public int bin2int(String s);
}

Programe, con una implementación recursiva, los siguientes métodos:

public String int2bin(int n): Recibe un entero como parámetro y devuelve un String con la representación binaria de dicho entero. Si recibe un número negativo como parámetro, lanzará una excepción del tipo IllegalArgumentException.
public int bin2int(String s): Recibe un objeto tipo String, que contiene la representación binaria de un entero positivo, y devuelve dicho entero. Si el parámetro recibido no corresponde con el formato esperado, lanzará una excepción del tipo IllegalArgumentException.

Recuerde que debe implementar ambos métodos usando recursión, no iteración.

Los siguientes métodos pueden servir de ayuda para implementar bin2int. Su funcionalidad está descrita en el API de Java:

public static int parseInt(String s), de la clase Integer
public String substring(int beginIndex, int endIndex), de la clase String

Pista: La manera estándar de resolver bin2int mediante recursión es seguir una estrategia de "divide y venceras", donde con cada llamada al método recursivo se procesan "porciones" más pequeñas del string. Esta vez, compensa crear substrings de la original con cada llamada recursiva, debido a la complejidad de conservar la string original en todas las llamadas recursivas.

Puede poner a prueba su implementación con la clase BinOperationsTest.java.

A continuación se muestra un ejemplo de ejecución:

; java BinOperationsTest 
Testing int2bin(-100): throws an IllegalArgumentException, OK
Testing int2bin(-1): throws an IllegalArgumentException, OK
Testing int2bin(0): "0", OK
Testing int2bin(1): "1", OK
Testing int2bin(2): "10", OK
Testing int2bin(3): "11", OK
Testing int2bin(4): "100", OK
Testing int2bin(5): "101", OK
Testing int2bin(6): "110", OK
Testing int2bin(7): "111", OK
Testing int2bin(8): "1000", OK
Testing int2bin(9): "1001", OK
Testing int2bin(10): "1010", OK
Testing int2bin(25): "11001", OK
Testing int2bin(256): "100000000", OK
Testing int2bin(2344): "100100101000", OK

Testing bin2int("00121011"): throws an IllegalArgumentException, OK
Testing bin2int("00110alcortes"): throws an IllegalArgumentException, OK
Testing bin2int("hello"): throws an IllegalArgumentException, OK
Testing bin2int("0"): 0, OK
Testing bin2int("1"): 1, OK
Testing bin2int("10"): 2, OK
Testing bin2int("11"): 3, OK
Testing bin2int("100"): 4, OK
Testing bin2int("101"): 5, OK
Testing bin2int("110"): 6, OK
Testing bin2int("111"): 7, OK
Testing bin2int("1000"): 8, OK
Testing bin2int("1001"): 9, OK
Testing bin2int("1010"): 10, OK
Testing bin2int("11001"): 25, OK
Testing bin2int("100000000"): 256, OK
Testing bin2int("100100101000"): 2344, OK

2. Actividades para casa

2.1. Palíndromos

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.

Programe una clase Palindrome que tenga un método public static boolean check(String s) que retorne true si la string que se le pasa como argumento es un palíndromo o false en caso contrario.

Para simplificar el problema suponga que los palíndromos no ignoran las letras acentuadas ni los signos de puntuación, aunque si ignoran si las letras están en mayúsculas o en minúsculas.

Implemente la recursión eficientemente, evitando copiar la string original o substring de la misma, en cada paso de la recursión.

Puede probar su implementación mediante la clase PalindromeTest.java.