Trong hướng dẫn này, bạn sẽ học cách tạo một hàm đệ quy (một hàm gọi chính nó).
Đệ quy là gì?
Đệ quy là quá trình xác định một cái gì đó về mặt chính nó.
Một ví dụ về thế giới vật chất là đặt hai gương song song đối diện nhau. Bất kỳ đối tượng nào ở giữa chúng sẽ được phản ánh một cách đệ quy.
Hàm đệ quy Python
Trong Python, chúng ta biết rằng một hàm có thể gọi các hàm khác. Thậm chí có thể cho hàm tự gọi. Các loại cấu trúc này được gọi là các hàm đệ quy.
Hình ảnh sau đây cho thấy hoạt động của một hàm đệ quy được gọi recurse.
Hàm đệ quy trong Python
Sau đây là một ví dụ về một hàm đệ quy để tìm giai thừa của một số nguyên.
Giai thừa của một số là tích của tất cả các số nguyên từ 1 đến số đó. Ví dụ, giai thừa của 6 (được ký hiệu là 6!) Là 1 * 2 * 3 * 4 * 5 * 6 = 720.
Ví dụ về một hàm đệ quy
def factorial(x): """This is a recursive function to find the factorial of an integer""" if x == 1: return 1 else: return (x * factorial(x-1)) num = 3 print("The factorial of", num, "is", factorial(num))
Đầu ra
Giai thừa của 3 là 6
Trong ví dụ trên, factorial()là một hàm đệ quy vì nó gọi chính nó.
Khi chúng ta gọi hàm này với một số nguyên dương, nó sẽ gọi một cách đệ quy chính nó bằng cách giảm số lượng.
Mỗi hàm nhân số với giai thừa của số bên dưới nó cho đến khi nó bằng một. Cuộc gọi đệ quy này có thể được giải thích theo các bước sau.
giai thừa (3) # Lần gọi đầu tiên với 3 3 * giai thừa (2) # Lần gọi thứ 2 với 2 3 * 2 * giai thừa (1) # Lần gọi thứ 3 với 1 3 * 2 * 1 # trả về từ lần gọi thứ 3 là số = 1 3 * 2 # quay lại từ cuộc gọi thứ 2 6 # quay lại từ cuộc gọi đầu tiên
Hãy xem một hình ảnh cho thấy quy trình từng bước của những gì đang diễn ra:
Làm việc của một hàm giai thừa đệ quy
Đệ quy của chúng ta kết thúc khi số lượng giảm xuống 1. Đây được gọi là điều kiện cơ sở.
Mọi hàm đệ quy phải có một điều kiện cơ sở để dừng đệ quy hoặc nếu không hàm gọi chính nó vô hạn.
Trình thông dịch Python giới hạn độ sâu của đệ quy để giúp tránh đệ quy vô hạn, dẫn đến tràn ngăn xếp.
Theo mặc định, độ sâu tối đa của đệ quy là 1000. Nếu vượt qua giới hạn, kết quả là RecursionError. Hãy xem xét một điều kiện như vậy.
def recursor(): recursor() recursor()
Đầu ra
Traceback (lần gọi gần đây nhất): Tệp "", dòng 3, trong Tệp "", dòng 2, trong Tệp "", dòng 2, trong Tệp "", dòng 2, trong a (Dòng trước lặp lại 996 lần nữa ) RecursionError: đã vượt quá độ sâu đệ quy tối đa
Ưu điểm của Đệ quy
- Các hàm đệ quy làm cho mã trông sạch sẽ và thanh lịch.
- Một nhiệm vụ phức tạp có thể được chia thành các bài toán con đơn giản hơn bằng cách sử dụng đệ quy.
- Việc tạo trình tự với đệ quy dễ dàng hơn so với việc sử dụng một số phép lặp lồng nhau.
Nhược điểm của Đệ quy
- Đôi khi logic đằng sau đệ quy rất khó theo dõi.
- Cuộc gọi đệ quy rất tốn kém (không hiệu quả) vì chúng chiếm nhiều bộ nhớ và thời gian.
- Các hàm đệ quy rất khó gỡ lỗi.
