Advanced Function Applications - Decorators and Recursion
In the previous chapter, we explored higher-order functions in Python. I believe everyone has a deeper understanding of function definition and application. In this chapter, we continue to explain function-related knowledge: one is Python’s distinctive syntax feature - decorators, and the other is recursive function calls.
Decorators
In Python, a decorator is a syntactic phenomenon that “uses one function to decorate another function and provide it with additional capabilities”. A decorator itself is a function whose parameter is the decorated function, and its return value is a function with decorative functionality. From the description above, I believe everyone has heard that a decorator is a higher-order function whose parameters and return values are both functions. However, the concept of decorators is still a headache for programming language beginners. Let’s first illustrate the role of decorators through a simple example. Suppose there are two functions named download and upload for file uploading and downloading, as shown below.
import random
import time
def download(filename):
"""Download file"""
print(f'Starting download {filename}.')
time.sleep(random.random() * 6)
print(f'{filename} download complete.')
def upload(filename):
"""Upload file"""
print(f'Starting upload {filename}.')
time.sleep(random.random() * 8)
print(f'{filename} upload complete.')
download('MySQL from Deletion to Running Away.avi')
upload('Python from Beginner to Hospital.pdf')Note: The code above simulates the time it takes to download and upload files by sleeping for a random period of time, and doesn’t actually upload or download files over the network. Implementing network file upload and download in Python is also very simple, and we’ll cover related knowledge later.
Now there’s a new requirement: we want to know how much time it actually takes to call the download and upload functions to upload and download files. How should we implement this? I believe many people have already thought of it - we can record a time when the function starts executing, record another time when the function call ends, and subtracting the two times gives us the download or upload time, as shown in the following code.
start = time.time()
download('MySQL from Deletion to Running Away.avi')
end = time.time()
print(f'Time spent: {end - start:.2f} seconds')
start = time.time()
upload('Python from Beginner to Hospital.pdf')
end = time.time()
print(f'Time spent: {end - start:.2f} seconds')Through the code above, we can record the time spent downloading and uploading files, but I wonder if everyone has noticed that the code for recording time, calculating, and displaying execution time is all duplicate code. People with programming experience know that duplicate code is the root of all evil. So is there a way to record function execution time in a simple and elegant way without writing duplicate code? In Python, decorators are the best choice for solving such problems. Through decorator syntax, we can encapsulate timing functionality code that has nothing to do with the original business (uploading and downloading) into a function. If the upload and download functions need to record time, we can simply apply the decorator to these two functions. Since we mentioned above that a decorator is a higher-order function whose parameters and return values are both functions, let’s tentatively name the decorator for recording time record_time. Its overall structure should be as shown in the following code.
def record_time(func):
def wrapper(*args, **kwargs):
result = func(*args, **kwargs)
return result
return wrapperI believe everyone has noticed that the parameter func of the record_time function represents a decorated function, and the wrapper function defined inside the function is a function with decorative functionality. It will execute the decorated function func and needs to return the return value produced by the function execution at the end. I wonder if everyone has noticed that I left two blank lines at lines 4 and 6 in the code above, which means we can add code in these places to implement additional functionality. The record_time function will ultimately return this wrapper function with decorative functionality and use it to replace the original function func. When the original function func is decorated by the record_time function, calling it actually calls the wrapper function, so it gains additional capabilities. The parameters of the wrapper function are special. Since we want to use wrapper to replace the original function func, but we don’t know what parameters the original function func will accept, we accept everything through variable arguments and keyword arguments, and then pass everything unchanged to func when calling it. It should also be emphasized here that Python supports nested function definitions. As shown above, we can define the wrapper function inside the record_time function, which is not supported in many programming languages.
After understanding this structure, we can write the time recording functionality into this decorator, as shown in the following code.
import time
def record_time(func):
def wrapper(*args, **kwargs):
# Record start time before executing decorated function
start = time.time()
# Execute decorated function and get return value
result = func(*args, **kwargs)
# Record end time after executing decorated function
end = time.time()
# Calculate and display execution time of decorated function
print(f'{func.__name__} execution time: {end - start:.2f} seconds')
# Return the return value of decorated function
return result
return wrapperAlthough writing decorators is quite laborious, it’s a once-and-for-all operation. In the future, when there’s a need to record function execution time, we only need to add the decorator above. There are two ways to use the decorator function above. The first way is to directly call the decorator function, pass in the decorated function and get the return value. We can use this return value to directly replace the original function, so that when calling, we already have the additional capability provided by the decorator (recording execution time). Try the following code and you’ll understand.
download = record_time(download)
upload = record_time(upload)
download('MySQL from Deletion to Running Away.avi')
upload('Python from Beginner to Hospital.pdf')In Python, there’s a more convenient syntactic sugar for using decorators (syntax added to programming languages that doesn’t affect language functionality but makes it more convenient to use and improves code readability - we call it “syntactic sugar” or “sugar syntax”). You can use @decorator_function to place the decorator function directly above the decorated function, with the same effect as the code above. Let’s list the complete code for everyone to see how we define and use decorators.
import random
import time
def record_time(func):
def wrapper(*args, **kwargs):
start = time.time()
result = func(*args, **kwargs)
end = time.time()
print(f'{func.__name__} execution time: {end - start:.2f} seconds')
return result
return wrapper
@record_time
def download(filename):
print(f'Starting download {filename}.')
time.sleep(random.random() * 6)
print(f'{filename} download complete.')
@record_time
def upload(filename):
print(f'Starting upload {filename}.')
time.sleep(random.random() * 8)
print(f'{filename} upload complete.')
download('MySQL from Deletion to Running Away.avi')
upload('Python from Beginner to Hospital.pdf')In the code above, we added decorators to the download and upload functions through decorator syntactic sugar. The decorated download and upload functions are actually the wrapper function we return in the decorator. Calling them is actually calling the wrapper function, so they have the functionality of recording function execution time.
If in some places in the code we want to remove the decorator’s effect and execute the original function, we need to do a little extra work when defining the decorator function. The wraps function from Python’s standard library functools module is also a decorator. We place it on the wrapper function, and this decorator can help us preserve the function before decoration. This way, when we need to cancel the decorator, we can get the function before decoration through the __wrapped__ attribute of the decorated function.
import random
import time
from functools import wraps
def record_time(func):
@wraps(func)
def wrapper(*args, **kwargs):
start = time.time()
result = func(*args, **kwargs)
end = time.time()
print(f'{func.__name__} execution time: {end - start:.2f} seconds')
return result
return wrapper
@record_time
def download(filename):
print(f'Starting download {filename}.')
time.sleep(random.random() * 6)
print(f'{filename} download complete.')
@record_time
def upload(filename):
print(f'Starting upload {filename}.')
time.sleep(random.random() * 8)
print(f'{filename} upload complete.')
# Calling decorated function records execution time
download('MySQL from Deletion to Running Away.avi')
upload('Python from Beginner to Hospital.pdf')
# Cancel decorator effect without recording execution time
download.__wrapped__('MySQL Must Know and Know.pdf')
upload.__wrapped__('Python from Novice to Master.pdf')Decorator functions themselves can also be parameterized. Simply put, decorators can also be customized through parameters passed by the caller. We’ll explain this knowledge point when we use it later.
Recursive Calls
Python allows nested function definitions and mutual function calls, and a function can also directly or indirectly call itself. A function calling itself is called a recursive call. So what’s the use of recursive calls? In reality, many problems are defined recursively. For example, the factorial we talked about before - the factorial of a non-negative integer N is N multiplied by the factorial of N-1, i.e., $\small{N! = N \times (N-1)!}$. The concept of factorial appears on both the left and right sides of the definition, so this is a recursive definition. Since this is the case, we can write a factorial function using recursive calls, as shown in the following code.
def fac(num):
if num in (0, 1):
return 1
return num * fac(num - 1)In the code above, the fac function calls the fac function again, which is the so-called recursive call. The if condition on line 2 is called the convergence condition of recursion. Simply put, it’s when to end the recursive call of the function. When calculating factorials, if we calculate the factorial of 0 or 1, we stop the recursive call and directly return 1; num * fac(num - 1) on line 4 is the recursive formula, which is the recursive definition of factorial. Below, let’s briefly analyze what the whole process would be like if we use fac(5) to calculate the factorial of 5.
# Recursive calls push functions onto stack
# 5 * fac(4)
# 5 * (4 * fac(3))
# 5 * (4 * (3 * fac(2)))
# 5 * (4 * (3 * (2 * fac(1))))
# Stop recursion and pop functions from stack
# 5 * (4 * (3 * (2 * 1)))
# 5 * (4 * (3 * 2))
# 5 * (4 * 6)
# 5 * 24
# 120
print(fac(5)) # 120Note that function calls use a data structure in memory called a “stack” to save the current code execution context, and after the function call ends, this stack structure is used to restore the previous execution context. A stack is a first-in-last-out data structure, which means the earliest function pushed onto the stack returns last, while the last function pushed onto the stack returns first. For example, calling a function named a, function a’s execution body calls function b, and function b’s execution body calls function c, then the first function pushed onto the stack is a, and the first function popped from the stack is c. Each time we enter a function call, the stack adds a stack frame, which is the structure we just mentioned for saving the current code execution context; whenever a function call ends, the stack reduces a stack frame. Usually, stack space in memory is small, so if there are too many recursive calls, it will cause stack overflow. Therefore, recursive calls must ensure quick convergence. We can try executing fac(5000) to see if it prompts a RecursionError error with the message: maximum recursion depth exceeded in comparison (maximum recursion depth exceeded), which is actually a stack overflow.
If we use the official Python interpreter (CPython), the maximum depth of the function call stack structure is set to 1000 layers by default. If this depth is exceeded, the RecursionError mentioned above will occur. Of course, we can use the setrecursionlimit function from the sys module to change the maximum depth of recursive calls, but we don’t recommend doing this, because making recursion converge quickly is what we should do. Otherwise, we should consider using loop iteration instead of recursion.
Let’s give another example of generating Fibonacci sequences that we talked about before. Because the first two numbers of the Fibonacci sequence are both 1, and starting from the third number, each number is the sum of the previous two numbers, it can be written as f(n) = f(n - 1) + f(n - 2). Obviously, this is again a recursive definition, so we can use the following recursive call function to calculate the nth Fibonacci number.
def fib1(n):
if n in (1, 2):
return 1
return fib1(n - 1) + fib1(n - 2)
for i in range(1, 21):
print(fib1(i))It should be reminded that although the code for calculating Fibonacci numbers above looks very simple and clear, the execution performance is quite poor. You can try changing the second parameter of the range function in the for loop above to 51, i.e., output the first 50 Fibonacci numbers, and see how long it takes. You’re also welcome to leave your code execution time in the comments section. As for why it’s so slow, you can think about the reason yourself. Obviously, directly using loop iteration to get Fibonacci sequences is a better choice, as shown in the following code.
def fib2(n):
a, b = 0, 1
for _ in range(n):
a, b = b, a + b
return aIn addition, we can also use the lru_cache function from Python’s standard library functools module to optimize the recursive code above. The lru_cache function is a decorator function. We place it above the function fib1, and it can cache the function’s execution results to avoid generating a large amount of duplicate calculations during recursive calls, so the code execution performance will have “flying” improvements. You can try outputting the first 50 Fibonacci numbers and see how long the code takes to execute after adding the decorator. See you in the comments section!
from functools import lru_cache
@lru_cache()
def fib1(n):
if n in (1, 2):
return 1
return fib1(n - 1) + fib1(n - 2)
for i in range(1, 51):
print(i, fib1(i))Tip: The
lru_cachefunction is a decorator with parameters, so when using decorator syntactic sugar on line 4 above,lru_cachemust be followed by parentheses. Thelru_cachefunction has a very important parameter calledmaxsize, which can be used to define the size of the cache space, with a default value of 128.
Summary
Decorators are a distinctive syntax feature of Python. Decorators can enhance existing functions, which is a very useful programming technique. On the other hand, through recursive function calls, some complex problems can be simplified at the code level, but recursive calls must pay attention to convergence conditions and recursive formulas. Finding the recursive formula gives you the opportunity to use recursive calls, and the convergence condition ensures that recursive calls can stop. Function calls use stack space in memory to save and restore contexts. Stack space is usually very small, so if recursion cannot converge quickly, it’s very likely to cause stack overflow errors, leading to program crashes.