<div dir="ltr"><div class="gmail_default" style="font-family:georgia,serif;font-size:large">Hola a todos,</div><div class="gmail_default" style="font-family:georgia,serif;font-size:large"><br></div><div class="gmail_default" style="font-family:georgia,serif;font-size:large">La recursividad en python es muy limitada. Pero lo que viene a descubrir es algo que se podría haber hecho mejor con generadores. En cuanto al otro uso, sería una aplicación parcial de argumentos (functools.partial).</div><div class="gmail_default" style="font-family:georgia,serif;font-size:large"><br></div><div class="gmail_default" style="font-family:georgia,serif;font-size:large">Aún así, hay algoritmos recursivos que no son tan fácilmente transcribibles en iterables.<br></div><div class="gmail_default" style="font-family:georgia,serif;font-size:large"><br></div><div class="gmail_default" style="font-family:georgia,serif;font-size:large"><br></div><div class="gmail_default" style="font-family:georgia,serif;font-size:large">Saludos.</div><div class="gmail_default" style="font-family:georgia,serif;font-size:large"><br></div></div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">El sáb, 2 ene 2021 a las 16:55, Jesus Cea (<<a href="mailto:jcea@jcea.es">jcea@jcea.es</a>>) escribió:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">El artículo requiere autenticarse para leerlo, así que voy a ser pirata <br>
y enviar una transcripción. La técnica me parece muy interesante. <br>
Podemos comentarla en la tertulia del martes próximo.<br>
<br>
<<a href="https://towardsdatascience.com/dont-use-recursion-in-python-any-more-918aad95094c" rel="noreferrer" target="_blank">https://towardsdatascience.com/dont-use-recursion-in-python-any-more-918aad95094c</a>><br>
<br>
Transcripción si no quieres autenticarte. Las imágenes se pierden, pero <br>
espero que se entienda el sentido general:<br>
<br>
"""<br>
Don’t Use Recursion In Python Any More<br>
Python Closure — A Pythonic technique you must know<br>
Christopher Tao<br>
Christopher Tao<br>
Nov 22, 2020·8 min read<br>
<br>
I was such a programmer who likes recursive functions very much before, <br>
simply because it is very cool and can be used to show off my <br>
programming skills and intelligence. However, in most of the <br>
circumstances, recursive functions have very high complexity that we <br>
should avoid using.<br>
<br>
One of the much better solutions is to use Dynamic Planning when <br>
possible, which is probably the best way to solve a problem that can be <br>
divided into sub-problems. One of my previous articles has illustrated <br>
the power of Dynamic Planning.<br>
Using Dynamic Planning to Help Trump Win the Elections<br>
Dynamic Planning in Python for optimising Election Promotion<br>
<a href="http://towardsdatascience.com" rel="noreferrer" target="_blank">towardsdatascience.com</a><br>
<br>
However, in this article, I’m going to introduce another technique in <br>
Python that can be utilised as an alternative to the recursive function. <br>
It won’t outperform Dynamic Planning, but much easier in term of <br>
thinking. In other words, we may sometimes be struggling to make Dynamic <br>
Planning works because of the abstraction of the ideas, but it will be <br>
much easier to use closure.<br>
What is Python Closure?<br>
Image for post<br>
Image for post<br>
Photo by Free-Photos on Pixabay<br>
<br>
First of all, let me use a simple example to demonstrate what is a <br>
closure in Python. Look at the function below:<br>
<br>
def outer():<br>
x = 1<br>
def inner():<br>
print(f'x in outer function: {x}')<br>
return inner<br>
<br>
The function outer is defined with another function inner inside itself, <br>
and the function outer returns the function inner as the “return value” <br>
of the function.<br>
<br>
In this case, the nested function is called a closure in Python. If we <br>
check the “return value” of the outer function, we will find that the <br>
returned value is a function.<br>
Image for post<br>
Image for post<br>
<br>
What does closure do? Because it returned a function, we can run this <br>
function, of course.<br>
Image for post<br>
Image for post<br>
<br>
OK, we can see that the inner function can access variables defined in <br>
the outer function. Usually, we don’t use closure in such a way shown as <br>
above, because it is kind of ugly. We usually want to define another <br>
function to hold the function returned by the closure.<br>
Image for post<br>
Image for post<br>
<br>
Therefore, we can also say that in a Python closure, we defined a <br>
function that defines functions.<br>
Access Outer Variables from the Inner Function<br>
Image for post<br>
Image for post<br>
Photo by igorovsyannykov on Pixabay<br>
<br>
How can we use a closure to replace a recursive then? Don’t be too <br>
hurry. Let’s have a look at another problem here, which is accessing <br>
outer variables from the inner function.<br>
<br>
def outer():<br>
x = 1<br>
def inner():<br>
print(f'x in outer function (before modifying): {x}')<br>
x += 1<br>
print(f'x in outer function (after modifying): {x}')<br>
return inner<br>
<br>
In the closure above-shown, we want to add 1 to the outer variable x in <br>
the inner function. However, this won’t work straightforward.<br>
Image for post<br>
Image for post<br>
<br>
By default, you won’t be able to access the outer variable from the <br>
inner function. However, just like how we define a global variable in <br>
Python, we can tell the inner function of a closure that the variable <br>
should not be considered as a “local variable”, by using the nonlocal <br>
keyword.<br>
<br>
def outer():<br>
x = 1<br>
def inner():<br>
nonlocal x<br>
print(f'x in outer function (before modifying): {x}')<br>
x += 1<br>
print(f'x in outer function (after modifying): {x}')<br>
return inner<br>
<br>
Now, let’s say we want to add the variable x by 1 for five times. We can <br>
simply write a for loop to achieve this.<br>
<br>
f = outer()for i in range(5):<br>
print(f'Run {i+1}')<br>
f()<br>
print('\n')<br>
<br>
Image for post<br>
Image for post<br>
Write a Fibonacci Function Using Closure<br>
Image for post<br>
Image for post<br>
Photo by Free-Photos on Pixabay<br>
<br>
Fibonacci is commonly used as a “hello world” example of recursive <br>
functions. If you don’t remember it, don’t worry, it is pretty simple to <br>
be explained.<br>
<br>
A Fibonacci sequence is a series of numbers that every number is the sum <br>
of the two numbers before it. The first two numbers, X₀ and X₁, are <br>
special. They are 0 and 1 respectively. Since X₂, the patter is as <br>
above-mentioned, it is the sum of X₀ and X₁, so X₂=1. Then, X₃ is X₁ + <br>
X₂ =2, X₄ is X₂ + X₃=3, X₅ is X₃ + X₄ = 5, and so on.<br>
<br>
The recursive function requires us to think reversely from the “current <br>
scenario” to the “previous scenario”, and eventually what are the <br>
terminate conditions. However, by using the closure, we can think about <br>
the problem more naturally.<br>
<br>
See the code below that the Fibonacci function is implemented using a <br>
closure.<br>
<br>
def fib():<br>
x1 = 0<br>
x2 = 1<br>
def get_next_number():<br>
nonlocal x1, x2<br>
x3 = x1 + x2<br>
x1, x2 = x2, x3<br>
return x3<br>
return get_next_number<br>
<br>
We know that the Fibonacci starts with two special number X₀=0 and X₁=1, <br>
so we just simply define them in the outer function. Then, the inner <br>
function get_next_number is simply return the sum of the two numbers it <br>
got from the outer function.<br>
<br>
Additionally, don’t forget to update X₀ and X₁ with X₁ and X₂. In fact, <br>
we can simplify the code:<br>
<br>
...<br>
x3 = x1 + x2<br>
x1, x2 = x2, x3<br>
return x3<br>
<br>
to<br>
<br>
x0, x1 = x1, x0 + x1<br>
return x1<br>
<br>
This is updating the two variables first and then return the second, <br>
which is equivalent to the previous code snippet.<br>
<br>
Then, we can use this closure to calculate Fibonacci numbers. For <br>
example, we want to show the Fibonacci sequence up to the 20th number.<br>
<br>
fibonacci = fib()for i in range(2, 21):<br>
num = fibonacci()<br>
print(f'The {i}th Fibonacci number is {num}')<br>
<br>
Image for post<br>
Image for post<br>
Compare the Performance<br>
Image for post<br>
Image for post<br>
Photo by KahlOrr on Pixabay<br>
<br>
Alright, we knew that we can use closure to replace a recursive function <br>
in the previous section. How about the performance? Let’s compare them!<br>
<br>
Firstly, let’s implement the Fibonacci function using a recursive function.<br>
<br>
def fib_recursion(n):<br>
if n == 0:<br>
return 0<br>
elif n == 1:<br>
return 1<br>
else:<br>
return fib_recursion(n-1) + fib_recursion(n-2)<br>
<br>
We can verify the function by output the 20th number of the Fibonacci <br>
sequence.<br>
Image for post<br>
Image for post<br>
<br>
Then, let’s embed the closure version in a function for comparing purposes.<br>
<br>
def fib_closure(n):<br>
f = fib()<br>
for i in range(2, n+1):<br>
num = f()<br>
return num<br>
<br>
Image for post<br>
Image for post<br>
<br>
Now, let’s compare the speed.<br>
Image for post<br>
Image for post<br>
<br>
2.79ms v.s. 2.75µs. The closure method is 1000x faster than the <br>
recursive! The most intuitive reason is that all the temporary values <br>
for every level of recursion are stored in the memory separately, but <br>
the closure is actually updating the same variables in every loop.<br>
<br>
Also, there is a depth limitation for recursion. For the closure, <br>
because it is basically a for loop, there will not be any constraints.<br>
<br>
Here is an example of getting the 1000th Fibonacci number<br>
Image for post<br>
Image for post<br>
<br>
That’s indeed a huge number, but the closure method can finish the <br>
calculation in about 100 µs, while the recursive function met its <br>
limitation.<br>
Other Use Cases of Closure<br>
Image for post<br>
Image for post<br>
Photo by HarinathR on Pixabay<br>
<br>
Python closures are very useful not only for replacing the recursive <br>
functions. In some cases, it can also replace Python classes with a <br>
neater solution, especially there are not too many attributes and <br>
methods in a class.<br>
<br>
Suppose we have a dictionary of students with their exam marks.<br>
<br>
students = {<br>
'Alice': 98,<br>
'Bob': 67,<br>
'Chris': 85,<br>
'David': 75,<br>
'Ella': 54,<br>
'Fiona': 35,<br>
'Grace': 69<br>
}<br>
<br>
We want to have several functions that help us to filter the students by <br>
marks, to put them into different grade classes. However, the criteria <br>
might change over time. In this case, we can define a Python closure as <br>
follows:<br>
<br>
def make_student_classifier(lower_bound, upper_bound):<br>
def classify_student(exam_dict):<br>
return {k:v for (k,v) in exam_dict.items() if lower_bound <= v <br>
< upper_bound}<br>
return classify_student<br>
<br>
The closure defines a function that defines other functions based on the <br>
parameters passed in dynamically. We will pass the lower bound and upper <br>
bound of the grade class, and the closure will return us a function does <br>
that.<br>
<br>
grade_A = make_student_classifier(80, 100)<br>
grade_B = make_student_classifier(70, 80)<br>
grade_C = make_student_classifier(50, 70)<br>
grade_D = make_student_classifier(0, 50)<br>
<br>
The above code will give us 4 functions that will classify the student <br>
to the corresponding grade classes based on the boundaries we gave. <br>
Please be noted that we can change the boundary any time to make another <br>
function or overwrite current grade functions.<br>
<br>
Let’s verify the functions now.<br>
Image for post<br>
Image for post<br>
<br>
Very neat! Just bear in mind that we still need to define classes when <br>
the case is more complex.<br>
Summary<br>
Image for post<br>
Image for post<br>
Photo by Free-Photos on Pixabay<br>
<br>
In this article, I have introduced a technique called closure in Python. <br>
It can be utilised to rewrite recursive functions in most of the <br>
circumstances and outperform the latter to a huge extent.<br>
<br>
Indeed, closure might not be the best solution for some problems from <br>
the performance perspective, especially when Dynamic Planning is <br>
applicable. However, it is much easier to come up with. Sometimes <br>
Dynamic Planning is a bit overkill when we are not very sensitive to the <br>
performance, but closure might be good enough.<br>
<br>
Closure can also be used to replace some use cases that we may want to <br>
define a class to satisfy. It is much neater and elegant in those cases.<br>
"""<br>
<br>
-- <br>
Jesús Cea Avión _/_/ _/_/_/ _/_/_/<br>
<a href="mailto:jcea@jcea.es" target="_blank">jcea@jcea.es</a> - <a href="https://www.jcea.es/" rel="noreferrer" target="_blank">https://www.jcea.es/</a> _/_/ _/_/ _/_/ _/_/ _/_/<br>
Twitter: @jcea _/_/ _/_/ _/_/_/_/_/<br>
jabber / <a href="mailto:xmpp%3Ajcea@jabber.org" target="_blank">xmpp:jcea@jabber.org</a> _/_/ _/_/ _/_/ _/_/ _/_/<br>
"Things are not so easy" _/_/ _/_/ _/_/ _/_/ _/_/ _/_/<br>
"My name is Dump, Core Dump" _/_/_/ _/_/_/ _/_/ _/_/<br>
"El amor es poner tu felicidad en la felicidad de otro" - Leibniz<br>
<br>
_______________________________________________<br>
Asociación Python España: <a href="http://www.es.python.org/" rel="noreferrer" target="_blank">http://www.es.python.org/</a><br>
general mailing list<br>
<a href="mailto:general@lists.es.python.org" target="_blank">general@lists.es.python.org</a><br>
<a href="https://lists.es.python.org/listinfo/general" rel="noreferrer" target="_blank">https://lists.es.python.org/listinfo/general</a><br>
</blockquote></div><br clear="all"><br>-- <br><div dir="ltr" class="gmail_signature"><div dir="ltr"><div>Hyperreals *R "Quarks, bits y otras criaturas infinitesimales": <a href="https://blog.ch3m4.org" target="_blank">https://blog.ch3m4.org</a><br>Buscador Python Hispano: <a href="https://blog.ch3m4.org/pages/busqueda-python-es/" target="_blank">http://busca.ch3m4.org</a></div></div></div>