[Py-MAD] Don’t Use Recursion In Python Any More,Python Closure — A Pythonic technique you must know

[Jesus Cea]

El artículo requiere autenticarse para leerlo, así que voy a ser pirata 
y enviar una transcripción. La técnica me parece muy interesante. 
Podemos comentarla en la tertulia del martes próximo.

<https://towardsdatascience.com/dont-use-recursion-in-python-any-more-918aad95094c>

Transcripción si no quieres autenticarte. Las imágenes se pierden, pero 
espero que se entienda el sentido general:

"""
Don’t Use Recursion In Python Any More
Python Closure — A Pythonic technique you must know
Christopher Tao
Christopher Tao
Nov 22, 2020·8 min read

I was such a programmer who likes recursive functions very much before, 
simply because it is very cool and can be used to show off my 
programming skills and intelligence. However, in most of the 
circumstances, recursive functions have very high complexity that we 
should avoid using.

One of the much better solutions is to use Dynamic Planning when 
possible, which is probably the best way to solve a problem that can be 
divided into sub-problems. One of my previous articles has illustrated 
the power of Dynamic Planning.
Using Dynamic Planning to Help Trump Win the Elections
Dynamic Planning in Python for optimising Election Promotion
towardsdatascience.com

However, in this article, I’m going to introduce another technique in 
Python that can be utilised as an alternative to the recursive function. 
It won’t outperform Dynamic Planning, but much easier in term of 
thinking. In other words, we may sometimes be struggling to make Dynamic 
Planning works because of the abstraction of the ideas, but it will be 
much easier to use closure.
What is Python Closure?
Image for post
Image for post
Photo by Free-Photos on Pixabay

First of all, let me use a simple example to demonstrate what is a 
closure in Python. Look at the function below:

def outer():
     x = 1
     def inner():
         print(f'x in outer function: {x}')
     return inner

The function outer is defined with another function inner inside itself, 
and the function outer returns the function inner as the “return value” 
of the function.

In this case, the nested function is called a closure in Python. If we 
check the “return value” of the outer function, we will find that the 
returned value is a function.
Image for post
Image for post

What does closure do? Because it returned a function, we can run this 
function, of course.
Image for post
Image for post

OK, we can see that the inner function can access variables defined in 
the outer function. Usually, we don’t use closure in such a way shown as 
above, because it is kind of ugly. We usually want to define another 
function to hold the function returned by the closure.
Image for post
Image for post

Therefore, we can also say that in a Python closure, we defined a 
function that defines functions.
Access Outer Variables from the Inner Function
Image for post
Image for post
Photo by igorovsyannykov on Pixabay

How can we use a closure to replace a recursive then? Don’t be too 
hurry. Let’s have a look at another problem here, which is accessing 
outer variables from the inner function.

def outer():
     x = 1
     def inner():
         print(f'x in outer function (before modifying): {x}')
         x += 1
         print(f'x in outer function (after modifying): {x}')
     return inner

In the closure above-shown, we want to add 1 to the outer variable x in 
the inner function. However, this won’t work straightforward.
Image for post
Image for post

By default, you won’t be able to access the outer variable from the 
inner function. However, just like how we define a global variable in 
Python, we can tell the inner function of a closure that the variable 
should not be considered as a “local variable”, by using the nonlocal 
keyword.

def outer():
     x = 1
     def inner():
         nonlocal x
         print(f'x in outer function (before modifying): {x}')
         x += 1
         print(f'x in outer function (after modifying): {x}')
     return inner

Now, let’s say we want to add the variable x by 1 for five times. We can 
simply write a for loop to achieve this.

f = outer()for i in range(5):
     print(f'Run {i+1}')
     f()
     print('\n')

Image for post
Image for post
Write a Fibonacci Function Using Closure
Image for post
Image for post
Photo by Free-Photos on Pixabay

Fibonacci is commonly used as a “hello world” example of recursive 
functions. If you don’t remember it, don’t worry, it is pretty simple to 
be explained.

A Fibonacci sequence is a series of numbers that every number is the sum 
of the two numbers before it. The first two numbers, X₀ and X₁, are 
special. They are 0 and 1 respectively. Since X₂, the patter is as 
above-mentioned, it is the sum of X₀ and X₁, so X₂=1. Then, X₃ is X₁ + 
X₂ =2, X₄ is X₂ + X₃=3, X₅ is X₃ + X₄ = 5, and so on.

The recursive function requires us to think reversely from the “current 
scenario” to the “previous scenario”, and eventually what are the 
terminate conditions. However, by using the closure, we can think about 
the problem more naturally.

See the code below that the Fibonacci function is implemented using a 
closure.

def fib():
     x1 = 0
     x2 = 1
     def get_next_number():
         nonlocal x1, x2
         x3 = x1 + x2
         x1, x2 = x2, x3
         return x3
     return get_next_number

We know that the Fibonacci starts with two special number X₀=0 and X₁=1, 
so we just simply define them in the outer function. Then, the inner 
function get_next_number is simply return the sum of the two numbers it 
got from the outer function.

Additionally, don’t forget to update X₀ and X₁ with X₁ and X₂. In fact, 
we can simplify the code:

...
x3 = x1 + x2
x1, x2 = x2, x3
return x3

to

x0, x1 = x1, x0 + x1
return x1

This is updating the two variables first and then return the second, 
which is equivalent to the previous code snippet.

Then, we can use this closure to calculate Fibonacci numbers. For 
example, we want to show the Fibonacci sequence up to the 20th number.

fibonacci = fib()for i in range(2, 21):
     num = fibonacci()
     print(f'The {i}th Fibonacci number is {num}')

Image for post
Image for post
Compare the Performance
Image for post
Image for post
Photo by KahlOrr on Pixabay

Alright, we knew that we can use closure to replace a recursive function 
in the previous section. How about the performance? Let’s compare them!

Firstly, let’s implement the Fibonacci function using a recursive function.

def fib_recursion(n):
     if n == 0:
         return 0
     elif n == 1:
         return 1
     else:
         return fib_recursion(n-1) + fib_recursion(n-2)

We can verify the function by output the 20th number of the Fibonacci 
sequence.
Image for post
Image for post

Then, let’s embed the closure version in a function for comparing purposes.

def fib_closure(n):
     f = fib()
     for i in range(2, n+1):
         num = f()
     return num

Image for post
Image for post

Now, let’s compare the speed.
Image for post
Image for post

2.79ms v.s. 2.75µs. The closure method is 1000x faster than the 
recursive! The most intuitive reason is that all the temporary values 
for every level of recursion are stored in the memory separately, but 
the closure is actually updating the same variables in every loop.

Also, there is a depth limitation for recursion. For the closure, 
because it is basically a for loop, there will not be any constraints.

Here is an example of getting the 1000th Fibonacci number
Image for post
Image for post

That’s indeed a huge number, but the closure method can finish the 
calculation in about 100 µs, while the recursive function met its 
limitation.
Other Use Cases of Closure
Image for post
Image for post
Photo by HarinathR on Pixabay

Python closures are very useful not only for replacing the recursive 
functions. In some cases, it can also replace Python classes with a 
neater solution, especially there are not too many attributes and 
methods in a class.

Suppose we have a dictionary of students with their exam marks.

students = {
     'Alice': 98,
     'Bob': 67,
     'Chris': 85,
     'David': 75,
     'Ella': 54,
     'Fiona': 35,
     'Grace': 69
}

We want to have several functions that help us to filter the students by 
marks, to put them into different grade classes. However, the criteria 
might change over time. In this case, we can define a Python closure as 
follows:

def make_student_classifier(lower_bound, upper_bound):
     def classify_student(exam_dict):
         return {k:v for (k,v) in exam_dict.items() if lower_bound <= v 
< upper_bound}
     return classify_student

The closure defines a function that defines other functions based on the 
parameters passed in dynamically. We will pass the lower bound and upper 
bound of the grade class, and the closure will return us a function does 
that.

grade_A = make_student_classifier(80, 100)
grade_B = make_student_classifier(70, 80)
grade_C = make_student_classifier(50, 70)
grade_D = make_student_classifier(0, 50)

The above code will give us 4 functions that will classify the student 
to the corresponding grade classes based on the boundaries we gave. 
Please be noted that we can change the boundary any time to make another 
function or overwrite current grade functions.

Let’s verify the functions now.
Image for post
Image for post

Very neat! Just bear in mind that we still need to define classes when 
the case is more complex.
Summary
Image for post
Image for post
Photo by Free-Photos on Pixabay

In this article, I have introduced a technique called closure in Python. 
It can be utilised to rewrite recursive functions in most of the 
circumstances and outperform the latter to a huge extent.

Indeed, closure might not be the best solution for some problems from 
the performance perspective, especially when Dynamic Planning is 
applicable. However, it is much easier to come up with. Sometimes 
Dynamic Planning is a bit overkill when we are not very sensitive to the 
performance, but closure might be good enough.

Closure can also be used to replace some use cases that we may want to 
define a class to satisfy. It is much neater and elegant in those cases.
"""

-- 
Jesús Cea Avión                         _/_/      _/_/_/        _/_/_/
jcea at jcea.es - https://www.jcea.es/    _/_/    _/_/  _/_/    _/_/  _/_/
Twitter: @jcea                        _/_/    _/_/          _/_/_/_/_/
jabber / xmpp:jcea at jabber.org  _/_/  _/_/    _/_/          _/_/  _/_/
"Things are not so easy"      _/_/  _/_/    _/_/  _/_/    _/_/  _/_/
"My name is Dump, Core Dump"   _/_/_/        _/_/_/      _/_/  _/_/
"El amor es poner tu felicidad en la felicidad de otro" - Leibniz

-------------- next part --------------
A non-text attachment was scrubbed...
Name: OpenPGP_signature
Type: application/pgp-signature
Size: 495 bytes
Desc: OpenPGP digital signature
URL: <https://lists.es.python.org/pipermail/madrid/attachments/20210102/a00ac3bf/attachment.bin>