Recetario

Recetario
T abla de C ont eni dos 1. 1. 2. Recetario Decoradores Recursin

Decoradores
(en construccin) Los decoradores fueron aadidos en python 2.4 (ver PEP 318) para hacer 'envoltorios' de funciones y mtodos, esto es, una funcin que recibe una funcin y devuelve otra, que permiten que sean fcilmente legibles y entendibles. Vamos a ver esto a partir de un ejemplo ledo en Stackoverflow [1]. La pregunta es Cmo puedo hacer un decorador en python que haga lo siguiente?
@hacernegrita @hacercursiva def say(): return "Hello"

Que debera devolver:

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

La respuesta corta, respondida por Paolo Bergantino sera algo as como lo siguiente: Revisa la documentacin[2] para ver como trabajan los decoradores. Aqu estara la solucin 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 podramos llegar a entender lo que hacen los decoradores pero nos quedamos un poco cortos. Veamos otra respuesta ms extensa hecha por el usuario e-satis. Creo que un pequeo tutorial sobre decoradores podra 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 funcin a una variable como # cualquier otro objeto grito = gritar # Date cuenta de que no usamos parntesis, no estamos llamando a la # funcin, estamos poniendo la funcin "gritar" en la variable "grito". # Eso significa que podemos llamar a "gritar" desde "grito": print grito() # outputs : 'Si !' # Adems, podemos borrar el nombre antiguo "gritar" y la funcin 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, qudate con lo anterior que volveremos pronto sobre ello. Otra propiedad interesante de las funciones en Python es que pueden ser definidas... dentro de otra funcin!
def hablar() : # Puedes definir una funcin al vuelo en "hablar" ... def susurrar(palabra="si") : return palabra.lower()+"..."; # ... y la usamos aqu mismo !

print susurrar() # Llamamos a la funcin "hablar", que define a la funcin "susurrar" CADA VEZ que la llamamos, por tanto # a la funcin "susurrar" se la llama en la funcin "hablar". hablar() # outputs : # si... # Pero la funcin "susurrar" NO EXISTE fuera de la funcin "hablar": try : print susurrar() except NameError, e : print e #outputs : "nombre 'susurrar' no est definido"*

Functions references Ok, todava andas por aqu? Mejor, ahora viene la parte divertida, has visto que las funciones son objetos y por tanto:

pueden ser asignadas a una variable; pueden ser definidas en otra funcin. Echemos un

Bien, eso significa que una funcin puede devolver otra funcin vistazo:
def vamosahablar(type="gritar"): # Definimos una funcin 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 funcin, # estamos devolviendo el objeto funcin return gritar else : return susurrar # Cmo usamos esta extraa bestia? # Obtn la funcin y asgnasela a una variable hablar = vamosahablar() # Puedes ver que "hablar" es aqu un objeto funcin: print hablar #outputs : <function gritar at 0xb7ea817c> # El objeto es aquel devuelto por la funcin:

print hablar() # E incluso la puedes usar directamente si ests asalvajado: print vamosahablar("susurrar")() #outputs : yes...

Pero espera, hay ms. Si puedes devolver una funcin, entonces puedes pasar una como parmetro:
def hazAlgoAntes(func) : print "Hago algo antes y luego llamo a la funcin que me pases" print func() hazAlgoAntes(grito) #outputs : #Hago algo antes y luego llamo a la funcin 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 cdigo antes y despus de la funcin que estn decorando sin necesidad de modificar la funcin misma. Decoradores artesanales Cmo lo podras hacer manualmente?:
# Un decorador es una funcin que espera otra funcin como parmetro def mi_brillante_nuevo_decorador(una_funcion_a_decorar) : # Dentro, el decorador define una funcin al vuelo: el 'envoltorio' (wrapper). # Esta funcin ser envuelta alrededor de la funcin original # as podra ejecutar cdigo antes y despus. def el_wrapper_sobre_la_funcion_original() : # Pon aqu el cdigo que quieres que se ejecute ANTES que la funcin # original llamada print "Antes de que se ejecute la funcin" # Llama a la funcin aqu (usando parntesis) una_funcion_a_decorar() # Pon aqu el cdigo que quieres que sea ejecutado DESPUS que la funcin # original llamada print "Despus de que se ejecute la funcin" # En este punto, "una_funcion_a_decorar" NO SE HA EJECUTADO NUNCA. # Devolvemos la funcin envoltorio que acabamos de crear. # El envoltorio contiene la funcin y el cdigo a ejecutar antes y despus. # Est listo para usarse! return el_wrapper_sobre_la_funcion_original

# Cmo imaginar crear una funcin que no querrs volver a retocar nunca? def una_funcion_autonoma() : print "Soy una funcin autnoma, no osars modificarme!" a_stand_alone_function() #outputs : Soy una funcin autnoma, no osars modificarme! # Bien, la puedes decorar para extender su comportamiento. # Solo psala al decorador, la envolver dinmicamente en # cualquier cdigo que quieras y te devolver una nueva funcin 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 funcin #Soy una funcin autnoma, no osars modificarme! #Despus de que se ejecute la funcin

Ahora, probablemente querrs que cada vez que llamas a "una_funcion_autonoma", "una_funcion_autonoma_decorada" ser llamada en su lugar. Eso es fcil, solo hay que borrar "una_funcion_autonoma" con la funcin 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 funcin #Soy una funcin autnoma, no osars modificarme! #Despus de que se ejecute la funcin # Y adivina qu, esp es EXACTAMENTE lo que hacen los decoradores!

Decoradores desmitificados El ejemplo previo, usando la sintxis de los decoradores:

@mi_brillante_nuevo_decorador def otra_funcion_autonoma() : print "Djame solo" otra_funcin_autnoma() #outputs : #Antes de que se ejecute la funcin #Soy una funcin autnoma, no osars modificarme! #Despus de que se ejecute la funcin

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 diseo de patrones Decorador. Hay variospatrones de diseo clsicos '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 sintxis 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 conclusin, fcilmente, puedes ver cmo responder a esta pregunta en stackoverflow.com:
# El decorador para hacerlo en negrita def hacernegrita(fn): # La nueva funcin que devuelve el decorador def envoltorio(): # Insercin de algo de cdigo antes y despus return "<b>" + fn() + "</b>" return envoltorio # El decorador para hacerlo en cursiva def hacer cursiva(fn): # La nueva funcin que devuelve el decorador def envoltorio(): # Insercin de algo de cdigo antes y despus 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 ms y ver un uso avanzado de los decoradores. Pasando argumentos a una funcin 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 ests llamando a la funcin devuelta por el decorador, # en realidad ests llamando al envoltorio(wrapper), # pasndole argumentos, y los dejar pasar a la funcin 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 mtodos Lo que es maravilloso en Python es que los mtodos y las funciones son realmente lo mismo, excepto que los mtodos esperan que su primer argumento sea una referencia del objeto actual (self). Eso significa que puedes crear un decorador para un mtodo 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 funcin/mtodo, 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 ests familiarizado con el desempaquetado (unpacking), visita: # http://www.saltycrane.com/blog/2008/01/how-to-use-args-andkwargs-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 diras sobre pasarle argumentos al decorador mismo? Bueno, esto es un poco retorcido porque un decorador debe aceptar una funcin como un argumento y, por tanto, no puedes pasar los argumentos de la funcin decorada directamente al decorador. Antes de lanzarnos a la solucin, escribamos un pequeo 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 ests diciendo a Python que llame a la funcin 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 funcin decorada. "+\ "Como envoltorio, devuelvo el RESULTADO de la funcin decorada." return func() print "Como decorador, devuelvo la funcin 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 funcin envuelta. # Vamos a llamar a la funcion: funcion_decorada() #ouputs: #Soy el envoltorio alrededor de la funcion decorada. #Me llaman cuando llamas a la funcin decorada. #Como envoltorio, devuelvo el RESULTADO de la funcin 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 funcin decorada. #Como el envoltorio (wrapper), Devuelvo el RESULTADO de la funcion decorada.

#Soy la funcion decorada.

Vamos a hacerlo de nuevo, pero incluso ms 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 funcin decorada. #Como el envoltorio (wrapper), Devuelvo el RESULTADO de la funcion decorada. #Soy la funcion decorada.

[1] Ejemplo en stackoverflow [2] Documentacin oficial

Recursin
Recursividad, para entenderla, primero hay que entenderla. La recursividad, recursin o recurrencia (en toda la receta usaremos cualquiera de estos trminos para referirnos a lo mismo) es una tcnica de programacin que permite crear una funcin que se puede llamar a s misma. Existen ciertos tipos de problemas matemticos que se ajustan bien a una solucin mediante recursividad. Podramos empezar definiendo la siguiente funcin:
[des]activar nros. de lnea 1 def recursividad(): 2 return recursividad()

Si se usa esta funcin, tericamente, debera estar corriendo infinitamente pero veremos que el programa falla:
[des]activar nros. de lnea 1 >> return recursividad() 2 RuntimeError: maximum recursion depth exceeded

Esto sucede porque cada vez que se usa una funcin usa un poco de memoria y despus de que se han hecho suficientes llamadas a la funcin el programa termina con el mensaje de error que indica que se ha superado la mxima

profundidad de recursin (RuntimeError: maximum recursion depth exceeded). Ver sys.getrecursionlimit() y sys.setrecursionlimit() para solucionar esto en problemas concretos, por defecto, el lmite 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 ms natural. La llamada a esta funcin presenta una recursin infinita, como si se empezara un bucle while True sin break o return, es decir, un bucle infinito. Pero lo que queremos es una funcin recursiva que haga algo til. Una funcin recursiva til normalmente se compone de de las siguientes partes:

- Un caso base (para el problema posible ms pequeo) cuando la funcin devuelve un valor directamente (este caso se usa para parar la recursin). - Un caso recursivo, el cual contiene una o ms llamadas recursivas sobre partes ms pequeas del problema.

El asunto aqu es que partiendo el problema en pequeas piezas, la recursin no puede continuar para siempre debido a que siempre se terminar con la parte ms pequea del problema, la cual est cubierta por el caso base. Por tanto, tenemos una funcin que se puede llamar a s misma. Pero, cmo es posible? No es tan extrao como pueda parecer. Como se ha comentado anteriormente, cada vez que se llama a una funcin, se crea un nuevo namespace para esa llamada especfica. Esto significa que cuando una funcin se llama a s misma en realidad estamos hablando de dos funciones diferentes (o la misma funcin pero con dos namespaces diferentes). Dos clsicos en este tema son el factorial y la exponenciacin. Primero, vamos a calcular el factorial de un nmero n. El factorial de n se define como n x (n1) x (n 2) x . . . x 1. Cmo lo calcularas? Siempre se puede usar un bucle: def factorial(n):
[des]activar nros. de lnea 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 implementacin sencilla. Basicamente, lo que hace es lo siguiente: primero, n se asigna al resultado; luego, el resultado se multiplica para cada uno de los nmeros entre q y n-1; finalmente, se devuelve el resultado. Pero se podra hacer esto de forma diferente. La clave es la definicin matemtica del factorial que podra ser algo as: El factorial de 1 es 1. El factorial de un nmero n ms grande que 1 es el producto de n por el factorial de n1. Como se puede ver, esta definicin es exactamente equivalente a lo definido anteriormente en esta receta. Ahora vamos a considerar como implementar esta definicin como una funcin, de hecho, es muy sencillo una vez que se ha entendido la definicin:
[des]activar nros. de lnea 1 def factorial(n): 2 if n == 1:

3 4 5

return 1 else: return n * factorial(n-1)

Esta es una implementacin directa de la definicin.Solo recuerda que la llamada a la funcin 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 funcin incorporada pow o el operador **. Se puede definir la exponenciacin (entera) de un nmero de diversas formas. Vamos a empezar con una simple: potencia(x,n) (x a la potencia de n) es el nmero 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 fcil de implementar:
[des]activar nros. de lnea 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 funcin pero, de nuevo, podemos implementar lo mismo con una funcin recursiva:

potencia(x, 0) es 1 para todos los nmeros x. potencia(x, n) para n > es el producto de x y potencia(x, n-1).

Otra vez, como puedes ver, esto da exactamente el mismo resultado que en la definicin ms simple e iterativa anterior. Entender la definicin es la parte ms difcil, implementarla es la fcil:
[des]activar nros. de lnea 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 definicin formal anterior a una descripcin textual en Python. Entonces, cul es el puntazo de la recursin?, podras usar bucles como alternativa? La verdad es que s, podras y, de hecho, en la mayora de los casos ser, posiblemente, ligeramente ms eficiente. Pero en muchos casos, la recursin ser ms legible, en algunos casos mucho ms legible, especialmente si entiendes la definicin recursiva de una funcin. Puedes considerar no usar nunca una funcin recursiva pero en muchos casos quiz tengas que entender los algoritmos recursivos y funciones creados por otros. Otro clsico de la recursin: la bsqueda binaria. Como otro ejemplo prctico de la recursin, vamos a echarle un vistazo al algoritmo llamado bsqueda 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 ms adecuadas posibles lo que intentars es acortar el nmero de posibilidades en la mitad (ms o menos). Por ejemplo, si sabes que la solucin es una persona puedes preguntar, ests pensando en una mujer?, no empezars preguntando, ests pensando en John Cleese? a no ser que tengas una corazonada. Otra versin del juego para aquellos que les gustan ms los nmeros preferiras la versin sobre acertar un nmero. Por ejemplo,tu coleguilla est pensando en un nmero entre 1 y 100, y t debes adivinar cual es. De acuerdo, lo puedes hacer a partir de 100 preguntas pero, cuntas necesitas en realidad? Aunque te pueda sorprender solo necesitas 7 preguntas. La primera pregunta podra ser algo as como, tu nmero es ms grande que 50? Si es as, la siguiente pregunta sera, es mayor que 75? La idea es ir haciendo la mitad de cada intervalo hasta que encuentres el nmero. Se puede hacer esto sin mucho pensar (que cansa). Esta misma tctica se puede seguir en muchos otros contextos. Un problema comn es encontrar si un nmero se encuentra en una secuencia (ordenada) e, incluso, encontrar donde se encuentra. Otra vez, podemos seguir el mismo procedimiento, se encuentra el nmero 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 lmite superior e inferior que definen el intervalo en el que se debera encontrar el nmero y partimos esta secuencia con cada nueva pregunta. El algoritmo se presta a una definicin e implementacin recursiva. Vamos a definir antes el algoritmo para no meter la pata y saber lo que estamos haciendo:

-Si los lmites superior e inferior son iguales, ambos se refieren a la posicin correcta del nmero y solo hemos de devolver esta solucin. -Si no es as, hay que encontrar la mitad del intervalo (el promedio de los lmites superior e inferior), y encontrar si el nmero se encuentra en la mitad derecha o izquierda. Y mantenemos la bsqueda en la mitad correcta.

La clave para el caso recursivo es que los nmeros estn ordenados, de esta forma, cuando encuentras el elemento medio, lo puedes comparar al nmero que ests buscando. Si tu nmero es ms 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 bsqueda se realiza en la forma descrita en la definicin. (Debes notar que el algoritmo de bsqueda devuelve la posicin donde el nmero debera estar, si no est presente en la secuencia, esta posicin estar ocupada por otro nombre). Ahora ests listo para implementar la bsqueda binaria:
[des]activar nros. de lnea 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 9 10

return search(sequence, number, middle+1, upper) else: return search(sequence, number, lower, middle)

Esto hace exactamente lo que la definicin dice que debera: if lower == upper, entonces devuelve upper, donde upper es el lmite superior. Notad que asumimos/afirmamos (assert) que el nmero que estamos buscando ha sido encontrado (number == sequence[upper]). Si tdava no has alcanzado tu caso base buscas las mitad, chequeamos si el nmero est a la izquierda o a la derechay llamamos a la bsqueda recursivamente con los nuevos lmites. Podramos crear esto incluso con una forma ms sencilla de usar haciendo que las especificaciones de lmites sean opcionales. Siplemente aadiremos la siguiente condicin al inicio de la funcin:
[des]activar nros. de lnea 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 lmites los lmites sern la primera y ltima posiciones de la secuencia. Vamos a ver si esto funciona:
[des]activar nros. de lnea 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? Podramos usar el mtodo index de las listas y, si buscas implementar esto t mismo, podras hacer un bucle empezando por el principio e iterando a lo largo hasta que se encuentre el nmero. Por supuesto, usar index est bien. Pero usar un bucle simple podra ser algo ineficiente. Recuerda que comentamos anteriormente que necesitabamos solo siete preguntar para encontrar un nmero entre 100 pero el bucle necesitar 100 preguntas en el peor de los escenarios. Esto se vuelve ms crtico 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 bsqueda binaria necesitara solo 117 preguntas. Otro ejemplo donde podra resultar ms sencillo usar recursin sera en el caso de aplanar listas que contienen otras listas. Hacer esto con bucles podra ser tedioso y complejo, sin embargo, mediante recursin podramos tener lo siguiente:
[des]activar nros. de lnea 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 traduccin libre, de [2] aadiendo 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 (ltima edicin 02-06-2011 10:49:02 efectuada por Kiko Correoso)