Danh sách lồng nhau đệ quy Python
\( \newcommand{\NOT}{\neg} \newcommand{\AND}{\wedge} \newcommand{\OR}{\vee} \newcommand{\XOR}{\oplus} \newcommand{\IMP}{\ . #1 \đúng. } \newcommand{\xspace}{} \newcommand{\proofheader}[1]{\underline{\textbf{#1}}} \) Show Trong hai phần trước, chúng ta đã học định nghĩa đệ quy chính thức của danh sách lồng nhau và sử dụng định nghĩa này để thiết kế và triển khai các hàm đệ quy hoạt động trên danh sách lồng nhau Trong phần này, chúng ta sẽ xem lại kiểu dữ liệu danh sách (không lồng nhau) quen thuộc, hiện đang áp dụng lăng kính đệ quy. Đây sẽ là bước đột phá đầu tiên của chúng ta trong việc xác định các kiểu dữ liệu đệ quy trong Python và sẽ xem trước các kiểu dữ liệu đệ quy phức tạp hơn mà chúng ta sẽ nghiên cứu trong chương tiếp theo Một định nghĩa đệ quy của danh sáchTất cả các cách trở lại trong Phần 1. 1, chúng tôi đã định nghĩa một danh sách là một tập hợp có thứ tự gồm 0 hoặc nhiều giá trị (có thể trùng lặp). Cho đến nay, chúng ta đã nghiên cứu hai cách để triển khai danh sách trong Python. triển khai dựa trên mảng của lớp Python 9 và triển khai danh sách liên kết dựa trên nút từ Chương 11. Mặc dù hai triển khai này khá khác nhau, nhưng chúng có chung một điểm tương đồng cơ bản. để thực hiện tính toán trên các tập hợp này, chúng tôi sử dụng các vòng lặp để xử lý từng phần tử danh sách mộtTuy nhiên, có một cách khác để xác định và thao tác trên danh sách, sử dụng tư duy đệ quy mà chúng ta đã phát triển trong chương này. Để bắt đầu, đây là một định nghĩa đệ quy của một danh sách
Nói cách khác, định nghĩa này phân tách một danh sách thành các phần "đầu tiên" và "phần còn lại" của nó và mang tính đệ quy vì phần "phần còn lại" là một danh sách khác. Đây là một ví dụ về cách bạn có thể hình dung biểu diễn này trong Python
Tuy nhiên, đây là một cách rườm rà để phân tách danh sách Python thông thường. Vì vậy, thay vào đó, chúng tôi sẽ định nghĩa một lớp Python đệ quy mới để biểu diễn định nghĩa đệ quy này. Đây là nỗ lực đầu tiên của chúng tôi
Chúng ta nói rằng kiểu dữ liệu 8 này là đệ quy, bởi vì thuộc tính thực thể 9 của nó đề cập đến một thực thể khác của 8. Tuy nhiên, có một vấn đề nhỏ với định nghĩa này. làm thế nào để chúng tôi đại diện cho danh sách trống? Để giải quyết vấn đề này, chúng tôi chỉ cần đặt cả hai thuộc tính này thành 11 để biểu thị một danh sách trống. Tuy nhiên, chúng tôi cần cẩn thận ghi lại hành vi này một cách cẩn thận trong một biểu diễn bất biến, để chúng tôi theo dõi chính xác thời điểm chúng tôi mong đợi một giá trị 11. Như chúng ta đã thấy với danh sách được liên kết, một lỗi lập trình phổ biến là sử dụng một biểu thức mà không nhận ra giá trị của nó có thể là 11. Đây là định nghĩa cập nhật của chúng tôi về lớp 8, với ____115 được sử dụng cho các thuộc tính và một trình khởi tạo cơ bản 1Và cuối cùng, đây là cách chúng ta có thể tạo một 8 đại diện cho chuỗi 17. So sánh biểu thức này với phân tách đệ quy trước đó của danh sách này 9Từ định nghĩa đệ quy đến các hàm đệ quyBây giờ, cho đến nay có vẻ như định nghĩa này khá rườm rà. Bây giờ chúng ta hãy xem một số tiền thưởng. giống như chúng ta đã làm với các danh sách lồng nhau, chúng ta có thể sử dụng định nghĩa danh sách đệ quy của mình để thiết kế và triển khai các hàm đệ quy hoạt động trên các danh sách đó Hãy xem một ví dụ quen thuộc. tính tổng của một danh sách các số nguyên. Chúng tôi sẽ xem xét từng phần trong định nghĩa của chúng tôi một cách riêng biệt
Điều này tự nhiên dẫn đến định nghĩa đệ quy sau cho tổng danh sách \[ sum(lst) = \begin{cases} 0, & \text{if $lst$ trống} \\ (\text{đầu tiên của $lst$}) + sum(\text{phần còn lại của $lst$} Và như chúng ta đã thấy một vài lần trong chương này, chúng ta có thể lấy định nghĩa này và dịch nó sang Python một cách tự nhiên, bây giờ là một phương thức của lớp 8 mới của chúng ta 1Bạn có thể thấy việc triển khai này vừa ngạc nhiên vừa không ngạc nhiên. Không có gì đáng ngạc nhiên, bởi vì nó là bản dịch tự nhiên của hàm toán học đệ quy, và vì vậy nếu bạn tin rằng hàm đó đúng, thì bạn cũng nên tin rằng hàm Python này cũng đúng. Nhưng ngạc nhiên vì hàm này tính tổng của một số phần tử tùy ý mà không cần sử dụng hàm tổng hợp hoặc vòng lặp có sẵn Để làm cho điểm cuối cùng này rõ ràng hơn, hãy so sánh phương thức này với hai hàm "tổng danh sách" trước đó trong khóa học này, trên danh sách Python và danh sách được liên kết 2Với định nghĩa đệ quy của chúng tôi về 19, có vẻ như có ít “công việc” được thực hiện hơn. Không có vòng lặp, hoặc truyền tải rõ ràng và truy cập các phần tử danh sách khác nhau. Bằng cách viết một hàm đệ quy, chúng ta để nó cho trình thông dịch Python xử lý đệ quy và theo dõi các lệnh gọi hàm cho chúng ta. Điều đó nói rằng, việc giảm tải công việc cho trình thông dịch Python này cũng có thể dẫn đến các vấn đề khác, chúng ta sẽ thảo luận sau trong khóa học. Mặc dù khái niệm đệ quy áp dụng cho tất cả các ngôn ngữ lập trình, nhưng cách các ngôn ngữ này xử lý đệ quy lại khác nhau khá nhiềuMột điều cuối cùng. các nút, được xem lạiBạn có thể đã nhận thấy điều gì đó rất quen thuộc về các thuộc tính của lớp 8 của chúng tôi. Kiểm tra nó ra 5Đúng rồi. Các lớp 8 và 92 về cơ bản có cấu trúc giống nhau. Vì vậy, trên thực tế, về mặt kỹ thuật, 92 cũng là một lớp đệ quy, mặc dù chúng tôi đã không giới thiệu chúng như vậy trong chương trước. Điều này có thể hơi ngạc nhiên, bởi vì mã mà chúng tôi đã viết cho danh sách được liên kết và 8 trông khá khác nhauVề cơ bản, chúng ta có thể xem các lớp 92 và 8 như hai cách nhìn của cùng một kiểu dữ liệu. Mã xác định các thuộc tính của chúng hầu như giống hệt nhau — đó là cách con người chúng ta diễn giải mã này khác nhauĐối với một 92, chúng tôi nghĩ về nó đại diện cho một phần tử danh sách duy nhất. Thuộc tính đệ quy của nó 98 là một “liên kết” đến một 92 khác và chúng tôi duyệt qua các liên kết này trong một vòng lặp để truy cập từng nút mộtMặt khác, đối với một 8, chúng tôi coi nó đại diện cho toàn bộ chuỗi các phần tử, không chỉ một phần tử. Thuộc tính đệ quy của nó 9 không phải là một liên kết, nó là phần còn lại của danh sách. Khi tính toán trên 8, chúng tôi không cố gắng truy cập từng mục riêng lẻ; Tính hai mặt giữa chế độ xem danh sách dựa trên nút và chế độ xem danh sách đệ quy là điều mà chúng ta sẽ thấy lại khi nghiên cứu một kiểu dữ liệu mới, cây, trong chương tiếp theo |