11. Recursión¶

Contenidos¶

1. Introducción a recursión
2. La repetición descrita como recursión
3. Funciones Recursivas: Más Allá de los Ejemplos Simples
4. Merge Sort: El Poder de la Recursión al Servicio de la Ordenación
5. Backtracking
6. Árbol de Decisiones y Esqueleto de Backtracking
7. Ejemplos
8. Ejercicios

11.1 Introducción a recursión¶

Hasta ahora, hemos resuelto muchos problemas usando el concepto de iteración. Por ejemplo, para calcular la suma de todos los elementos de una lista de números, usamos palabras claves como while y for, que se conocen, en la teoría de lenguajes de programación, como constructos iterativos. La iteración consiste en repetir una porción de código algún número de veces para lograr un objetivo de cómputo. La iteración a primera vista parece necesaria en los lenguajes de programación, porque hay problemas cuya solución es inherentemente repetitiva. Volviendo al ejemplo anterior, para sumar todos los elementos de una lista, necesariamente debemos tener acceso a cada elemento de la lista, y si no sabemos con anticipación cuál es el tamaño de la lista (la lista podría ser arbitrariamente grande), debemos expresar la solución como un algoritmo repetitivo.

La iteración, sin embargo, no es la única forma de resolver un problema que requiere repetición. Existe una forma alternativa: la recursión. Como veremos en este capítulo, recursión es una técnica extremadamente poderosa. De hecho, existen clases de problemas de computación cuyas soluciones requieren de repetición y para los cuales sólo es posible dar una solución elegante usando la técnica de recursión. Recursión, cuando es bien utilizada, generalmente resulta en soluciones muy elegantes, de pocas líneas de código. Tan así que no es raro que algunos programadores consideren a la recursión como aquella técnica de programación que más nos acerca a la programación como un arte y no solo como una técnica.

Nótese lo radical de lo que hemos dicho arriba. La iteración no es necesaria si tenemos recursión a nuestro alcance. Dicho de otro modo, el for y el while son dispensables si uno conoce bien la técnica de recursión. Sin perjuicio de esto, como veremos más adelante, la elegancia en la programación la consigue un programador que comprende cuál es la técnica más apropiada a usar en qué momento. Así, las funciones recursivas complejas usualmente utilizan elementos iterativos. El objetivo de este capítulo es que aprendas esta nueva técnica y que comprendas como integrarla a todo lo que ya aprendiste.

11.2 La repetición descrita como recursión¶

La recursión es una técnica natural; de hecho, es posible argumentar que es más natural que la iteración. Esto es porque las personas, incluso cuando no tienen conocimientos de programación, la utilizan. Imagina que un niño pequeño se acerca a preguntarte “¿como puedo pintar este árbol?”.

Figura 11.1. Mandala.

Una respuesta sencilla (recordemos que el niño es pequeño) podría ser la siguiente: “Primero, pinta el tronco de color café. Luego haz lo siguiente: escoge una hoja, píntala verde, y luego sigue con el resto de las hojas. Habrás terminado cuando no queden hojas por pintar”. Esta forma de describir cómo pintar el árbol es recursiva. De hecho, le hemos explicado al niño un procedimiento para pintar el árbol completo. Este procedimiento pinta una hoja y luego se invoca a sí mismo al “seguir con el resto”. El procedimiento termina cuando no existe una hoja sin pintar.

Para comprender la sutileza presente de la descripción anterior, transformaremos nuestro ejemplo de pintar el árbol a un ejemplo concreto en Python. Nos concentraremos solo en la parte que pinta las hojas. Específicamente queremos programar una función pintarHojas(listaHojas), que supone que lista listaHojas es una lista de hojas, donde cada hoja es un objeto. Finalmente, suponemos que si h es una hoja h.pinta(color) pinta la hoja de color color.

Siguiendo la explicación lo más ajustadamente posible, programamos la función de esta manera:

def pintarHojas(listaHojas,color):
  if listaHojas != []:
    listaHojas[0].pintar(color)
    pintarHojas(listaHojas[1:],color)

Notemos que la función pintarHojas se invoca a sí misma, y por lo tanto es recursiva. La pregunta que nos cabe responder ahora es, ¿por qué es esta función correcta?

Para convencerse de aquello hay varias opciones. Explicaremos ahora la más sencilla, que es ejecutar la función con un problema pequeño, para luego convencerse que también funciona para problemas más grandes. Supongamos entonces que ejecutamos pintarHojas([h1,h2],c). Al llamar a la función, el programa procede a ejecutar h1.pintar(c), y luego a hacer el llamado recursivo a pintarHojas([h2],c), sin que pintarHojas([h1,h2],c) haya retornado aun. Ahora, en el llamado a pintarHojas([h2],c), se ejecuta h2.pintar(c) y luego se hace un llamado recursivo a pintarHojas([],c). Notemos que en este punto tenemos tres llamados a la misma función que están “activos”, dos de ellos están “esperando” el retorno de un llamado recursivo para continuar. Este último llamado a pintarHojas([],c) retorna inmediatamente, transmitiendo el control hacia la función pintarHojas([h2],c), que también retorna, pasando ahora el control a la función pintarHojas([h1,h2],c), que también retorna.

Como consecuencia de la ejecución, todas las hojas en la lista se pintan, y no es difícil ver que la función es correcta para cualquier lista de hojas.

11.3 Funciones Recursivas: Más Allá de los Ejemplos Simples¶

Las siguientes son dos características de las funciones recursivas.

1. Definen una solución concreta para uno o varios problemas pequeños. Esto se conoce como el/los caso(s) base.
2. Definen la solución a un cierto problema P en términos de la solución de uno o varios problemas más pequeños que P. La implementación de esto se hace mediante lo que se conoce como un llamado recursivo, el que usualmente se implementa mediante un llamado a la misma función.

Hay muchas funciones matemáticas que naturalmente se expresan de manera recursiva. Por ejemplo, la conocida serie de Fibonacci se puede definir mediante una función f que satisface:

Figura 11.2. Función versión 1.

Por otro lado, la función factorial se puede definir como:

Figura 11.3. Función versión 2.

Ejercicio: Escribe versiones recursivas e iterativas para ambas funciones.

En este punto tú podrías sentir algo de decepción. Todos los ejemplos que hemos visto se pueden resolver usando simples algoritmos iterativos. Además, recursión tal vez no te parece ser la técnica más natural del mundo. El objetivo del resto de este capítulo es mostrarte cómo es que podemos, con recursión, hacer cosas que con la iteración parecen imposibles. Partiremos con un ejemplo sencillo que se puede resolver con iteraciones, luego lo complicaremos solo un poco y obtendremos un problema muy difícil de resolver con iteraciones.

El problema sencillo es este: “escriba una función esta(elem, lista) que retorna True si elem está en la lista lista , y False en caso contrario”. Para encontrar una respuesta intentamos hacer calzar esta función a las reglas que definimos arriba. Podríamos usar el siguiente razonamiento.

1. (Caso base) Si lista está vacía, entonces retornamos False
2. (Recursión)

• Si elem es el elemento que está al principio de lista, retornamos :code`True`; en caso contrario,
• retornamos lo mismo que retorna esta(elem,lista[1:]).

La implementación de esta idea resulta en lo siguiente:

def esta(elem, lista):
      if lista == []:
              return False
      if elem == lista[0]:
              return True
      else:
              return esta(elem,lista[1:])

Pasemos ahora a un ejemplo un poco más complejo. El ejercicio consiste en escribir una función que sea capaz de encontrar un elemento en una lista anidada, es decir, una lista que pueda contener listas que a su vez puedan contener listas. Suponemos ahora que el nivel de anidación es arbitrariamente grande, es decir, que no tiene límite. Llamaremos a esta función superEsta(elem, lista), y los siguientes son ejemplos de ejecución.

• superEsta(2,[1,2,3,4]) retorna True.
• superEsta(0,[1,2,3,4]) retorna False.
• superEsta(2,[[1,2],3,4]) retorna True.
• superEsta(2,[1,['a',['b',[2]],3,4]) retorna True
• superEsta(2,[1,[[[[2]]]],3,4]) retorna True.

Ahora describimos esta función recursivamente, inspirándonos en la definición de la función esta :

1. (Caso base) Si lista está vacía, entonces retornamos False
2. (Recursión)

• Si elem es el elemento que está al principio de lista, retornamos True; en caso contrario,
• si lista[0] es una lista y superEsta(elem,lista[0]) retorna True, entonces retornamos True. En caso contrario,
• retornamos lo mismo que retorna superEsta(elem,lista[1:]).

Notemos que, a pesar de que esta función parecía mucho más difícil que la anterior, en nuestro razonamiento sólo tenemos un punto más. La implementación queda de esta manera:

def superEsta(elem, lista):
      if lista == []:
              return False
      if type(lista[0]) == list and superEsta(elem,lista[0]):
              return True
      else:
              return superEsta(elem, lista)

A continuación te presentamos algunos ejercicios:

1. Escriba una función que, dada una lista anidada con números, encuentre la suma de todos los elementos. Escriba otra que encuentre el máximo.
2. Escriba una función para “aplanar” una lista anidada; es decir, que cuando reciba [[1],2,[3]] o [[[[1,[2]]],[[3]]] retorne [1,2,3].
3. Escriba una función camino(elem,lista) que retorna una lista que describa cómo llegar a un elemento en una lista anidada. Por ejemplo camino(2,[1,2,3]) retorna [1] porque el elemento 2 está en la posición 1 de [1,2,3]. Por otro lado camino(2,[1,['a','b',[2]],3,4]) retorna [1,2,0] porque para encontrar el elemento 2 en la lista deseada, es necesario ir al elemento en la posición 1 en la lista original, que es ['a','b',[2]],3,4], luego al elemento 2 de ella, que es [2], y luego al elemento 0 de [2]. Su función debe retornar la lista vacía en caso que el elemento no se encuentre en la lista.
4. El lenguaje de programación “Symple” tiene solo dos palabras claves: write`y :code:`repeat. La palabra clave write se debe seguir de un string y su efecto, al ejecutarse, es mostrar el string en pantalla. La sentencia repeat, por otro lado, recibe un número n y un bloque de código y su efecto es repetir el bloque n veces. Un programa se escribe como una lista Python. Los siguientes son ejemplos de programas en Symple.

• [['write', 'hola mundo']]
• [['write', 'hola mundo'],['write','chao']]
• [['repeat', 5, ['write','hola!']],['repeat',4,['write','chao!']]]
• [['repeat', 2,['repeat', 2,['write', 'hola']]]]]

y este es el resultado de ejecutarlos:

• hola mundo
• hola mundochao
• hola!hola!hola!hola!hola!chao!chao!chao!chao!
• hola!hola!hola!hola!

Escriba un intérprete de Symple en Python; específicamente, una función que dado cualquier programa Symple (arbitrariamente grande y con una cantidad arbitraria de anidaciones) que imprima la salida correcta.

Resolveremos ahora un ejemplo en donde se muestra claramente el potencial de recursión para resolver problemas combinatoriales. Se pide lo siguiente: escriba una función permutaciones(s) que retorne una lista con todas las permutaciones de un string s. Una permutación de un string s consiste en cambiar cero o más de sus caracteres de posición; así, ["abc","acb","bac","bca","cab","cba"] es una lista que contiene todas las permutaciones de "abc".

En este ejemplo (como en muchos otros) la clave está en pensar cómo construir la solución a un problema P en términos de la solución a un sub-problema de P más pequeño que P. En nuestro ejemplo, conviene hacerse la pregunta, ¿puedo expresar las permutaciones de "abc" en términos de las permutaciones de "bc"?

La respuesta es sí. Primero observamos que la lista de permutaciones de "bc" es ["bc","cb"]. Para obtener las permutaciones de "abc", insertamos la letra 'a' en todas las posiciones posibles de "bc", con lo que obtenemos ["abc","bac","bca"], y luego en todas las posiciones posibles de "cb", con lo que obtenemos ["acb","cab","cba"]. Al unir ambas listas, tendremos la solución al problema.

Luego de encontrar una respuesta positiva nos preguntamos: ¿generaliza el método que encontré a cualquier string?. En nuestro caso, verificamos que la respuesta para este problema también es sí. Para convencerte, podrías verificar que, siguiendo la misma idea, es posible construir las permutaciones de "dabc" en función de las permutaciones de "abc".

Para plantear la solución supongamos que tenemos implementada la función insertar(c,s), que retorna la lista en donde el caracter c, está insertado en todas las posiciones de s (es decir suponemos que, por ejemplo,:code:insertar(‘a’,’bc’) retorna la lista ['abc', 'bac','bca']).

Ahora podemos plantear la solución recursiva:

1. Si s es el string vacío entonces permutaciones(s) retorna la lista que contiene a [""]. (Observa que el string vacío es la única permutación de sí mismo.). En caso contrario,
2. Retornamos la lista que resulta de concatenar insertar(s[0],st), para cada st que pertenece a la lista permutaciones(s[1:]).

En Python, obtenemos el siguiente código:

def insertar(a,s):
    return [s[:i] + a + s[i:] for i in range(len(s)+1)]

def permutaciones(s):
    if s == '':
        return ['']
    else:
        l=[]
        for st in permutaciones(s[1:]):
            l.extend(insertar(s[0],st))
        return l

Puedes ver y ejecutar una solución al ejercicio de permutaciones en el ejemplo 7.4.

A continuación te presentamos algunos ejercicios:

1. Desciba con precisión cómo es que toda sentencia while en un programa Python se puede eliminar, reemplazándola por un llamado a una función recursiva. Muestre varios ejemplos.
2. Una subscuencia de una lista l se obtiene de eliminar 0 o más elementos de l. Escriba una función subsecuencias(lista), que retorne todas las subsecuencias de lista.
3. Un string de paréntesis balanceados contiene solo los caracteres '('`y `')' tal que cada abre paréntesis tiene un cierre de paréntesis correspondiente. Los siguientes son ejemplos de strings de paréntesis balanceados:

• ()
• (((())))
• ()()()
• (()())()
• ()(())((())(()))

Mientras que los siguientes son strings de paréntesis que no son balanceados:

• ())(
• ())
• )()(

Escriba una función balanceados(n), que retorne una lista con todos los strings balanceados de n caracteres.

11.4 Merge Sort: El Poder de la Recursión al Servicio de la Ordenación¶

¿Podremos expresar el problema de ordenar una lista en forma recursiva? La respuesta más o menos obvia es que sí, porque, como vimos en el ejercicio de arriba, existe un método para eliminar todas las sentencias while de un programa dado, manteniendo la semántica del programa. Bastaría, entonces, con aplicar ese método a un algoritmo que ya conocemos (por ejemplo, ordenación por selección), y obtendríamos algo que funciona. Sin embargo, no obtendríamos ningún beneficio en términos de eficiencia.

Merge Sort es un algoritmo de ordenación recursivo que explota la recursión a tal nivel que el algoritmo que se obtiene es, como veremos, substancialmente más rápido que cualquiera de los algoritmos que vimos en el capítulo de Ordenación y Búsqueda.

El algoritmo usa la siguiente idea. Si tenemos una lista de números l, podríamos ordenarla de la siguiente forma:

1. Si la lista l está vacía, la retornamos. En caso contrario,
2. Dividimos a l en dos mitades li y ld.
3. Ordenamos ambas listas.
4. Finalmente, construimos una tercera lista ordenada, l' mezclando (de aquí de donde viene Merge) li y ld
5. Retornamos l'

Nota que el punto 2 se puede implementar con un llamado recursivo. Finalmente, el punto 3 es fácil de implementar usando una función iterativa, que primero mira cuál de las dos listas tiene el elemento más pequeño al principio y lo ubica al principio de la lista resultante. Cuando alguna de las listas se acaba, ubicamos en la lista resultante todos los elementos de la otra. En Python, esta función se ve así.

def mezcla(li,ld):
  r = []   # r es la lista resultado
  i = 0
  j = 0
  while i < len(li) and j < len(ld):
    if li[i] <= ld[j]: # agregamos primer elemento de li a r
      r.append(li[i])
      i += 1
    else:  # agregamos primer elemento de ld a r
      r.append(ld[j])
      j += 1
  if i >= len(li):
    r.extend(ld[j:])
  else:
    r.extend(li[i:])
  return r

Ahora la implementación de la función recursiva queda de la siguiente manera.

def mergesort(l):
  if len(l) <= 1:
    return l
  m = len(l) // 2
  li = mergesort(l[:m])
  ld = mergesort(l[m:])
  return mezcla(li,ld)

Análisis de Merge Sort¶

La pregunta más importante que aún no hemos respondido es: ¿es este algoritmo realmente mejor que lo que ya hemos visto?

Para entender bien si es mejor que algoritmos anteriores, recordemos el caso de Selection Sort. La idea detrás de este algoritmo era la siguiente: seleccionábamos el elemento más pequeño de la lista a ordenar y lo ubicábamos al principio de la lista resultante, luego, buscábamos el segundo elemento más pequeño, para ponerlo en el lugar de índice 1, y así sucesivamente. Contemos ahora el número de veces que accedemos a un elemento de la lista. Para calcular el primer mínimo, necesitamos “mirar” n elementos. Para buscar el segundo mínimo, necesitamos mirar n-1 elementos. Y así sucesivamente, para una lista de n elementos necesitamos revisar:

Figura 11.4. Fórmula merge sort.

posiciones de la lista. Así, diremos que el algoritmo ejecuta del orden de $n^2$ operaciones o, simplemente, que es cuadrático.

Veamos ahora cuántas operaciones debe hacer Merge Sort. Para ello, en la siguiente ilustración se muestran los llamados recursivos que hace Merge Sort en forma de árbol.

Figura 11.5. Diagrama de árbol merge sort.

En cada llamado, la lista se divide en dos y luego se ejecuta el mismo algoritmo en las dos mitades. Cuando ambos llamados recursivos retornan, se deben mezclar ambas listas ordenadas. Para obtener el número que buscamos, debemos responder las siguientes preguntas.

1. ¿Cuánto es el máximo número de niveles que puede tener el árbol? Al máximo número de niveles le llamamos profundidad del árbol.
2. ¿Cuántas operaciones se realizan en cada nivel del árbol?

Para responder la pregunta 1 nos damos cuenta que, dado que cada vez que se realiza un llamado recursivo la lista se divide en dos, entonces tenemos que el máximo número de niveles M es tal que n/(2^M)=1 (cada vez que bajamos un nivel dividimos a n por 2, y al final hemos dividido a n por 2^M). Obtenemos entonces que M=log2(n).

Para responder la pregunta 2, notamos que el número de elementos al que debe hacer la función mezcla es, a lo más, igual al número total de elementos que hay entre li y ld. Lo interesante es que eso significa que en cada nivel del árbol de la figura, el trabajo total empleado en mezclar es exactamente n.

Como tenemos log2(n) niveles en el árbol y hacemos n operaciones en cada nivel, Merge Sort, en el peor caso, realiza del orden de n*log(n) operaciones. Para valores grandes de n, n*log(n) es sustancialmente menor que n^2. (Piensa que log(n) es proporcional al número de dígitos del n.) Concluimos que el principio de recursión es una herramienta crucial para obtener, no solo soluciones elegantes sino que también eficientes. Te presentamos un ejercicio.

Ejercicio: Compara la eficiencia de Merge Sort con la de Selection Sort. Para ello, haz un programa para generar un archivo con 10 mil números aleatorios. Luego extiende el programa de arriba para leer el archivo y luego ordenarlo.

11.5 Backtracking¶

Backtracking es una técnica recursiva básica para resolver problemas combinatoriales. La clase de problemas a los que se aplica es aquella en donde una solución se construye mediante una secuencia de decisiones. Una vez que se ha tomado una cierta cantidad de decisiones es posible verificar si hemos encontrado una solución.

Estos son ejemplos de algunos problemas combinatoriales que se pueden resolver tomando una secuencia de decisiones.

1. Sudoku. Cada cuadro vacío debe ser llenado con un número. La “decisión” tiene dos partes: donde ubico el siguiente número y cuál número ubico ahí.
2. Asignación de salas en una universidad. Hay un conjunto de salas disponibles. Cada sala tiene cierta capacidad. Además tenemos un conjunto de cursos, cada uno de los cuales debe ser asignado a una sala. Los cursos tienen un número de inscritos, que no debe superar la capacidad de la sala donde se le asigna. Acá la decisión es en qué sala se ubica cada curso.
3. Dado un conjunto de números, queremos separar, si es posible, a los números en dos conjuntos que sumen lo mismo. Una vez que hemos creado los dos conjuntos, debemos asignar a cada número en uno de ellos; la decisión es a cuál conjunto lo asignamos.
4. Dado un conjunto de números C y un número n, queremos encontrar un subconjunto S de C tal que la suma de sus elementos sea n. Dado que debemos encontrar un subconjunto de C, para cada número x de C debemos decidir si x va a pertenecer o no al conjunto S.

Los problemas combinatoriales son muy importantes en ingeniería. A veces no solo interesa encontrar combinaciones que “sirven” (piense en el ejemplo de la universidad), sino que combinaciones que optimizan cierta función. Por ejemplo, en el caso de la asignación de salas en la universidad nos podría interesar minimizar alguna función de “distancia” porque, por ejemplo, podríamos querer que los alumnos se desplacen lo menos posible entre salas, o que cursos de una unidad (p.ej., Ingeniería) quedaran ubicados en salas de la misma unidad. En este capítulo nos enfocaremos primero en los problemas en donde basta con encontrar “una” combinación que funciona. Sin embargo, luego veremos una técnica sencilla para resolver problemas de optimización combinatoriales.

11.6 Árbol de Decisiones y Esqueleto de Backtracking¶

Arriba dijimos que Backtracking se ajusta a problemas donde debemos tomar una secuencia de decisiones. Una observación clave es que en cada “punto de decisión”, tenemos, en general, más de una opción. Por ejemplo, pensemos en el problema 4. de arriba. Para cada número del conjunto C debemos decidir si ese número estará o no presente en el conjunto S. La siguiente figura muestra cómo es que podemos organizar todas las posibles secuencias de decisiones como un “árbol de decisiones” y como es que podemos construir cualquier subconjunto de S tomando siempre 3 decisiones sucesivas.

Figura 11.6. Diagrama de árbol de decisión.

Si logramos construir una función que recorra ese árbol de decisiones, podremos resolver cualquier problema que necesite enumerar, revisar o visitar todos los subconjuntos de un conjunto.

Backtracking es una técnica que permite precisamente hacer eso: generar todas las secuencias de decisiones que existen para un problema particular. La técnica no se limita a la generación de subconjuntos, como en nuestro ejemplo, sino a la exploración de todas las combinaciones de decisiones posibles.

Todas las funciones que usan backtracking se ajustan a una estructura bastante similar. Ahora veremos esta estructura mediante un pseudo código, es decir, una especificación del algoritmo en castellano en vez de en Python. Los pseudo códigos son especialmente útiles porque permiten evitar mencionar detalles demasiados específico.

Nuestro pseudo código, por el momento, solo es capaz de decir si es que el problema tiene solución, pero no será capaz de decirnos cuál es la solución. Luego lo extenderemos un poco para encontrar la solución. Al mirarlo, te recomiendo que imagines que el pseudo código es un programa.

BackTrack(P)

# Parámetros de entrada: Un problema P

# Qué retorna: True, si el problema tiene solución. False, en caso contrario.

1. Si P ya está resuelto, retornar True.
2. Sea D un conjunto de decisiones que se pueden tomar en este momento.
3. Para cada decisión d en D:

• genere el problema P’ que corresponde a tomar la decisión d en P.
• Si el llamado a BackTrack(P’) retorna True, entonces retornarmos True

4. Retornar False

Ahora intentaremos convertir ese pseudocódigo en un programa en Python. Además, apuntaremos a escribir un código elegante. Para simplificar nuestro razonamiento, pensaremos en un problema específico: dado el conjunto C={5,6,11,15}, escriba una función Python que retorne True si existe un subconjunto de C que sume N=20, y que retorne False en otro caso. Podemos verificar que la respuesta debiera ser sí, porque 5+15=20.

Antes de empezar a programar, debemos hacernos tres preguntas. La primera es: ¿qué es el problema P en este caso?. Observemos que nuestro problema está caracterizado por dos cosas: un conjunto de números y un “número objetivo”. Entonces, en nuestra función Python, lo natural es que P quede representado por dos elementos: una lista de números (para representar el conjunto), y un número.

La segunda pregunta es: ¿qué es una decisión, y cuál es el problema que resulta como resultado de tomar una decisión?. Debido a que estamos construyendo un subconjunto S de un conjunto C, por cada elemento de C hay dos opciones: el elemento está en S o no lo está. Si C={5,6,11,15}, la primera decisión que tomamos es si 5 va o no a pertenecer al subconjunto que queremos que sume 20. Si decidimos que 5 sí estará en aquel conjunto, el problema resultante está caracterizado por el par C’={6,11,15} y N’=15. Observa acá que C’ tiene un elemento menos que C y que el número N’ es distinto de N. En efecto, si 5 pertenece al conjunto que buscamos, ahora nuestro problema se ha reducido a encontrar un subconjunto de C’ que sume 15; si logramos mostrar que ese sub-problema tiene solución, habremos demostrado que el problema original tiene solución. Por otra parte, si decidimos que 5 no va en el conjunto, hemos reducido el problema original, a uno caracterizado por C’={6,11,15} y N’=20. Observa que en ambos casos el problema resultante es “más pequeño” que el problema original, porque hay un elemento menos en el conjunto.

La tercera pregunta es: ¿cuándo un problema está resuelto? o, alternativamente, ¿cuál es el caso base?. Para responder esta pregunta observamos que el tamaño del conjunto es el que define el tamaño del problema. Los problemas más pequeños que existen son, entonces, aquellos donde el conjunto está vacío.

La función en Python se ve así:

def sub_suma(lista, valor):
  if lista == []:
      if valor == 0:
          return True
      else:
          return False
  if sub_suma(lista[1:], valor - lista[0]):
      return True
  if sub_suma(lista[1:], valor):
      return True
  return False

La siguiente figura muestra el árbol de llamados recursivos que se genera cuando se llama a sub_suma([5,6,11,15],20). A cada elemento de la forma (“lista”,”numero”) lo llamamos “nodo”. Cada nodo representa un llamado a sub_suma, con los argumentos correspondientes. Cuando un nodo n está directamente unido con otro nodo n’ encima de él, decimos que n es “hijo de” n’, y significa que la función, al ser invocada con los argumentos de n’, llama a la función con los argumentos de n. Como se espera, cada nodo tiene a lo más dos hijos porque sub_suma hace a los más dos llamados recursivos. En la figura, suponemos que el hijo izquierdo representa el primer llamado recursivo, mientras que el derecho representa el segundo. El árbol tiene 15 nodos, lo que significa que, en total, necesitamos 15 llamados a sub_suma para encontrar el “nodo solución”, representado por ([],0).

Figura 11.7. Árbol de llamados recursivos del ejemplo.

Lo decepcionante de la función anterior es que solo retorna True o False, pero no entrega la solución en ninguna parte! Para lograr esto, es posible agregar un argumento adicional a la función, en donde se vayan “anotando” los números que son considerados a participar en el conjunto. Podemos modificar la función para que ahora retorne la solución encontrada y que retorne None en caso contrario.

def sub_suma_ret(lista, valor, solucion=[]):
  if lista == []:
      if valor == 0:
          return solucion
      else:
          return None
  sol_hijo = sub_suma_ret(lista[1:], valor - lista[0], solucion+[lista[0]])
  if sol_hijo != None:
      return sol_hijo

  sol_hijo = sub_suma_ret(lista[1:], valor, solucion)
  if sol_hijo != None:
      return sol_hijo
  return None

En este programa, vemos que la solución se “anota” en el tercer parametro de la función, solucion.

Veremos ahora otro ejemplo. Queremos escribir una función que nos diga cómo recorrer completamente un tablero de ajedrez con un caballo, sin visitar dos veces el mismo cuadro. Para este ejemplo, el problema está caracterizado por un conjunto de posiciones libres, más la posición del caballo. La solución, en cambio, está caracterizada por una matriz cuadrada, digamos tab, que es tal que si tab[i][j]=n, entonces el caballo visita el cuadro de coordenada (i,j) en el n-esimo paso. Dado un problema, la decisión consiste en escoger la próxima movida del caballo. La siguiente es una posible solución:

N=6
def caballo(i,j,tablero,cuenta):
    # i,j es la posicion del caballo
    # tablero tiene la solucion hasta el momento
    # cuenta almacena cuantas decisiones hemos tomado
    if cuenta == N**2:
        return True
    delta = [[1,2],[-1,2],[1,-2],[-1,-2],[2,1],[-2,1],[2,-1],[-2,-1]]
    for d in delta:
        nuevo_i = i + d[0]
        nuevo_j = j + d[1]
        if 0 <= nuevo_i < N and 0 <= nuevo_j < N and tablero[nuevo_i][nuevo_j] == 0:
            tablero[nuevo_i][nuevo_j] = cuenta + 1
            if caballo(nuevo_i,nuevo_j,tablero,cuenta+1):
                return True
            tablero[nuevo_i][nuevo_j] = 0
    return False

tab = []
for i in range(N):
    tab.append([0]*N)

tab[0][0] = 1
caballo(0,0,tab,1)
for fila in tab:
    print(" ".join([str(x) for x in fila]))

El programa principal usa la matriz tab, que luego es modificada por la función caballo. La codificación al problema está dada por la posción del caballo (i,j), las posiciones libres (implícitamente dadas por la matriz tab). Para facilitar la condición de término, además se ocupa la variable cuenta que lleva el número de decisiones que se han tomado hasta el momento. Esta variable no es necesaria realmente (podríamos calcular su valor a partir de tab), pero permite que el programa quede un poco más elegante.

def sub_suma_auxiliar(lista, valor, resultados, solucion=[]):
    if lista == [] and valor == 0:
        resultados.append(solucion)
    sub_suma_auxiliar(lista[1:], valor - lista[0], todas, solucion + [lista[0]])
    sub_suma_auxiliar(lista[1:], valor, todas, solucion)


def sub_suma_todas(lista, valor):
    resultados = []
    sub_suma_auxiliar(lista,valor,resultados)
    return resultados

11.7 Ejemplos¶

A continuación, te proponemos varios ejemplos para que los ejecutes en tu libro interactivo.

11.8 Ejercicios¶