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}}} \)

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ách

Tấ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

from __future__ import annotations
from typing import Any


class RecursiveList:
    """A recursive implementation of the List ADT.
    """
    # Private Instance Attributes:
    #   - _first: The first item in the list.
    #   - _rest: A list containing the items that come after the first one.
    _first: Any
    _rest: RecursiveList
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ột

Tuy 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

  • Danh sách rỗng

    from __future__ import annotations
    from typing import Any
    
    
    class RecursiveList:
        """A recursive implementation of the List ADT.
        """
        # Private Instance Attributes:
        #   - _first: The first item in the list.
        #   - _rest: A list containing the items that come after the first one.
        _first: Any
        _rest: RecursiveList
    0 là một danh sách

  • Nếu

    from __future__ import annotations
    from typing import Any
    
    
    class RecursiveList:
        """A recursive implementation of the List ADT.
        """
        # Private Instance Attributes:
        #   - _first: The first item in the list.
        #   - _rest: A list containing the items that come after the first one.
        _first: Any
        _rest: RecursiveList
    1 là một giá trị và
    from __future__ import annotations
    from typing import Any
    
    
    class RecursiveList:
        """A recursive implementation of the List ADT.
        """
        # Private Instance Attributes:
        #   - _first: The first item in the list.
        #   - _rest: A list containing the items that come after the first one.
        _first: Any
        _rest: RecursiveList
    0 là một danh sách, thì chúng ta có thể tạo một danh sách mới
    from __future__ import annotations
    from typing import Any
    
    
    class RecursiveList:
        """A recursive implementation of the List ADT.
        """
        # Private Instance Attributes:
        #   - _first: The first item in the list.
        #   - _rest: A list containing the items that come after the first one.
        _first: Any
        _rest: RecursiveList
    1 có phần tử đầu tiên là
    from __future__ import annotations
    from typing import Any
    
    
    class RecursiveList:
        """A recursive implementation of the List ADT.
        """
        # Private Instance Attributes:
        #   - _first: The first item in the list.
        #   - _rest: A list containing the items that come after the first one.
        _first: Any
        _rest: RecursiveList
    1 và các phần tử khác của nó là các phần tử của
    from __future__ import annotations
    from typing import Any
    
    
    class RecursiveList:
        """A recursive implementation of the List ADT.
        """
        # Private Instance Attributes:
        #   - _first: The first item in the list.
        #   - _rest: A list containing the items that come after the first one.
        _first: Any
        _rest: RecursiveList
    0

    Trong trường hợp này, chúng tôi gọi

    from __future__ import annotations
    from typing import Any
    
    
    class RecursiveList:
        """A recursive implementation of the List ADT.
        """
        # Private Instance Attributes:
        #   - _first: The first item in the list.
        #   - _rest: A list containing the items that come after the first one.
        _first: Any
        _rest: RecursiveList
    1 là phần tử đầu tiên của
    from __future__ import annotations
    from typing import Any
    
    
    class RecursiveList:
        """A recursive implementation of the List ADT.
        """
        # Private Instance Attributes:
        #   - _first: The first item in the list.
        #   - _rest: A list containing the items that come after the first one.
        _first: Any
        _rest: RecursiveList
    1 và
    from __future__ import annotations
    from typing import Any
    
    
    class RecursiveList:
        """A recursive implementation of the List ADT.
        """
        # Private Instance Attributes:
        #   - _first: The first item in the list.
        #   - _rest: A list containing the items that come after the first one.
        _first: Any
        _rest: RecursiveList
    0 là phần còn lại của
    from __future__ import annotations
    from typing import Any
    
    
    class RecursiveList:
        """A recursive implementation of the List ADT.
        """
        # Private Instance Attributes:
        #   - _first: The first item in the list.
        #   - _rest: A list containing the items that come after the first one.
        _first: Any
        _rest: RecursiveList
    1

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

[1, 2, 3, 4] ==
([1] +
    ([2] +
        ([3] +
            ([4] + [])))

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

from __future__ import annotations
from typing import Any


class RecursiveList:
    """A recursive implementation of the List ADT.
    """
    # Private Instance Attributes:
    #   - _first: The first item in the list.
    #   - _rest: A list containing the items that come after the first one.
    _first: Any
    _rest: RecursiveList

Chúng ta nói rằng kiểu dữ liệu

from __future__ import annotations
from typing import Any


class RecursiveList:
    """A recursive implementation of the List ADT.
    """
    # Private Instance Attributes:
    #   - _first: The first item in the list.
    #   - _rest: A list containing the items that come after the first one.
    _first: Any
    _rest: RecursiveList
8 này là đệ quy, bởi vì thuộc tính thực thể
from __future__ import annotations
from typing import Any


class RecursiveList:
    """A recursive implementation of the List ADT.
    """
    # Private Instance Attributes:
    #   - _first: The first item in the list.
    #   - _rest: A list containing the items that come after the first one.
    _first: Any
    _rest: RecursiveList
9 của nó đề cập đến một thực thể khác của
from __future__ import annotations
from typing import Any


class RecursiveList:
    """A recursive implementation of the List ADT.
    """
    # Private Instance Attributes:
    #   - _first: The first item in the list.
    #   - _rest: A list containing the items that come after the first one.
    _first: Any
    _rest: RecursiveList
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

from __future__ import annotations
from typing import Any


class RecursiveList:
    """A recursive implementation of the List ADT.
    """
    # Private Instance Attributes:
    #   - _first: The first item in the list.
    #   - _rest: A list containing the items that come after the first one.
    _first: Any
    _rest: RecursiveList
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ị
from __future__ import annotations
from typing import Any


class RecursiveList:
    """A recursive implementation of the List ADT.
    """
    # Private Instance Attributes:
    #   - _first: The first item in the list.
    #   - _rest: A list containing the items that come after the first one.
    _first: Any
    _rest: RecursiveList
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à
from __future__ import annotations
from typing import Any


class RecursiveList:
    """A recursive implementation of the List ADT.
    """
    # Private Instance Attributes:
    #   - _first: The first item in the list.
    #   - _rest: A list containing the items that come after the first one.
    _first: Any
    _rest: RecursiveList
11. Đây là định nghĩa cập nhật của chúng tôi về lớp
from __future__ import annotations
from typing import Any


class RecursiveList:
    """A recursive implementation of the List ADT.
    """
    # Private Instance Attributes:
    #   - _first: The first item in the list.
    #   - _rest: A list containing the items that come after the first one.
    _first: Any
    _rest: RecursiveList
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

from __future__ import annotations
from typing import Any


class RecursiveList:
    """A recursive implementation of the List ADT.
    """
    # Private Instance Attributes:
    #   - _first: The first item in the list.
    #   - _rest: A list containing the items that come after the first one.
    _first: Any
    _rest: RecursiveList
1

Và cuối cùng, đây là cách chúng ta có thể tạo một

from __future__ import annotations
from typing import Any


class RecursiveList:
    """A recursive implementation of the List ADT.
    """
    # Private Instance Attributes:
    #   - _first: The first item in the list.
    #   - _rest: A list containing the items that come after the first one.
    _first: Any
    _rest: RecursiveList
8 đại diện cho chuỗi
from __future__ import annotations
from typing import Any


class RecursiveList:
    """A recursive implementation of the List ADT.
    """
    # Private Instance Attributes:
    #   - _first: The first item in the list.
    #   - _rest: A list containing the items that come after the first one.
    _first: Any
    _rest: RecursiveList
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

from __future__ import annotations
from typing import Any


class RecursiveList:
    """A recursive implementation of the List ADT.
    """
    # Private Instance Attributes:
    #   - _first: The first item in the list.
    #   - _rest: A list containing the items that come after the first one.
    _first: Any
    _rest: RecursiveList
9

Từ định nghĩa đệ quy đến các hàm đệ quy

Bâ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

  • Đặt \(lst\) là một danh sách rỗng. Trong trường hợp này, tổng của nó là 0

  • Đặt \(lst\) là một danh sách các số nguyên khác rỗng. Trong trường hợp này, chúng ta có thể phân tách nó thành phần tử đầu tiên, \(x\), và các phần tử còn lại, \(r\). Tổng của \(lst\) bằng \(x\) cộng với tổng của các phần tử còn lại

    Ví dụ: nếu \(lst = [1, 2, 3, 4]\), thì \(sum(lst) = 1 + sum([2, 3, 4])\)

Đ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

from __future__ import annotations
from typing import Any


class RecursiveList:
    """A recursive implementation of the List ADT.
    """
    # Private Instance Attributes:
    #   - _first: The first item in the list.
    #   - _rest: A list containing the items that come after the first one.
    _first: Any
    _rest: RecursiveList
8 mới của chúng ta

from __future__ import annotations
from typing import Any


class RecursiveList:
    """A recursive implementation of the List ADT.
    """
    # Private Instance Attributes:
    #   - _first: The first item in the list.
    #   - _rest: A list containing the items that come after the first one.
    _first: Any
    _rest: RecursiveList
1

Bạ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

from __future__ import annotations
from typing import Any


class RecursiveList:
    """A recursive implementation of the List ADT.
    """
    # Private Instance Attributes:
    #   - _first: The first item in the list.
    #   - _rest: A list containing the items that come after the first one.
    _first: Any
    _rest: RecursiveList
2

Với định nghĩa đệ quy của chúng tôi về

from __future__ import annotations
from typing import Any


class RecursiveList:
    """A recursive implementation of the List ADT.
    """
    # Private Instance Attributes:
    #   - _first: The first item in the list.
    #   - _rest: A list containing the items that come after the first one.
    _first: Any
    _rest: RecursiveList
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ều

Một điều cuối cùng. các nút, được xem lại

Bạ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

from __future__ import annotations
from typing import Any


class RecursiveList:
    """A recursive implementation of the List ADT.
    """
    # Private Instance Attributes:
    #   - _first: The first item in the list.
    #   - _rest: A list containing the items that come after the first one.
    _first: Any
    _rest: RecursiveList
8 của chúng tôi. Kiểm tra nó ra

from __future__ import annotations
from typing import Any


class RecursiveList:
    """A recursive implementation of the List ADT.
    """
    # Private Instance Attributes:
    #   - _first: The first item in the list.
    #   - _rest: A list containing the items that come after the first one.
    _first: Any
    _rest: RecursiveList
5

Đúng rồi. Các lớp

from __future__ import annotations
from typing import Any


class RecursiveList:
    """A recursive implementation of the List ADT.
    """
    # Private Instance Attributes:
    #   - _first: The first item in the list.
    #   - _rest: A list containing the items that come after the first one.
    _first: Any
    _rest: RecursiveList
8 và
from __future__ import annotations
from typing import Any


class RecursiveList:
    """A recursive implementation of the List ADT.
    """
    # Private Instance Attributes:
    #   - _first: The first item in the list.
    #   - _rest: A list containing the items that come after the first one.
    _first: Any
    _rest: RecursiveList
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,
from __future__ import annotations
from typing import Any


class RecursiveList:
    """A recursive implementation of the List ADT.
    """
    # Private Instance Attributes:
    #   - _first: The first item in the list.
    #   - _rest: A list containing the items that come after the first one.
    _first: Any
    _rest: RecursiveList
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à
from __future__ import annotations
from typing import Any


class RecursiveList:
    """A recursive implementation of the List ADT.
    """
    # Private Instance Attributes:
    #   - _first: The first item in the list.
    #   - _rest: A list containing the items that come after the first one.
    _first: Any
    _rest: RecursiveList
8 trông khá khác nhau

Về cơ bản, chúng ta có thể xem các lớp

from __future__ import annotations
from typing import Any


class RecursiveList:
    """A recursive implementation of the List ADT.
    """
    # Private Instance Attributes:
    #   - _first: The first item in the list.
    #   - _rest: A list containing the items that come after the first one.
    _first: Any
    _rest: RecursiveList
92 và
from __future__ import annotations
from typing import Any


class RecursiveList:
    """A recursive implementation of the List ADT.
    """
    # Private Instance Attributes:
    #   - _first: The first item in the list.
    #   - _rest: A list containing the items that come after the first one.
    _first: Any
    _rest: RecursiveList
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

from __future__ import annotations
from typing import Any


class RecursiveList:
    """A recursive implementation of the List ADT.
    """
    # Private Instance Attributes:
    #   - _first: The first item in the list.
    #   - _rest: A list containing the items that come after the first one.
    _first: Any
    _rest: RecursiveList
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ó
from __future__ import annotations
from typing import Any


class RecursiveList:
    """A recursive implementation of the List ADT.
    """
    # Private Instance Attributes:
    #   - _first: The first item in the list.
    #   - _rest: A list containing the items that come after the first one.
    _first: Any
    _rest: RecursiveList
98 là một “liên kết” đến một
from __future__ import annotations
from typing import Any


class RecursiveList:
    """A recursive implementation of the List ADT.
    """
    # Private Instance Attributes:
    #   - _first: The first item in the list.
    #   - _rest: A list containing the items that come after the first one.
    _first: Any
    _rest: RecursiveList
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ột

Mặt khác, đối với một

from __future__ import annotations
from typing import Any


class RecursiveList:
    """A recursive implementation of the List ADT.
    """
    # Private Instance Attributes:
    #   - _first: The first item in the list.
    #   - _rest: A list containing the items that come after the first one.
    _first: Any
    _rest: RecursiveList
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ó
from __future__ import annotations
from typing import Any


class RecursiveList:
    """A recursive implementation of the List ADT.
    """
    # Private Instance Attributes:
    #   - _first: The first item in the list.
    #   - _rest: A list containing the items that come after the first one.
    _first: Any
    _rest: RecursiveList
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
from __future__ import annotations
from typing import Any


class RecursiveList:
    """A recursive implementation of the List ADT.
    """
    # Private Instance Attributes:
    #   - _first: The first item in the list.
    #   - _rest: A list containing the items that come after the first one.
    _first: Any
    _rest: RecursiveList
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