Nói một cách dễ hiểu, đệ quy là một cách giải quyết vấn đề bằng cách tự gọi hàm, Từ “ đệ quy 'Bắt nguồn từ động từ Latinh' tái diễn ”, Có nghĩa là làm lại một cái gì đó. Đây là những gì hàm đệ quy làm, nó lặp đi lặp lại cùng một thứ, tức là nó tự nhớ lại chính nó. Trong bài này, chúng ta sẽ tìm hiểu về đệ quy trong python. Sau đây là các chủ đề được đề cập trong blog này:
- Đệ quy trong Python là gì?
- Điều kiện chấm dứt
- Giới hạn đệ quy của Python
- Làm phẳng danh sách với đệ quy
- Ưu điểm của đệ quy
- Nhược điểm của Đệ quy
Đệ quy trong Python là gì?
Đệ quy là quá trình xác định một cái gì đó về mặt chính nó. Chúng ta biết rằng trong Python, bất kỳ hàm nào cũng có thể gọi bất kỳ hàm nào khác, một hàm cũng có thể gọi chính nó. Những loại hàm tự gọi nó cho đến khi điều kiện nhất định không được đáp ứng được gọi là hàm đệ quy.
Hãy lấy một vài ví dụ để xem cách hoạt động của nó, Nếu bạn được cung cấp một số nguyên dương n thì giai thừa sẽ là.
cách sao chép sâu trong java
- n! = n * (n-1) * (n-2), v.v.
- 2! = 2 * (2-1)
- một! = 1
- 0! = 0
- 4! = 4 * 3!
- 3! = 3 * 2!
- 2! = 2 * 1!
Thay thế các giá trị trên sẽ dẫn đến biểu thức sau
- 4! = 4 * 3 * 2 * 1
Chúng ta phải định nghĩa một hàm cho phép nói fact (n) nhận số nguyên dương hoặc 0 làm tham số của nó và trả về giai thừa thứ n, làm thế nào chúng ta có thể thực hiện điều đó bằng cách sử dụng đệ quy?
Hãy xem, để làm như vậy bằng cách sử dụng đệ quy, chúng ta cần kiểm tra phương trình sau
n! = n. (n-1). (n-2) & hellip3.2.1
n! = n. (n-1)! # chúng ta có thể viết lại câu lệnh trên như trên dòng này
Bây giờ ở đây nếu chúng ta truyền 2 làm tham số, chúng ta sẽ nhận được:
2! = 2,1! = 2
Tương tự, nếu chúng ta vượt qua 1, chúng ta sẽ nhận được:
một! = 1,0! = 1
Nhưng nếu chúng ta vượt qua 0, nó sẽ phá vỡ
0! = 0. (- 1)! và ở đây giai thừa cho -1 không được xác định vì vậy điều này chỉ hoạt động với các giá trị> 0
Vì vậy, chúng ta phải viết hai trường hợp
1. n! = n. (n-1)! nếu n> = 1
2. 1 nếu n = 0
Đây là một giải pháp hoàn chỉnh cho tất cả các số nguyên dương và 0.
Điều kiện chấm dứt
Một hàm đệ quy phải đáp ứng một điều kiện quan trọng để kết thúc. Hướng tới một điều kiện mà vấn đề có thể được giải quyết mà không cần đệ quy thêm, một hàm đệ quy sẽ kết thúc, giảm thiểu vấn đề thành các bước con nhỏ hơn. Một đệ quy có thể kết thúc trong một vòng lặp vô hạn nếu điều kiện kết thúc không được đáp ứng trong các lệnh gọi.
Điều kiện giai thừa:
- giai thừa của n = n * (n-1) miễn là n lớn hơn 1.
- 1 nếu n = 0
Chúng tôi sẽ chuyển đổi các điều kiện giai thừa ở trên trong mã python:
def fact (n): if n == 1: return n else: trả về n * fact (n-1)
Hãy lấy một ví dụ, giả sử chúng ta muốn tìm giai thừa của 4:
fact (4) #this sẽ trả về 4 * fact (3) và cứ tiếp tục như vậy cho đến khi n == 1.
Đầu ra: 24
Nó thường được sử dụng làm ví dụ cho phép đệ quy vì tính đơn giản và rõ ràng của nó. Giải quyết các trường hợp nhỏ hơn của một vấn đề ở mỗi bước mà nó được gọi là đệ quy trong khoa học máy tính.
Giới hạn đệ quy của Python
Trong một số ngôn ngữ, bạn có thể tạo một vòng lặp đệ quy vô hạn, nhưng trong Python, có một giới hạn đệ quy. Để kiểm tra giới hạn, hãy chạy chức năng sau từ mô-đun sys. sẽ cung cấp giới hạn của tập đệ quy cho python.
nhập sys sys.getrecursionlimit ()
Đầu ra: 1000
Bạn cũng có thể thay đổi giới hạn bằng cách sử dụng functionsetrecursionlimit () của mô-đun sys theo yêu cầu của bạn, Bây giờ chúng ta hãy tạo một hàm tự gọi đệ quy cho đến khi nó vượt quá giới hạn và kiểm tra điều gì sẽ xảy ra:
def recursive (): recursive () if __name__ == '__main__': recursive ()
Nếu bạn chạy đoạn mã trên, bạn sẽ nhận được một ngoại lệ thời gian chạy: RuntimeError: đã vượt quá độ sâu đệ quy tối đa. Python ngăn bạn tạo một hàm kết thúc bằng một vòng lặp đệ quy không bao giờ kết thúc.
Làm phẳng danh sách với đệ quy
Những việc khác bạn có thể làm bằng cách sử dụng đệ quy ngoại trừ các giai thừa, giả sử bạn muốn tạo một danh sách từ một danh sách được lồng vào nhau, bạn có thể thực hiện điều đó bằng cách sử dụng mã bên dưới:
def flatten (a_list, flat_list = none): if flat_list is none: flat_list = [] cho item trong a_list: if isinstance (item, list): flatten (item, flat_list) else: flat_list.append (item) return flat_list if __name__ == '__main__': nested = [1,2,3, [4,5], 6] x = flatten (lồng nhau) print (x)
Đầu ra: [1,2,3,4,5,6]
Chạy đoạn mã trên sẽ dẫn đến một danh sách duy nhất thay vì danh sách số nguyên chứa danh sách số nguyên mà chúng tôi đã sử dụng làm đầu vào. Bạn cũng có thể làm điều tương tự bằng cách sử dụng các cách khác, Python có một thứ gọi là itertools.chain (), bạn có thể kiểm tra mã được sử dụng để tạo chuỗi hàm () đó là một cách tiếp cận khác để thực hiện điều tương tự như chúng ta đã làm.
Ưu điểm của đệ quy
Mã rõ ràng và thanh lịch trong một hàm đệ quy.
Một nhiệm vụ tổng hợ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 chuỗi 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, việc tuân theo logic đằng sau hàm đệ quy có thể khó.
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.
Trong bài viết này, chúng ta đã biết đệ quy là gì và cách chúng ta có thể phát triển các hàm đệ quy từ câu lệnh bài toán, cách toán học một câu lệnh bài toán có thể được định nghĩa. Chúng tôi đã giải quyết một vấn đề về giai thừa và tìm ra các điều kiện cần thiết để tìm giai thừa mà từ đó chúng tôi có thể chuyển đổi các điều kiện đó thành mã python, cung cấp cho bạn sự hiểu biết về cách hoạt động của đệ quy. Tôi nghĩ thật tuyệt là Python có giới hạn đệ quy được tích hợp sẵn để ngăn các nhà phát triển tạo các hàm đệ quy được xây dựng kém. Một điều quan trọng cần lưu ý là khó có thể gỡ lỗi đệ quy vì hàm liên tục gọi chính nó.