Đệ quy trong Python
Trong lập trình có một khái niệm gọi là đệ quy - khi một hàm gọi chính nó.
Ví dụ . Đệ quy đơn giản với bộ đếm
Hãy in ra các số từ 1 đến 10
bằng cách sử dụng đệ quy:
i = 1
def func():
global i
print(i)
i += 1
if i <= 10:
func() # tại đây hàm gọi chính nó
func()
Hãy cùng thảo luận về cách đoạn mã này hoạt động.
Chúng ta có biến toàn cục i
và hàm func, bên trong hàm này
nội dung của biến i được in ra
console, sau đó cộng thêm một đơn vị vào nó.
Nếu biến i của chúng ta nhỏ hơn hoặc
bằng 10, thì hàm sẽ được gọi lại.
Vì biến i là toàn cục, nên với mỗi lần gọi
hàm mới, nó sẽ có giá trị của biến i
được thiết lập từ lần gọi trước đó.
Kết quả là hàm sẽ tự gọi chính nó
cho đến khi i lớn hơn 10.
Lưu ý rằng, trong trường hợp của chúng ta, không thể khởi chạy hàm
mà không có if - nếu làm vậy,
sẽ xảy ra việc gọi hàm vô hạn.
Ví dụ . Đệ quy để in các phần tử của danh sách lồng nhau
Đệ quy thường được áp dụng nhất cho việc duyệt qua các danh sách có độ sâu lồng nhau khác nhau. Giả sử chúng ta có danh sách sau:
lst = [1, [2, 3], [[4, 5], [6, 7, 8, [9]]]]
Hãy tạo một hàm để duyệt qua nó.
Trong hàm, trước tiên cần đặt điều kiện,
để phần tử là kiểu dữ liệu nguyên thủy,
tức là số được lấy ra trực tiếp từ danh sách,
sẽ được in ra console.
Còn nếu phần tử là một đối tượng phức tạp,
ví dụ như danh sách lồng nhau, thì
trong trường hợp này, hàm hãy tự gọi chính nó,
tức là xảy ra đệ quy. Để kiểm tra
kiểu của phần tử, hãy sử dụng hàm isinstance.
Chỉ cho ví dụ của chúng ta, trong tham số đầu tiên của
isinstance chúng ta sẽ viết el, còn
tham số thứ hai là kiểu list:
def func(lst):
for el in lst:
if isinstance(el, list):
func(el)
else:
print(el)
Khi gọi hàm, một loạt các số từ danh sách lồng nhau sẽ được in ra:
func(lst) # sẽ in ra 1, 2, ... 8, 9
Ví dụ . Đệ quy cho các phép toán với phần tử danh sách lồng nhau
Đệ quy cũng có thể được áp dụng cho các phép toán khác nhau với các phần tử của danh sách lồng nhau. Giả sử chúng ta có danh sách sau:
lst = [1, [2, 3], [[4, 5], [6, 7, 8, [9]]]]
Hãy tính tổng của tất cả các phần tử của nó.
Để làm điều này, trong hàm, hãy khai báo một biến res,
mà tổng các số sẽ được tích lũy vào đó.
Trong điều kiện, chúng ta sẽ viết rằng nếu phần tử
là một đối tượng phức tạp, thì nó sẽ được truyền vào
tham số của hàm func và cộng dồn
vào tổng. Điều này có nghĩa là phần tử sẽ
nằm trong đệ quy cho đến khi nó trở thành
kiểu nguyên thủy. Và trong trường hợp đó, nó sẽ đơn giản
được cộng vào tổng đã ghi trong res:
def func(lst):
res = 0
for el in lst:
if isinstance(el, list):
res += func(el)
else:
res += el
return res
Hãy gọi hàm và in kết quả của nó ra console:
print(func(lst)) # sẽ in ra 45
Ví dụ . Đệ quy để tích lũy vào một danh sách
Với sự trợ giúp của đệ quy, bạn có thể chuyển đổi các danh sách lồng nhau thành một danh sách một chiều duy nhất. Giả sử chúng ta có danh sách sau:
lst = [1, [2, 3], [[4, 5], [6, 7, 8, [9]]]]
Hãy viết trong hàm một danh sách trống
res, mà các phần tử của danh sách ban đầu
sẽ được tích lũy vào đó. Sau đó, khởi chạy
vòng lặp và đặt điều kiện - nếu phần tử
là một danh sách, thì nó sẽ được đưa vào phương thức
extend. Phương thức này nối
các phần tử của một danh sách vào cuối danh sách thứ hai,
tức là các phần tử của danh sách lồng nhau
sẽ được đưa vào cuối danh sách res:
def func(lst):
res = []
for el in lst:
if isinstance(el, list):
res.extend(func(el))
else:
res.append(el)
return res
print(func(lst))
Kết quả của mã được thực hiện:
[1, 2, 3, 4, 5, 6, 7, 8, 9]
Bài tập thực hành
Hãy in ra tất cả các phần tử số của từ điển với độ sâu lồng nhau bất kỳ:
{
'a': {
'b': 1,
'c': 2,
'd': {
'e': 3,
'f': 4
}
},
'j': {
'h': 5,
'k': 6,
},
'l': 7
}
Tìm tổng các phần tử của từ điển từ bài tập trước đó.
Nhận một danh sách các phần tử nguyên thủy của từ điển từ bài tập trước đó.
