Universidad Carlos III de Madrid

Grado en Ingeniería Telemática/Grado en Ingeniería de Sistemas de Comunicaciones

Enero-Mayo 2014

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. Actividades para casa
2.1. Palíndromos

Lab Section1. Sesión 2 (laboratorio): Recursión

Exercise Section1.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

Solución 

public class CandleCounterIterative implements CandleCounter {

    public String getImplementationDescription() {
        return "Iterative";
    }

    public long count(long years) {
        // TODO: throw an exception if years < 0
        long output = 0;
        for (long i = 0; i <= years; i++)
            output += i;
        return output;
    }
}

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

Solución 

public class CandleCounterRecursive implements CandleCounter {

    public String getImplementationDescription() {
        return "Recursive";
    }

    // non-tail recursive version
    public long count(long years) {
        // TODO: throw an exception if years < 0
        if (years < 2)
            return years;
        else
            return years + count(years - 1);
    }
}

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 = Σni=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

Solución 

public class CandleCounterEfficient implements CandleCounter {

    public String getImplementationDescription() {
        return "Efficient";
    }

    public long count(long years) {
        // TODO: throw an exception if years < 0
        return years * (years + 1) / 2 ;
    }
}

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

Solución 

public class BacteriaCounterIterative implements BacteriaCounter {

    public String getImplementationDescription() {
        return "Iterative";
    }

    public long count(int days) {
        // TODO: throw an error if days < 1
        long output = 1;
        for (long i = 2; i <= days; i++)
            output *= 2;
        return output;
    }
}

public class BacteriaCounterRecursive implements BacteriaCounter {

    public String getImplementationDescription() {
        return "Recursive";
    }

    // non-tail recursive version
    public long count(int days) {
        // TODO: throw an error if days < 1
        if (days == 1)
            return 1;
        else
            return 2 * count(days - 1);
    }
}
public class BacteriaCounterEfficient implements BacteriaCounter {

    public String getImplementationDescription() {
        return "Efficient";
    }

    public long count(int days) {
        // TODO: throw an error if days < 1
        return (long) Math.pow(2, days-1) ;
    }
}

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

Solución

Merece la pena usar soluciones recursivas cuando la solución puede expresarse más fácilmente mediante recursión o cuando la definición del problema hace que una solución recursiva resulte más intuitiva.

Aunque potencialmente puedan existir soluciones iterativas más eficiente, pueden ser tan difíciles de encontrar o tan difíciles de programar, que la (supuesta) mejora de eficiencia acaba por no merecer la pena.

En las próximas semanas, cuando se introduzcan los árboles como estructura de datos, se verán ejemplos evidentes de soluciones recursivas sencillas cuyos equivalentes iterativos son extremadamente complejos y no merecen la pena.

Exercise Section1.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

Solución 

public class ArrayUtils {

    // It begins at the end of the array
    static int getMax(int numbers[], int pos) {
        int aux;
        if (pos == 0) {
            return numbers[pos];
        } else {
            aux = getMax(numbers, pos - 1);
            if (numbers[pos] > aux) {
                return numbers[pos];
            } else {
                return aux;
            }
        }
    }

    public static int getMax(int numbers[]) {
        if (numbers == null) {
            throw new IllegalArgumentException();
        } else if (numbers.length == 0) {
            throw new IllegalArgumentException();
        }
        return getMax(numbers, numbers.length - 1);
    }
}

Exercise Section1.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

Solución 

public class BinOperations implements BinConverter {

    public String int2bin(int n) {
        String output;
        if (n < 0) {
            throw new IllegalArgumentException();
        } else if (n < 2) {
            output = "" + n;
        } else {
            String bit = "" + (n % 2);
            output = int2bin(n / 2) + bit;
        }
        return output;
    }

    public int bin2int(String s) {
        int first;
        try {
            first = Integer.parseInt(s.substring(0, 1));
        } catch (NumberFormatException e) {
            throw new IllegalArgumentException();
        }
        if ( first != 0 && first != 1 ) {
            throw new IllegalArgumentException();
        }

        int output;
        if (s.length() > 1) {
            output = first * (int) Math.pow(2, s.length() - 1)
                + bin2int(s.substring(1));
        } else {
            output = first;
        }
        return output;
    }
}

Homework Section2. Actividades para casa

Exercise Section2.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.

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

; java PalindromeTest 
Testing palindrome "": true, OK
Testing palindrome "abccba": true, OK
Testing palindrome "Ana": true, OK
Testing palindrome "Level": true, OK
Testing palindrome "Dabale arroz a la zorra el abad": true, OK
Testing palindrome "Satan oscillate my metallic sonatas": true, OK
Testing non-palindrome "Hola mundo": false, OK
Testing non-palindrome "Si a la ingenieria telematica": false, OK

Solución 

public class Palindrome {

    static boolean check(String s, int i, int j) {
        if (i != (s.length() / 2)) {
            if (s.charAt(i) == s.charAt(j)) {
                return palindrome(s, ++i, --j);
            } else {
                return false;
            }
        }
        return true;
    }

    public static boolean check(String s) {
        // Convert the characters to lowercase and skip the blank characters
        String normalizedString = s.replaceAll(" ", "");
        normalizedString = normalizedString.toLowerCase();
        return check(normalizedString, 0, normalizedString.length() - 1);
    }
}