Recetario

Contents

  1. Recetario
    1. Decoradores
    2. Recursión

Decoradores

(en construcción) Los decoradores fueron añadidos en python 2.4 (ver PEP 318) para hacer 'envoltorios' de funciones y métodos, esto es, una función que recibe una función y devuelve otra, que permiten que sean fácilmente legibles y entendibles.

Vamos a ver esto a partir de un ejemplo leído en Stackoverflow [1].

La pregunta es ¿Cómo puedo hacer un decorador en python que haga lo siguiente? 

@hacernegrita
@hacercursiva
def say():
   return "Hello"

Que debería devolver: 

<b><i>Hello<i></b>

La respuesta corta, respondida por Paolo Bergantino sería algo así como lo siguiente:

Revisa la documentación[2] para ver como trabajan los decoradores. Aquí estaría la solución a la pregunta: 

def hacernegrita(fn):
    def wrapped():
        return "<b>" + fn() + "</b>"
    return wrapped

def hacercursiva(fn):
    def wrapped():
        return "<i>" + fn() + "</i>"
    return wrapped

@hacernegrita
@hacercursiva
def hello():
    return "hello world"

print hello() ## returns <b><i>hello world</i></b>

Con esta respuesta podríamos llegar a entender lo que hacen los decoradores pero nos quedamos un poco cortos. Veamos otra respuesta más extensa hecha por el usuario e-satis.

Creo que un pequeño tutorial sobre decoradores podría ayudar.

En Python las funciones son objetos

Para entender los decoradores, primero hay que entender que las funciones son objetos en Python. Esto tiene consecuencias importantes. Vamos a ver porqué con un ejemplo simple 

def gritar(palabra="si") :
    return palabra.capitalize()+" !"

print gritar()
# outputs : 'Si !'

# Al ser un objeto puedes asignarle la función a una variable como
# cualquier otro objeto

grito = gritar

# Date cuenta de que no usamos paréntesis, no estamos llamando a la
# función, estamos poniendo la función "gritar" en la variable "grito".
# Eso significa que podemos llamar a "gritar" desde "grito":

print grito()
# outputs : 'Si !'

# Además, podemos borrar el nombre antiguo "gritar" y la función seguirá
# estando accesible desde "grito"

del gritar
try :
    print gritar()
except NameError, e :
    print e
    #outputs : "name 'gritar' is not defined"

print grito()
# outputs : 'Si !'

Ok, quédate con lo anterior que volveremos pronto sobre ello. Otra propiedad interesante de las funciones en Python es que pueden ser definidas... dentro de otra función! 

def hablar() :

    # Puedes definir una función al vuelo en "hablar" ...
    def susurrar(palabra="si") :
        return palabra.lower()+"...";

    # ... y la usamos aquí mismo !

    print susurrar()

# Llamamos a la función "hablar", que define a la función "susurrar" CADA VEZ que la llamamos, por tanto
# a la función "susurrar" se la llama en la función "hablar".

hablar()
# outputs :
# si...

# Pero la función "susurrar" NO EXISTE fuera de la función "hablar":

try :
    print susurrar()
except NameError, e :
    print e
    #outputs : "nombre 'susurrar' no está definido"*

Functions references

Ok, ¿todavía andas por aquí? Mejor, ahora viene la parte divertida, has visto que las funciones son objetos y por tanto:

Bien, eso significa que una función puede devolver otra función :-) Echemos un vistazo: 

def vamosahablar(type="gritar"):

    # Definimos una función al vuelo
    def gritar(palabra="si") :
        return palabra.capitalize()+" !"

    def susurrar(palabra="si") :
        return palabra.lower()+"...";

    # Y devolvemos una de ellas
    if type == "gritar" :
        # No usamos "()", no estamos llamando a la función,
        # estamos devolviendo el objeto función
        return gritar
    else :
        return susurrar

# ¿Cómo usamos esta extraña bestia?

# Obtén la función y asígnasela a una variable
hablar = vamosahablar()

# Puedes ver que "hablar" es aquí un objeto función:
print hablar
#outputs : <function gritar at 0xb7ea817c>

# El objeto es aquel devuelto por la función:
print hablar()

# E incluso la puedes usar directamente si estás asalvajado:
print vamosahablar("susurrar")()
#outputs : yes...

Pero espera, hay más. Si puedes devolver una función, entonces puedes pasar una como parámetro: 

def hazAlgoAntes(func) :
    print "Hago algo antes y luego llamo a la función que me pases"
    print func()

hazAlgoAntes(grito)
#outputs :
#Hago algo antes y luego llamo a la función que me pases
#Si !

Bien, tienes todo lo que necesitas para entender los decoradores. Como puedes ver, los decoradores son 'envoltorios', que siginifica que te dejan ejecutar código antes y después de la función que están decorando sin necesidad de modificar la función misma.

Decoradores artesanales

¿Cómo lo podrías hacer manualmente?: 

# Un decorador es una función que espera otra función como parámetro
def mi_brillante_nuevo_decorador(una_funcion_a_decorar) :

    # Dentro, el decorador define una función al vuelo: el 'envoltorio' (wrapper).
    # Esta función será envuelta alrededor de la función original
    # así podría ejecutar código antes y después.
    def el_wrapper_sobre_la_funcion_original() :

        # Pon aquí el código que quieres que se ejecute ANTES que la función
        # original llamada
        print "Antes de que se ejecute la función"

        # Llama a la función aquí (usando paréntesis)
        una_funcion_a_decorar()

        # Pon aquí el código que quieres que sea ejecutado DESPUÉS que la función
        # original llamada
        print "Después de que se ejecute la función"

    # En este punto, "una_funcion_a_decorar" NO SE HA EJECUTADO NUNCA.
    # Devolvemos la función envoltorio que acabamos de crear.
    # El envoltorio contiene la función y el código a ejecutar antes y después.
    # Está listo para usarse!
    return el_wrapper_sobre_la_funcion_original

# ¿Cómo imaginar crear una función que no querrás volver a retocar nunca?
def una_funcion_autonoma() :
    print "Soy una función autónoma, ¡no osarás modificarme!"

a_stand_alone_function()
#outputs : Soy una función autónoma, ¡no osarás modificarme!

# Bien, la puedes decorar para extender su comportamiento.
# Solo pásala al decorador, la envolverá dinámicamente en
# cualquier código que quieras y te devolverá una nueva función lista para usar:

una_funcion_autonoma_decorada = mi_brillante_nuevo_decorador(una_funcion_autonoma)
una_funcion_autonoma_decorada()
#outputs :
#Antes de que se ejecute la función
#Soy una función autónoma, ¡no osarás modificarme!
#Después de que se ejecute la función

Ahora, probablemente querrás que cada vez que llamas a "una_funcion_autonoma", "una_funcion_autonoma_decorada" será llamada en su lugar. Eso es fácil, solo hay que borrar "una_funcion_autonoma" con la función devuelta por "mi_brillante_nuevo_decorador": 

una_funcion_autonoma = mi_brillante_nuevo_decorador(una_funcion_autonoma)
una_funcion_autonoma()
#outputs :
#Antes de que se ejecute la función
#Soy una función autónoma, ¡no osarás modificarme!
#Después de que se ejecute la función

# Y adivina qué, ¡esp es EXACTAMENTE lo que hacen los decoradores!

Decoradores desmitificados

El ejemplo previo, usando la sintáxis de los decoradores: 

@mi_brillante_nuevo_decorador
def otra_funcion_autonoma() :
    print "Déjame solo"

otra_función_autónoma()
#outputs :
#Antes de que se ejecute la función
#Soy una función autónoma, ¡no osarás modificarme!
#Después de que se ejecute la función

Sí, eso es todo, es así de simple. @decorador es solo una atajo a: 

otra_funcion_autonoma = mi_brillante_nuevo_decorador(otra_funcion_autonoma)

Los decoradores son solo la variante pythonica del diseño de patrones - Decorador. Hay variospatrones de diseño clásicos 'incrustados' en Python para el desarollo sencillo , como los iteradores.

Por supuesto, se pueden acumular decoradores: 

def pan(func):
    def envoltorio():
        print "</''''''\>"
        func()
        print "<\______/>"
    return envoltorio

def ingredientes(func) :
    def envoltorio() :
        print "#tomates#"
        func()
        print "~ensalada~"
    return envoltorio

def sandwich(comida="--jamon--") :
    print comida

sandwich()
#outputs : --jamon--
sandwich = pan(ingredientes(sandwich))
sandwich()
#outputs :
#</''''''\>
# #tomates#
# --jamon--
# ~ensalada~
#<\______/>

Usando la sintáxis de decoradores de Python: 

@pan
@ingredientes
def sandwich(comida="--jamon--") :
    print comida

sandwich()
#outputs :
#</''''''\>
# #tomates#
# --jamon--
# ~ensalada~
#<\______/>

El orden en que se pongan los decoradores IMPORTA: 

@ingredientes
@pan
def sandwich_extranyo(comida="--jamon--") :
    print comida

sandwich_extranyo()
#outputs :
##tomates#
#</''''''\>
# --jamon--
#<\______/>
# ~ensalada~

Finalmente, respondiendo a la pregunta

Como conclusión, fácilmente, puedes ver cómo responder a esta pregunta en stackoverflow.com: 

# El decorador para hacerlo en negrita
def hacernegrita(fn):
    # La nueva función que devuelve el decorador
    def envoltorio():
        # Inserción de algo de código antes y después
        return "<b>" + fn() + "</b>"
    return envoltorio

# El decorador para hacerlo en cursiva
def hacer cursiva(fn):
    # La nueva función que devuelve el decorador
    def envoltorio():
        # Inserción de algo de código antes y después
        return "<i>" + fn() + "</i>"
    return envoltorio

@hacernegrita
@hacercursiva
def decir():
    return "hola"

print hola() 
#outputs: <b><i>hola</i></b>

# Este es el equivalente exacto a 
def decir():
    return "hola"
decir = hacernegrita(hacercursiva(decir))

print decir() 
#outputs: <b><i>hola</i></b>

Ya nos puedes dejar felizmente, o calentarte el cerebro un poquito más y ver un uso avanzado de los decoradores.

Pasando argumentos a una función decorada 

# No es magia negra, solo tienes que dejar al envoltorio (wrapper) 
# pasar el argumento :

def un_decorador_pasando_argumentos(funcion_a_decorar) :
    def un_envoltorio_aceptando_argumentos(arg1, arg2) :
        print "Tengo argumentos ! Mira :", arg1, arg2
        funcion_a_decorar(arg1, arg2)
    return un_envoltorio_aceptando_argumentos

# Cuando estás llamando a la función devuelta por el decorador, 
# en realidad estás llamando al envoltorio(wrapper), 
# pasándole argumentos, y los dejará pasar a la función decorada

@un_decorador_pasando_argumentos
def muestra_el_nombre_entero(nombre, apellido) :
    print "Mi nombre es",nombre, apellido

muestra_el_nombre_entero("Pedro", "Picapiedra")
# outputs:
#Tengo argumentos ! Mira : Pedro Picapiedra
#Mi nombre es Pedro Picapiedra

Decorando métodos

Lo que es maravilloso en Python es que los métodos y las funciones son realmente lo mismo, excepto que los métodos esperan que su primer argumento sea una referencia del objeto actual (self). Eso significa que puedes crear un decorador para un método de la misma forma que creas decoradores para funciones, solo recuerda tener en cuenta a "self": 

def decorador_amigable_para_metodo(metodo_a_decorar):
    def envoltorio(self, mentir) :
        mentir = mentir - 3 # muy amigable :-)
        return metodo_a_decorar(self, mentir)
    return envoltorio


class Lucy(object) :

    def __init__(self) :
        self.edad = 32

    @decorador_amigable_para_metodo
    def diTuEdad(self, mentir) :
        print "Tengo %s, ¿Cuantos crees que tengo?" % (self.edad + mentir)

l = Lucy()
l.diTuEdad(-3)
#outputs: Tengo 26, ¿Cuantos crees que tengo?

Por supuesto, si haces un decorador muy general y deseas aplicarlo a cualquier función/método, no hay que preocuparse por los argumentos, se puede usar *args, **kwargs: 

def un_decorador_pasando_argumentos_arbitrarios(funcion_a_decorar) :
    # El envoltorio (wrapper) acepta cualquier argumento
    def un_envoltorio_aceptando_argumentos_arbitrarios(*args, **kwargs) :
        print "¿Tengo argumentos?:"
        print args
        print kwargs
        # Luego se desempaquetan (unpack) los argumentos aqui *args, **kwargs
        # Si no estás familiarizado con el desempaquetado (unpacking), visita:
        # http://www.saltycrane.com/blog/2008/01/how-to-use-args-and-kwargs-in-python/
        funcion_a_decorar(*args, **kwargs)
    return un_envoltorio_aceptando_argumentos_arbitrarios

@un_decorador_pasando_argumentos_arbitrarios
def funcion_sin_argumentos() :
    print "Python es chachi, sin argumentos aqui."

funcion_sin_argumentos()
#outputs
#¿Tengo argumentos?:
#()
#{}
#Python es chachi, sin argumentos aqui.

@un_decorador_pasando_argumentos_arbitrarios
def funcion_con_argumentos(a, b, c) :
    print a, b, c

funcion_con_argumentos(1,2,3)
#outputs
#¿Tengo argumentos?:
#(1, 2, 3)
#{}
#1 2 3 

@un_decorador_pasando_argumentos_arbitrarios
def funcion_con_argumentos_nombrados(a, b, c, platypus="¿Por que no?") :
    print "¿Son %s, %s y %s como platipus? %s" %\
    (a, b, c, platypus)

funcion_con_argumentos_nombrados("Bill", "Linus", "Steve", platypus="¡Ya lo creo!")
#outputs
#¿Tengo arguementos?:
#('Bill', 'Linus', 'Steve')
#{'platypus': '¡Ya lo creo!'}
#¿Son Bill, Linus y Steve como platypus? ¡Ya lo creo!

class Mary(object) :

    def __init__(self) :
        self.edad = 31

    @un_decorador_pasando_argumentos_arbitrarios
    def diTuEdad(self, mentir=-3) : # Ahora puedes agregar un valor por defecto
        print "Tengo %s, ¿Cuantos crees que tengo?" % (self.edad + mentir)

m = Mary()
m.diTuEdad()
#outputs
# ¿Tengo argumentos?:
#(<__main__.Mary object at 0xb7d303ac>,)
#{}
#Tengo 28, ¿Cuantos crees que tengo?

Pasando argumentos al decorador

Bien, ¿Ahora qué dirías sobre pasarle argumentos al decorador mismo? Bueno, esto es un poco retorcido porque un decorador debe aceptar una función como un argumento y, por tanto, no puedes pasar los argumentos de la función decorada directamente al decorador.

Antes de lanzarnos a la solución, escribamos un pequeño recordatorio: 

# Los decoradores son funciones ORDINARIAS
def mi_decorador(func) :
    print "Soy una funcion ordinaria"
    def envoltorio() :
        print "Soy una funcion devuelta por el decorador"
        func()
    return envoltorio

# Por tanto, podemos llamar al decorador sin"@"

def funcion_perezosa():
    print "zzzzzzzz"

funcion_decorada = mi_decorador(funcion_perezosa)
#ouputs : Spy una funcion ordinaria

# Ofrece como salida "Soy una funcion ordinaria", porque eso es lo que hace:
# Llamar a una funcion. Nada magico.

@mi_decorador
def funcion_peresosa() :
    print "zzzzzzzz"

#ouputs : Soy una funcion ordinaria

Es exactamente lo mismo. "mi_decorador" es llamado. Por tanto, cuando escribes @mi_decorador, le estás diciendo a Python que llame a la función etiquetada por la variables "mi_decorador". Esto es importante porque la etiqueta que le des puede apuntar directamente al decorador... o no!! ¡Vamos a empezar a ser malos! 

def creador_de_decoradores() :

    print "¡Hago decoradores! Solo soy ejecutado una vez: "+\
          "cuando me haces crear un decorador."

    def mi_decorador(func) :

        print "¡Soy un decorador! Me ejecuto solo cuando decoras una funcion."

        def envuelto() :
            print "Soy el envoltorio alrededor de la funcion decorada. "+\
                  "Me llaman cuando llamas a la función decorada. "+\
                  "Como envoltorio, devuelvo el RESULTADO de la función decorada."
            return func()

        print "Como decorador, devuelvo la función envuelta."

        return wrapped

    print "Como creador de decoradores, devuelvo un decorador"
    return mi_decorador

# Vamos a crear un decorador. Despues de todo no es mas que una nueva funcion.
nuevo_decorador = creador_de_decoradores()       
#ouputs:
#¡Hago decoradores! Solo soy ejecutado una vez: cuando me haces crear un decorador.
#Como creador de decoradores, devuelvo un decorador

# Y despues decoramos la funcion

def funcion_decorada() :
    print "Soy la funcion decorada."

funcion_decorada = nuevo_decorador(funcion_decorada)
#ouputs:
#¡Soy un decorador! Me ejecuto solo cuando decoras una funcion.
#Como decorador, devuelvo la función envuelta.

# Vamos a llamar a la funcion:
funcion_decorada()
#ouputs:
#Soy el envoltorio alrededor de la funcion decorada.
#Me llaman cuando llamas a la función decorada.
#Como envoltorio, devuelvo el RESULTADO de la función decorada.

No hay sorpresas aquí. Vamos a hacer exactamente la mismo cosa, pero vamos a evitar las variables intermedias: 

def funcion_decorada() :
    print "Soy la funcion decorada."
funcion_decorada = creador_de_decoradores()(funcion_decorada)
#ouputs:
#Creo decoradores! Soy ejecutado solo una vez: cuando me haces crear un decorador.
#Como creador de decoradores, devuelvo un decorador
#Soy un decorador ! Soy ejecutado unicamente cuando decoras una funcion.
#como decorador, devuelvo la funcion envuelta (wrapped).

# Finalmente:
funcion_decorada()    
#ouputs:
#Soy el envoltorio (wrapper) alrededor de la funcion decorada. Me llaman cuando llamas a la función decorada.
#Como el envoltorio (wrapper), Devuelvo el RESULTADO de la funcion decorada.
#Soy la funcion decorada.

Vamos a hacerlo de nuevo, pero incluso más corto: 

@creador_de_decoradores()
def funcion_decorada() :
    print "Soy la funcion decorada."
#ouputs:
#Creo decoradores! Soy ejecutado solo una vez: cuando me haces crear un decorador.
#Como creador de decoradores, devuelvo un decorador
#Soy un decorador ! Soy ejecutado unicamente cuando decoras una funcion.
#como decorador, devuelvo la funcion envuelta (wrapped).

#Eventualmente: 
funcion_decorada()    
#ouputs:
#Soy el envoltorio (wrapper) alrededor de la funcion decorada. Me llaman cuando llamas a la función decorada.
#Como el envoltorio (wrapper), Devuelvo el RESULTADO de la funcion decorada.
#Soy la funcion decorada.

[1] Ejemplo en stackoverflow

[2] Documentación oficial

Recursión

Recursividad, para entenderla, primero hay que entenderla.

La recursividad, recursión o recurrencia (en toda la receta usaremos cualquiera de estos términos para referirnos a lo mismo) es una técnica de programación que permite crear una función que se puede llamar a sí misma. Existen ciertos tipos de problemas matemáticos que se ajustan bien a una solución mediante recursividad.

Podríamos empezar definiendo la siguiente función: 

   1 def recursividad():
   2     return recursividad()

Si se usa esta función, teóricamente, debería estar corriendo infinitamente pero veremos que el programa falla: 

   1     >> return recursividad()
   2 RuntimeError: maximum recursion depth exceeded

Esto sucede porque cada vez que se usa una función usa un poco de memoria y después de que se han hecho suficientes llamadas a la función el programa termina con el mensaje de error que indica que se ha ‘superado la máxima profundidad de recursión’ (RuntimeError: maximum recursion depth exceeded). Ver sys.getrecursionlimit() y sys.setrecursionlimit() para solucionar esto en problemas concretos, por defecto, el límite es 1000. Por tanto, como vemos, las funciones recursivas pueden ser computacionalmente exigentes pero, en algunos casos, se pueden expresar los algoritmos de forma mucho más natural.

La llamada a esta función presenta una recursión infinita, como si se empezara un bucle while True sin break o return, es decir, un bucle infinito.

Pero lo que queremos es una función recursiva que haga algo útil. Una función recursiva útil normalmente se compone de de las siguientes partes:

El asunto aquí es que partiendo el problema en pequeñas piezas, la recursión no puede continuar para siempre debido a que siempre se terminará con la parte más pequeña del problema, la cual está cubierta por el caso base.

Por tanto, tenemos una función que se puede llamar a sí misma. Pero, ¿cómo es posible? No es tan extraño como pueda parecer. Como se ha comentado anteriormente, cada vez que se llama a una función, se crea un nuevo namespace para esa llamada específica. Esto significa que cuando una función se llama a sí misma en realidad estamos hablando de dos funciones diferentes (o la misma función pero con dos namespaces diferentes).

Dos clásicos en este tema son el factorial y la exponenciación. Primero, vamos a calcular el factorial de un número n. El factorial de n se define como n x (n–1) x (n–2) x . . . x 1. ¿Cómo lo calcularías? Siempre se puede usar un bucle: def factorial(n): 

   1 def factorial(n):
   2     resultado = n
   3     for i in range(1,n):
   4         resultado *= i
   5     return resultado

Esto funciona y es una implementación sencilla. Basicamente, lo que hace es lo siguiente: primero, n se asigna al resultado; luego, el resultado se multiplica para cada uno de los números entre q y n-1; finalmente, se devuelve el resultado. Pero se podría hacer esto de forma diferente. La clave es la definición matemática del factorial que podría ser algo así: • El factorial de 1 es 1. • El factorial de un número n más grande que 1 es el producto de n por el factorial de n–1. Como se puede ver, esta definición es exactamente equivalente a lo definido anteriormente en esta receta. Ahora vamos a considerar como implementar esta definición como una función, de hecho, es muy sencillo una vez que se ha entendido la definición: 

   1 def factorial(n):
   2     if n == 1:
   3         return 1
   4     else:
   5         return n * factorial(n-1)

Esta es una implementación directa de la definición.Solo recuerda que la llamada a la función factorial(n) es una entidad diferente a la llamada a factorial(n-1).

Vamos a considerar otro ejemplo. Imaginemos que queremos calcular exponentes como la función incorporada pow o el operador **. Se puede definir la exponenciación (entera) de un número de diversas formas. Vamos a empezar con una simple: potencia(x,n) (x a la potencia de n) es el número x multiplicado por si mismo n-1 veces. Por ejemplo, potencia(2,3) is multiplicar 2 por si mismo tres veces, o 2 x 2 x 2 = 8. Esto es fácil de implementar: 

   1 def potencia(x, n):
   2     resultado = 1
   3     for i in range(n):
   4         resultado *= x
   5     return resultado

Esta es una dulce y simple función pero, de nuevo, podemos implementar lo mismo con una función recursiva:

Otra vez, como puedes ver, esto da exactamente el mismo resultado que en la definición más simple e iterativa anterior. Entender la definición es la parte más difícil, implementarla es la fácil: 

   1 def potencia(x, n):
   2     if n == 0:
   3         return 1
   4     else:
   5         return x * potencia(x, n-1)

Simplemente hemos traducido la definición formal anterior a una descripción textual en Python.

Entonces, ¿cuál es el puntazo de la recursión?, ¿podrías usar bucles como alternativa? La verdad es que sí, podrías y, de hecho, en la mayoría de los casos será, posiblemente, ligeramente más eficiente. Pero en muchos casos, la recursión será más legible, en algunos casos mucho más legible, especialmente si entiendes la definición recursiva de una función. Puedes considerar no usar nunca una función recursiva pero en muchos casos quizá tengas que entender los algoritmos recursivos y funciones creados por otros.

Otro clásico de la recursión: la búsqueda binaria. Como otro ejemplo práctico de la recursión, vamos a echarle un vistazo al algoritmo llamado búsqueda binaria. Quizá conozcas el juego en el cual tienes que adivinar lo que está pensando alguien haciendo 20 preguntas con respuesta Sí o No. Para wu tus preguntas sean lo más adecuadas posibles lo que intentarás es acortar el número de posibilidades en la mitad (más o menos). Por ejemplo, si sabes que la solución es una persona puedes preguntar, ‘¿estás pensando en una mujer?’, no empezarás preguntando, ‘¿estás pensando en John Cleese?’ a no ser que tengas una corazonada.

Otra versión del juego para aquellos que les gustan más los números preferiras la versión sobre acertar un número. Por ejemplo,tu coleguilla está pensando en un número entre 1 y 100, y tú debes adivinar cual es. De acuerdo, lo puedes hacer a partir de 100 preguntas pero, ¿cuántas necesitas en realidad? Aunque te pueda sorprender solo necesitas 7 preguntas. La primera pregunta podría ser algo así como, ¿tu número es más grande que 50? Si es así, la siguiente pregunta sería, ¿es mayor que 75? La idea es ir haciendo la mitad de cada intervalo hasta que encuentres el número. Se puede hacer esto sin mucho pensar (que cansa).

Esta misma táctica se puede seguir en muchos otros contextos. Un problema común es encontrar si un número se encuentra en una secuencia (ordenada) e, incluso, encontrar donde se encuentra.

Otra vez, podemos seguir el mismo procedimiento, ¿se encuentra el número en la mitad derecha de la secuencia? Si no se encuentra ahí, ¿se encuentra en el segundo cuarto (a la derecha de la mitad de la mitad izquierda, ¡¡ups, que mareo!!) y así hasta que encontremos lo que buscamos. Mantenemos un límite superior e inferior que definen el intervalo en el que se debería encontrar el número y partimos esta secuencia con cada nueva pregunta.

El algoritmo se presta a una definición e implementación recursiva. Vamos a definir antes el algoritmo para no meter la pata y saber lo que estamos haciendo:

La clave para el caso recursivo es que los números estén ordenados, de esta forma, cuando encuentras el elemento medio, lo puedes comparar al número que estás buscando. Si tu número es más grande entonces debe estar a la derecha y si es menor debe estar a la izquierda. La parte recursiva está en 'seguir buscando en la mitad apropiada del intervalo', así la búsqueda se realiza en la forma descrita en la definición. (Debes notar que el algoritmo de búsqueda devuelve la posición donde el número debería estar, si no está presente en la secuencia, esta posición estará ocupada por otro nombre).

Ahora estás listo para implementar la búsqueda binaria: 

   1 def search(sequence, number, lower, upper):
   2     if lower == upper:
   3         assert number == sequence[upper]
   4         return upper
   5     else:
   6         middle = (lower + upper) // 2
   7         if number > sequence[middle]:
   8             return search(sequence, number, middle+1, upper)
   9         else:
  10             return search(sequence, number, lower, middle)

Esto hace exactamente lo que la definición dice que debería: if lower == upper, entonces devuelve upper, donde upper es el límite superior. Notad que asumimos/afirmamos (assert) que el número que estamos buscando ha sido encontrado (number == sequence[upper]). Si tdavía no has alcanzado tu caso base buscas las mitad, chequeamos si el número está a la izquierda o a la derechay llamamos a la búsqueda recursivamente con los nuevos límites. Podríamos crear esto incluso con una forma más sencilla de usar haciendo que las especificaciones de límites sean opcionales. Siplemente añadiremos la siguiente condición al inicio de la función: 

   1 def search(sequence, number, lower=0, upper=None):
   2     if upper is None: upper = len(sequence)-1
   3     ...

Ahora, si no has suministrado los límites los límites serán la primera y última posiciones de la secuencia. Vamos a ver si esto funciona: 

   1 >>> seq = [34, 67, 8, 123, 4, 100, 95]
   2 >>> seq.sort()
   3 >>> seq
   4 [4, 8, 34, 67, 95, 100, 123]
   5 >>> search(seq, 34)
   6 2
   7 >>> search(seq, 100)
   8 5

Pero, ¿por qué liarnos tanto con todo esto? Podríamos usar el método index de las listas y, si buscas implementar esto tú mismo, podrías hacer un bucle empezando por el principio e iterando a lo largo hasta que se encuentre el número. Por supuesto, usar index está bien. Pero usar un bucle simple podría ser algo ineficiente. Recuerda que comentamos anteriormente que necesitabamos solo siete preguntar para encontrar un número entre 100 pero el bucle necesitará 100 preguntas en el peor de los escenarios. Esto se vuelve más crítico si la lista tiene 100,000,000,000,000,000,000,000,000,000,000,000 elementos este tipo de cosas empiezan a ser importantes. La búsqueda binaria necesitaría solo 117 preguntas.

Otro ejemplo donde podría resultar más sencillo usar recursión sería en el caso de aplanar listas que contienen otras listas. Hacer esto con bucles podría ser tedioso y complejo, sin embargo, mediante recursión podríamos tener lo siguiente: 

   1 def flatten(lists):
   2     for s in lists:
   3         if isinstance(s,list):
   4             flatten(s)
   5         else:
   6             print(s)
   7 
   8 items = [[1,2,3],[4,5,[5,6]],[7,8,9]]
   9 flatten(items)     # Prints 1 2 3 4 5 6 7 8 9

Referencias (la receta está basada, en una traducción libre, de [2] añadiendo un par de cosas de el resto de referencias):

[1] Head First Programming. A learner's guide to programming using the Python language

[2] Beginning Python: From Novice to Professional

[3] Learning to program

[4] Python essencial reference

Recetario (last edited 02-06-2011 10:49:02 by Kiko Correoso)