Cronicas de un Mundo Gris

No hace falta ser un experto para ser un gran programador.

Hoy les quiero mostrar una técnica muy simple para hacer cosas muy complejas. Generalmente uno se enfrenta con problemas donde la solución informática es siempre aparente, o sea, al desarrollar una aplicación empresarial, un sitio web, un videojuego simple, uno sabe que esta yendo por terreno conocido, que el sistema va a tener cierta forma, que la programación no va a ser compleja pero si va a llevar su tiempo. Pero no todos los problemas que hay ahí afuera esperandonos son tan simples como aparentan, es más, los más difíciles son a veces los más engañosos en apariencia. Muchos de estos dejan sin dormir a los pobres matemáticos, pero nosotros no vamos a intentar hacer lo que ellos.

Sin embargo estos problemas no son poco frecuentes como uno quisiera creer, por ejemplo, supongamos el caso de un sistema de ecommerce que trabajan con un sistema de envio que cobra por caja y cada caja tiene una capacidad dada, a su vez cada item tiene características distintas, queremos armarle al cliente las cajas de manera que tenga que pagar lo mínimo posible en el envio… no es tan fácil como parece ¿no?

Primero notemos que varios de estos problemas son “acotados”, lo que significa que aún si no sabemos cual es la solución, sabemos que está dentro de ciertas posibilidades, en este caso la solución es una de todas las posibles combinaciones de items posibles. Una forma de resolver el problema es trivial: probar cada una de las combinaciones hasta encontrar una que cumpla los requisitos (a veces puede haber más de una solución). Esta solución se conoce como “por fuerza bruta” y no es la más eficiente, pero es una solución y muchas veces no trabajamos con una complejidad tal que requiera eficiencia (en este caso, si son pocos items los que hay que acomodar no deberíamos preocuparnos tanto).

De todas maneras, aunque sabemos esta solución, la fuerza bruta, a veces, no es tan fácil de poner en práctica, y muchas veces no es la solución más agradable. Pero mediante la técnica de recursión podemos ponerla en práctica de una manera elegante, si el tipo de problema lo permite.

Vamos a intentar resolver una variante del problema anterior, mucho más simple. Supongamos que tenemos una bolsa de monedas de distintos valores, no necesariamente los habituales, y queremos obtener cierto monto en particular con las monedas que disponemos. El problema tiene 2 parámetros: un conjunto de valores y una suma deseada, y vamos a asumir que todos son valores positivos.

La técnica de recursión es muy simple: vamos a resolver el problema para una cantidad de monedas N, asumiendo que la solución para N-1 monedas ya existe. Entonces nosotros quitamos una moneda de la bolsa y sabemos que ahora podemos obtener una solución para esa bolsa, y nos falta saber que hacer para obtener una solución que considere a la moneda que quitamos. Podríamos chequear primero si existe una solución sin la moneda que quitamos, si existe el problema está resuelto. Si no existe deberíamos considerar que tal vez la moneda era necesaria para una solución, pero en vez de agregarla y probar con otra, simplemente cambiamos la suma deseada restandole el valor de dicha moneda. En pseudo-código:

funcion obtenerMonto(bolsa, monto) donde bolsa tiene N monedas
    moneda <- bolsa.sacarMoneda()
    solucion1 <- obtenerMonto(bolsa, monto)
    si solucion1 existe
        devolver solucion1
    si no
        solucion2 <- obtenerMonto(bolsa, monto - moneda)
        si solucion2 existe
            solucion2.agregarMoneda(moneda)
            devolver solucion2
        si no
            devolver no existe

Ahora, para resolver el problema con N monedas, usamos la solución con N-1, y esa usa la solución con N-2, y así sucesivamente, en algún momento debemos encontrar un solución que decida por sí sola, si no la recursión sería infinita. Lo que necesitamos se llama “caso base” y generalmente es una instancia del problema que es trivial resolver, en este caso, si la bolsa ya no contiene monedas. Si no hay monedas solo hay un caso que puede tener solución, éste es cuando el monto deseado es cero, en cuyo caso devolvemos una solución vacía. Si no indicamos que la solución no existe. En pseudo-código:

funcion obtenerMonto(bolsa, monto) donde bolsa no tiene monedas
    si monto = 0
        devolver solucion vacia
    si no
        devolver no existe

Luego, podemos combinar el caso resursivo y el caso base en una única función, simplemente chequeando la condición de la entrada:

funcion obtenerMonto(bolsa, monto)
    si bolsa no tiene monedas
        aplicar caso base
    si no
        aplicar caso recursivo

Eso es todo. Observen que, por cada moneda, el caso recursivo comprueba la posibilidad de que la moneda esté o no esté en la solución, o sea que, en definitiva, está comprobando todos los casos posibles hasta encontrar uno. Esto es algo usual al usar recursión, y es una buena guía para saber si estamos usando esta técnica correctamente, considerar si estamos probando todas las opciones posibles para el item que estamos evaluando en la etapa recursiva.

Ahora te toca a tí (?)