Liệt kê trong Python đệ quy

Đệ quy có nghĩa là “xác định một thứ gì đó theo chính nó” thường ở quy mô nhỏ hơn, có thể nhiều lần, để đạt được mục tiêu của bạn. Ví dụ: chúng ta có thể nói “Con người là người có mẹ là con người”, hoặc “thư mục là cấu trúc chứa các tệp và thư mục [nhỏ hơn]”, hoặc “cây phả hệ bắt đầu bằng một cặp vợ chồng có con,

Các ngôn ngữ lập trình thường hỗ trợ đệ quy, điều đó có nghĩa là để giải quyết một vấn đề, các hàm có thể gọi chính chúng để giải các bài toán con nhỏ hơn

Bất kỳ vấn đề nào có thể được giải theo cách lặp [với vòng lặp for hoặc while] cũng có thể được giải theo cách đệ quy. Tuy nhiên, đệ quy mất một khoảng thời gian để bạn cân nhắc và vì điều này, nó thường chỉ được sử dụng trong các trường hợp cụ thể, trong đó vấn đề của bạn có tính chất đệ quy hoặc dữ liệu của bạn là đệ quy

Vẽ Fractal

Đối với mục đích của chúng tôi, fractal là một hình vẽ cũng có cấu trúc tự tương tự, trong đó nó có thể được định nghĩa theo chính nó. Đây là một ví dụ điển hình của một vấn đề có tính chất đệ quy

Chúng ta hãy bắt đầu bằng cách nhìn vào fractal Koch nổi tiếng. Một trật tự 0 Koch fractal chỉ đơn giản là một đường thẳng có kích thước nhất định

Một đơn đặt hàng 1 Koch fractal thu được như thế này. thay vì chỉ vẽ một đường, hãy vẽ bốn đoạn nhỏ hơn, theo mẫu được hiển thị ở đây

Bây giờ điều gì sẽ xảy ra nếu chúng ta lặp lại mẫu Koch này một lần nữa trên mỗi phân đoạn của đơn hàng 1?

Lặp lại mô hình của chúng tôi một lần nữa sẽ cho chúng tôi một đơn đặt hàng 3 Koch fractal

Bây giờ chúng ta hãy nghĩ về nó theo cách khác. Để vẽ một fractal Koch bậc 3, chúng ta chỉ cần vẽ bốn fractal Koch bậc 2. Nhưng mỗi trong số này lần lượt cần bốn fractal bậc 1 Koch, và mỗi trong số chúng lần lượt cần bốn fractal bậc 0. Cuối cùng, bản vẽ duy nhất sẽ diễn ra theo thứ tự 0. Điều này rất đơn giản để viết mã trong Python

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

def koch[tortoise, order, size]:
    """
       Make turtle tortoise draw a Koch fractal of 'order' and 'size'.
       Leave the turtle facing the same direction.
    """

    if order == 0:          # The base case is just a straight line
        tortoise.forward[size]
    else:
        koch[tortoise, order-1, size/3]   # Go 1/3 of the way
        tortoise.left[60]
        koch[tortoise, order-1, size/3]
        tortoise.right[120]
        koch[tortoise, order-1, size/3]
        tortoise.left[60]
        koch[tortoise, order-1, size/3]

Điều quan trọng mới ở đây là nếu thứ tự không bằng 0, thì

def koch[tortoise, order, size]:
    if order == 0:
        tortoise.forward[size]
    else:
        for angle in [60, -120, 60, 0]:
           koch[tortoise, order-1, size/3]
           tortoise.left[angle]

3 sẽ gọi chính nó một cách đệ quy để hoàn thành công việc của nó

Hãy quan sát đơn giản và thắt chặt mã này. Hãy nhớ rằng rẽ phải 120 cũng giống như rẽ trái -120. Vì vậy, với một chút sắp xếp lại thông minh, chúng ta có thể sử dụng một vòng lặp thay vì các dòng 10-16

1
2
3
4
5
6
7

def koch[tortoise, order, size]:
    if order == 0:
        tortoise.forward[size]
    else:
        for angle in [60, -120, 60, 0]:
           koch[tortoise, order-1, size/3]
           tortoise.left[angle]

Vòng quay cuối cùng là 0 độ — vì vậy nó không có hiệu lực. Nhưng nó đã cho phép chúng tôi tìm ra một mẫu và giảm bảy dòng mã xuống còn ba dòng, điều này sẽ giúp mọi việc dễ dàng hơn cho các lần quan sát tiếp theo của chúng tôi

Đệ quy, chế độ xem cấp cao

Một cách để nghĩ về điều này là thuyết phục bản thân rằng hàm này hoạt động chính xác khi bạn gọi nó cho một lệnh 0 fractal. Sau đó, thực hiện một bước nhảy vọt về niềm tin, nói rằng “bà tiên đỡ đầu [hoặc Python, nếu bạn có thể coi Python là bà tiên đỡ đầu của bạn] biết cách xử lý các lệnh gọi đệ quy cấp 0 cho tôi ở các dòng 11, 13, 15 và 17, . ” Tất cả những gì tôi cần tập trung vào là làm thế nào để vẽ một lệnh 1 fractal nếu tôi có thể cho rằng lệnh 0 đã hoạt động

Bạn đang thực hành tư duy trừu tượng - bỏ qua vấn đề con trong khi giải quyết vấn đề lớn

Nếu cách suy nghĩ này hoạt động [và bạn nên thực hành nó. ], sau đó đưa nó lên cấp độ tiếp theo. à há. bây giờ tôi có thể thấy rằng nó sẽ hoạt động khi được gọi cho lệnh 2 với giả định rằng nó đã hoạt động ở mức 1

Và, nói chung, nếu tôi có thể giả sử thứ tự n-1 trường hợp hoạt động, tôi có thể giải quyết vấn đề cấp n không?

Các sinh viên toán học đã chơi với bằng chứng quy nạp sẽ thấy một số điểm tương đồng rất rõ ràng ở đây

Đệ quy, chế độ xem hoạt động cấp thấp

Một cách khác để hiểu đệ quy là loại bỏ nó. Nếu chúng ta có các chức năng riêng biệt để vẽ fractal cấp 3, fractal cấp 2, fractal cấp 1 và fractal cấp 0, chúng ta có thể đơn giản hóa đoạn mã trên, khá máy móc, đến một tình huống không còn bất kỳ đệ quy nào, như thế này

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

def koch_0[tortoise, size]:
    tortoise.forward[size]

def koch_1[tortoise, size]:
    for angle in [60, -120, 60, 0]:
       koch_0[tortoise, size/3]
       tortoise.left[angle]

def koch_2[tortoise, size]:
    for angle in [60, -120, 60, 0]:
       koch_1[tortoise, size/3]
       tortoise.left[angle]

def koch_3[tortoise, size]:
    for angle in [60, -120, 60, 0]:
       koch_2[tortoise, size/3]
       tortoise.left[angle]

Thủ thuật "hủy kiểm soát" đệ quy này cho chúng ta một cái nhìn hoạt động về những gì xảy ra. Bạn có thể theo dõi chương trình thành

def koch[tortoise, order, size]:
    if order == 0:
        tortoise.forward[size]
    else:
        for angle in [60, -120, 60, 0]:
           koch[tortoise, order-1, size/3]
           tortoise.left[angle]

4, rồi từ đó, thành

def koch[tortoise, order, size]:
    if order == 0:
        tortoise.forward[size]
    else:
        for angle in [60, -120, 60, 0]:
           koch[tortoise, order-1, size/3]
           tortoise.left[angle]

5, rồi thành

def koch[tortoise, order, size]:
    if order == 0:
        tortoise.forward[size]
    else:
        for angle in [60, -120, 60, 0]:
           koch[tortoise, order-1, size/3]
           tortoise.left[angle]

6, v.v. , tất cả các lớp khác nhau của đệ quy

Đây có thể là một gợi ý hữu ích để xây dựng sự hiểu biết của bạn. Tuy nhiên, mục tiêu tinh thần là có thể thực hiện việc trừu tượng hóa

Cấu trúc dữ liệu đệ quy

Hầu hết các kiểu dữ liệu Python mà chúng ta đã thấy có thể được nhóm bên trong danh sách và bộ dữ liệu theo nhiều cách khác nhau. Danh sách và bộ dữ liệu cũng có thể được lồng vào nhau, cung cấp nhiều khả năng tổ chức dữ liệu. Việc tổ chức dữ liệu nhằm mục đích làm cho nó dễ sử dụng hơn được gọi là cấu trúc dữ liệu

Đã đến lúc bầu cử và chúng tôi đang giúp tính toán các phiếu bầu khi họ đến. Các phiếu bầu đến từ từng phường, khu bầu cử, thành phố tự trị, quận và tiểu bang đôi khi được báo cáo dưới dạng tổng số phiếu bầu và đôi khi dưới dạng danh sách tổng số phiếu bầu. Sau khi xem xét cách lưu trữ số liệu tốt nhất, chúng tôi quyết định sử dụng danh sách số lồng nhau mà chúng tôi xác định như sau

Danh sách số lồng nhau là danh sách có các phần tử hoặc

1. con số
2. danh sách số lồng nhau

Lưu ý rằng thuật ngữ, danh sách số lồng nhau được sử dụng theo định nghĩa riêng của nó. Các định nghĩa đệ quy như thế này khá phổ biến trong toán học và khoa học máy tính. Chúng cung cấp một cách ngắn gọn và mạnh mẽ để mô tả các cấu trúc dữ liệu đệ quy bao gồm một phần các thể hiện nhỏ hơn và đơn giản hơn của chính chúng. Định nghĩa không phải là vòng tròn, vì đến một lúc nào đó chúng ta sẽ đạt được một danh sách không có bất kỳ danh sách nào làm phần tử

Bây giờ, giả sử công việc của chúng ta là viết một hàm tính tổng tất cả các giá trị trong danh sách số lồng nhau. Python có một hàm tích hợp tìm tổng của một dãy số

def koch[tortoise, order, size]:
    """
       Make turtle tortoise draw a Koch fractal of 'order' and 'size'.
       Leave the turtle facing the same direction.
    """

    if order == 0:          # The base case is just a straight line
        tortoise.forward[size]
    else:
        koch[tortoise, order-1, size/3]   # Go 1/3 of the way
        tortoise.left[60]
        koch[tortoise, order-1, size/3]
        tortoise.right[120]
        koch[tortoise, order-1, size/3]
        tortoise.left[60]
        koch[tortoise, order-1, size/3]

0

Tuy nhiên, đối với danh sách số lồng nhau của chúng tôi,

def koch[tortoise, order, size]:
    if order == 0:
        tortoise.forward[size]
    else:
        for angle in [60, -120, 60, 0]:
           koch[tortoise, order-1, size/3]
           tortoise.left[angle]

7 sẽ không hoạt động

def koch[tortoise, order, size]:
    """
       Make turtle tortoise draw a Koch fractal of 'order' and 'size'.
       Leave the turtle facing the same direction.
    """

    if order == 0:          # The base case is just a straight line
        tortoise.forward[size]
    else:
        koch[tortoise, order-1, size/3]   # Go 1/3 of the way
        tortoise.left[60]
        koch[tortoise, order-1, size/3]
        tortoise.right[120]
        koch[tortoise, order-1, size/3]
        tortoise.left[60]
        koch[tortoise, order-1, size/3]

2

Vấn đề là phần tử thứ ba của danh sách này,

def koch[tortoise, order, size]:
    if order == 0:
        tortoise.forward[size]
    else:
        for angle in [60, -120, 60, 0]:
           koch[tortoise, order-1, size/3]
           tortoise.left[angle]

8, bản thân nó là một danh sách, vì vậy nó không thể được thêm vào

def koch[tortoise, order, size]:
    if order == 0:
        tortoise.forward[size]
    else:
        for angle in [60, -120, 60, 0]:
           koch[tortoise, order-1, size/3]
           tortoise.left[angle]

9,

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

0 và

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

1

Xử lý danh sách số đệ quy

Để tính tổng tất cả các số trong danh sách số lồng nhau đệ quy của chúng ta, chúng ta cần duyệt qua danh sách, truy cập từng phần tử trong cấu trúc lồng nhau của nó, thêm bất kỳ phần tử số nào vào tổng của chúng ta và lặp lại đệ quy quy trình tính tổng với bất kỳ phần tử nào mà chính chúng là con

Nhờ đệ quy, mã Python cần thiết để tính tổng các giá trị của danh sách số lồng nhau ngắn một cách đáng ngạc nhiên

def koch[tortoise, order, size]:
    """
       Make turtle tortoise draw a Koch fractal of 'order' and 'size'.
       Leave the turtle facing the same direction.
    """

    if order == 0:          # The base case is just a straight line
        tortoise.forward[size]
    else:
        koch[tortoise, order-1, size/3]   # Go 1/3 of the way
        tortoise.left[60]
        koch[tortoise, order-1, size/3]
        tortoise.right[120]
        koch[tortoise, order-1, size/3]
        tortoise.left[60]
        koch[tortoise, order-1, size/3]

7

def koch[tortoise, order, size]:
    """
       Make turtle tortoise draw a Koch fractal of 'order' and 'size'.
       Leave the turtle facing the same direction.
    """

    if order == 0:          # The base case is just a straight line
        tortoise.forward[size]
    else:
        koch[tortoise, order-1, size/3]   # Go 1/3 of the way
        tortoise.left[60]
        koch[tortoise, order-1, size/3]
        tortoise.right[120]
        koch[tortoise, order-1, size/3]
        tortoise.left[60]
        koch[tortoise, order-1, size/3]

8

Phần thân của

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

2 chủ yếu bao gồm một vòng lặp

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

3 đi ngang qua

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

4. Nếu

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

5 là một giá trị số [nhánh

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

6], nó chỉ cần được thêm vào

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

7. Nếu

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

5 là một danh sách, thì

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

2 được gọi lại, với phần tử làm đối số. Câu lệnh bên trong định nghĩa hàm trong đó hàm gọi chính nó được gọi là lời gọi đệ quy

Ví dụ trên có trường hợp cơ sở [trên dòng 13] không dẫn đến lệnh gọi đệ quy. trường hợp phần tử không phải là danh sách [phụ]. Không có trường hợp cơ sở, bạn sẽ có đệ quy vô hạn và chương trình của bạn sẽ không hoạt động

Một giải pháp thay thế, đệ quy hoàn toàn, sẽ như sau. Lưu ý rằng việc triển khai này không chứa vòng lặp

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

3

def koch[tortoise, order, size]:
    """
       Make turtle tortoise draw a Koch fractal of 'order' and 'size'.
       Leave the turtle facing the same direction.
    """

    if order == 0:          # The base case is just a straight line
        tortoise.forward[size]
    else:
        koch[tortoise, order-1, size/3]   # Go 1/3 of the way
        tortoise.left[60]
        koch[tortoise, order-1, size/3]
        tortoise.right[120]
        koch[tortoise, order-1, size/3]
        tortoise.left[60]
        koch[tortoise, order-1, size/3]

7

def koch[tortoise, order, size]:
    """
       Make turtle tortoise draw a Koch fractal of 'order' and 'size'.
       Leave the turtle facing the same direction.
    """

    if order == 0:          # The base case is just a straight line
        tortoise.forward[size]
    else:
        koch[tortoise, order-1, size/3]   # Go 1/3 of the way
        tortoise.left[60]
        koch[tortoise, order-1, size/3]
        tortoise.right[120]
        koch[tortoise, order-1, size/3]
        tortoise.left[60]
        koch[tortoise, order-1, size/3]

1

Đệ quy thực sự là một trong những công cụ đẹp và thanh lịch nhất trong khoa học máy tính

Một vấn đề phức tạp hơn một chút là tìm giá trị lớn nhất trong danh sách số lồng nhau của chúng tôi

def koch[tortoise, order, size]:
    """
       Make turtle tortoise draw a Koch fractal of 'order' and 'size'.
       Leave the turtle facing the same direction.
    """

    if order == 0:          # The base case is just a straight line
        tortoise.forward[size]
    else:
        koch[tortoise, order-1, size/3]   # Go 1/3 of the way
        tortoise.left[60]
        koch[tortoise, order-1, size/3]
        tortoise.right[120]
        koch[tortoise, order-1, size/3]
        tortoise.left[60]
        koch[tortoise, order-1, size/3]

2

def koch[tortoise, order, size]:
    """
       Make turtle tortoise draw a Koch fractal of 'order' and 'size'.
       Leave the turtle facing the same direction.
    """

    if order == 0:          # The base case is just a straight line
        tortoise.forward[size]
    else:
        koch[tortoise, order-1, size/3]   # Go 1/3 of the way
        tortoise.left[60]
        koch[tortoise, order-1, size/3]
        tortoise.right[120]
        koch[tortoise, order-1, size/3]
        tortoise.left[60]
        koch[tortoise, order-1, size/3]

3

Vấn đề bổ sung cho vấn đề này là tìm một giá trị để khởi tạo

def koch_0[tortoise, size]:
    tortoise.forward[size]

def koch_1[tortoise, size]:
    for angle in [60, -120, 60, 0]:
       koch_0[tortoise, size/3]
       tortoise.left[angle]

def koch_2[tortoise, size]:
    for angle in [60, -120, 60, 0]:
       koch_1[tortoise, size/3]
       tortoise.left[angle]

def koch_3[tortoise, size]:
    for angle in [60, -120, 60, 0]:
       koch_2[tortoise, size/3]
       tortoise.left[angle]

1. Chúng ta không thể chỉ sử dụng _______ 62, vì đó có thể là một phần tử hoặc một danh sách. Để giải quyết vấn đề này [ở mọi cuộc gọi đệ quy], chúng tôi khởi tạo cờ Boolean [ở dòng 8]. Khi chúng tôi tìm thấy giá trị quan tâm, [ở dòng 15], chúng tôi kiểm tra xem liệu đây có phải là giá trị khởi tạo [đầu tiên] cho

def koch_0[tortoise, size]:
    tortoise.forward[size]

def koch_1[tortoise, size]:
    for angle in [60, -120, 60, 0]:
       koch_0[tortoise, size/3]
       tortoise.left[angle]

def koch_2[tortoise, size]:
    for angle in [60, -120, 60, 0]:
       koch_1[tortoise, size/3]
       tortoise.left[angle]

def koch_3[tortoise, size]:
    for angle in [60, -120, 60, 0]:
       koch_2[tortoise, size/3]
       tortoise.left[angle]

1 hay giá trị có khả năng thay đổi

def koch_0[tortoise, size]:
    tortoise.forward[size]

def koch_1[tortoise, size]:
    for angle in [60, -120, 60, 0]:
       koch_0[tortoise, size/3]
       tortoise.left[angle]

def koch_2[tortoise, size]:
    for angle in [60, -120, 60, 0]:
       koch_1[tortoise, size/3]
       tortoise.left[angle]

def koch_3[tortoise, size]:
    for angle in [60, -120, 60, 0]:
       koch_2[tortoise, size/3]
       tortoise.left[angle]

1

Một lần nữa ở đây chúng ta có một trường hợp cơ bản ở dòng 13. Nếu chúng tôi không cung cấp trường hợp cơ sở, Python sẽ dừng sau khi đạt đến độ sâu đệ quy tối đa và trả về lỗi thời gian chạy. Xem điều này xảy ra như thế nào, bằng cách chạy tập lệnh nhỏ này mà chúng ta sẽ gọi là Infinite_recursion. py

def koch[tortoise, order, size]:
    """
       Make turtle tortoise draw a Koch fractal of 'order' and 'size'.
       Leave the turtle facing the same direction.
    """

    if order == 0:          # The base case is just a straight line
        tortoise.forward[size]
    else:
        koch[tortoise, order-1, size/3]   # Go 1/3 of the way
        tortoise.left[60]
        koch[tortoise, order-1, size/3]
        tortoise.right[120]
        koch[tortoise, order-1, size/3]
        tortoise.left[60]
        koch[tortoise, order-1, size/3]

4

def koch[tortoise, order, size]:
    """
       Make turtle tortoise draw a Koch fractal of 'order' and 'size'.
       Leave the turtle facing the same direction.
    """

    if order == 0:          # The base case is just a straight line
        tortoise.forward[size]
    else:
        koch[tortoise, order-1, size/3]   # Go 1/3 of the way
        tortoise.left[60]
        koch[tortoise, order-1, size/3]
        tortoise.right[120]
        koch[tortoise, order-1, size/3]
        tortoise.left[60]
        koch[tortoise, order-1, size/3]

5

Sau khi xem các tin nhắn lướt qua, bạn sẽ thấy phần cuối của một truy nguyên dài kết thúc bằng một thông báo như sau

def koch[tortoise, order, size]:
    """
       Make turtle tortoise draw a Koch fractal of 'order' and 'size'.
       Leave the turtle facing the same direction.
    """

    if order == 0:          # The base case is just a straight line
        tortoise.forward[size]
    else:
        koch[tortoise, order-1, size/3]   # Go 1/3 of the way
        tortoise.left[60]
        koch[tortoise, order-1, size/3]
        tortoise.right[120]
        koch[tortoise, order-1, size/3]
        tortoise.left[60]
        koch[tortoise, order-1, size/3]

6

Chúng tôi chắc chắn sẽ không bao giờ muốn điều gì đó như thế này xảy ra với người dùng của một trong các chương trình của chúng tôi, vì vậy trong một phụ lục khác, chúng tôi sẽ xem cách xử lý lỗi, bất kỳ loại lỗi nào trong Python

nghiên cứu điển hình. số Fibonacci

Dãy Fibonacci nổi tiếng 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 134, … do Fibonacci [1170-1250] nghĩ ra, người đã sử dụng dãy này để mô hình hóa [ . Nếu ở thế hệ thứ 7, bạn có tổng cộng 21 cặp, trong đó có 13 cặp trưởng thành, thì thế hệ tiếp theo, tất cả những người trưởng thành sẽ sinh ra những đứa trẻ mới và những đứa trẻ trước đó sẽ lớn lên thành người lớn. Vì vậy, ở thế hệ 8, bạn sẽ có 13+21=34, trong đó 21 người lớn

Mô hình này để giải thích việc chăn nuôi thỏ đã đưa ra giả định đơn giản hóa rằng thỏ không bao giờ chết. Các nhà khoa học thường đưa ra các giả định và hạn chế đơn giản hóa [không thực tế] để giải quyết vấn đề

Nếu chúng ta đánh số các phần tử của dãy từ 0, chúng ta có thể mô tả đệ quy mỗi phần tử là tổng của hai phần tử trước đó

def koch[tortoise, order, size]:
    """
       Make turtle tortoise draw a Koch fractal of 'order' and 'size'.
       Leave the turtle facing the same direction.
    """

    if order == 0:          # The base case is just a straight line
        tortoise.forward[size]
    else:
        koch[tortoise, order-1, size/3]   # Go 1/3 of the way
        tortoise.left[60]
        koch[tortoise, order-1, size/3]
        tortoise.right[120]
        koch[tortoise, order-1, size/3]
        tortoise.left[60]
        koch[tortoise, order-1, size/3]

7

Điều này dịch rất trực tiếp sang một số Python

def koch[tortoise, order, size]:
    """
       Make turtle tortoise draw a Koch fractal of 'order' and 'size'.
       Leave the turtle facing the same direction.
    """

    if order == 0:          # The base case is just a straight line
        tortoise.forward[size]
    else:
        koch[tortoise, order-1, size/3]   # Go 1/3 of the way
        tortoise.left[60]
        koch[tortoise, order-1, size/3]
        tortoise.right[120]
        koch[tortoise, order-1, size/3]
        tortoise.left[60]
        koch[tortoise, order-1, size/3]

4

def koch[tortoise, order, size]:
    """
       Make turtle tortoise draw a Koch fractal of 'order' and 'size'.
       Leave the turtle facing the same direction.
    """

    if order == 0:          # The base case is just a straight line
        tortoise.forward[size]
    else:
        koch[tortoise, order-1, size/3]   # Go 1/3 of the way
        tortoise.left[60]
        koch[tortoise, order-1, size/3]
        tortoise.right[120]
        koch[tortoise, order-1, size/3]
        tortoise.left[60]
        koch[tortoise, order-1, size/3]

9

Đây là một thuật toán đặc biệt không hiệu quả và điều này có thể được giải quyết lặp đi lặp lại hiệu quả hơn nhiều

1
2
3
4
5
6
7

1
2
3
4
5
6
7

1

Chúng tôi nhận được kết quả chính xác, nhưng khối lượng công việc tăng vọt

1
2
3
4
5
6
7

2

Ví dụ với các thư mục và tệp đệ quy

Chương trình sau liệt kê nội dung của một thư mục và tất cả các thư mục con của nó

1
2
3
4
5
6
7

3

1
2
3
4
5
6
7

4

Gọi hàm

def koch_0[tortoise, size]:
    tortoise.forward[size]

def koch_1[tortoise, size]:
    for angle in [60, -120, 60, 0]:
       koch_0[tortoise, size/3]
       tortoise.left[angle]

def koch_2[tortoise, size]:
    for angle in [60, -120, 60, 0]:
       koch_1[tortoise, size/3]
       tortoise.left[angle]

def koch_3[tortoise, size]:
    for angle in [60, -120, 60, 0]:
       koch_2[tortoise, size/3]
       tortoise.left[angle]

5 với một số tên thư mục sẽ tạo ra kết quả tương tự như thế này

1
2
3
4
5
6
7

5

Lưu ý rằng một cái gì đó tương tự đã được triển khai trong mô-đun os. hệ điều hành. đi bộ

Một fractal hoạt hình, sử dụng PyGame

Ở đây chúng ta có một mô hình cây fractal bậc 8. Chúng tôi đã gắn nhãn một số cạnh, hiển thị độ sâu của phép đệ quy tại đó mỗi cạnh được vẽ

Ở cây trên, góc lệch so với thân cây là 30 độ. Thay đổi góc đó sẽ tạo ra các hình dạng thú vị khác, ví dụ, với góc 90 độ, chúng ta có được điều này

Một hình ảnh động thú vị sẽ xảy ra nếu chúng ta tạo và vẽ cây rất nhanh, mỗi lần thay đổi góc độ một chút. Mặc dù mô-đun Rùa có thể vẽ những cái cây như thế này khá đẹp mắt, nhưng chúng tôi có thể phải vật lộn để đạt được tốc độ khung hình tốt. Vì vậy, chúng tôi sẽ sử dụng PyGame để thay thế, với một vài điểm nhấn và quan sát. [Một lần nữa, chúng tôi khuyên bạn nên cắt và dán mã này vào môi trường Python của mình. ]

1
2
3
4
5
6
7

6

1
2
3
4
5
6
7

7

• Thư viện

  def koch_0[tortoise, size]:
      tortoise.forward[size]
  
  def koch_1[tortoise, size]:
      for angle in [60, -120, 60, 0]:
         koch_0[tortoise, size/3]
         tortoise.left[angle]
  
  def koch_2[tortoise, size]:
      for angle in [60, -120, 60, 0]:
         koch_1[tortoise, size/3]
         tortoise.left[angle]
  
  def koch_3[tortoise, size]:
      for angle in [60, -120, 60, 0]:
         koch_2[tortoise, size/3]
         tortoise.left[angle]
  

  6 hoạt động với các góc tính bằng radian chứ không phải độ

• Dòng 14 và 15 sử dụng một số lượng giác trung học. Từ độ dài của đoạn thẳng mong muốn [

  def koch_0[tortoise, size]:
      tortoise.forward[size]
  
  def koch_1[tortoise, size]:
      for angle in [60, -120, 60, 0]:
         koch_0[tortoise, size/3]
         tortoise.left[angle]
  
  def koch_2[tortoise, size]:
      for angle in [60, -120, 60, 0]:
         koch_1[tortoise, size/3]
         tortoise.left[angle]
  
  def koch_3[tortoise, size]:
      for angle in [60, -120, 60, 0]:
         koch_2[tortoise, size/3]
         tortoise.left[angle]
  

  7] và góc mong muốn của nó,

  def koch_0[tortoise, size]:
      tortoise.forward[size]
  
  def koch_1[tortoise, size]:
      for angle in [60, -120, 60, 0]:
         koch_0[tortoise, size/3]
         tortoise.left[angle]
  
  def koch_2[tortoise, size]:
      for angle in [60, -120, 60, 0]:
         koch_1[tortoise, size/3]
         tortoise.left[angle]
  
  def koch_3[tortoise, size]:
      for angle in [60, -120, 60, 0]:
         koch_2[tortoise, size/3]
         tortoise.left[angle]
  

  8 và

  def koch_0[tortoise, size]:
      tortoise.forward[size]
  
  def koch_1[tortoise, size]:
      for angle in [60, -120, 60, 0]:
         koch_0[tortoise, size/3]
         tortoise.left[angle]
  
  def koch_2[tortoise, size]:
      for angle in [60, -120, 60, 0]:
         koch_1[tortoise, size/3]
         tortoise.left[angle]
  
  def koch_3[tortoise, size]:
      for angle in [60, -120, 60, 0]:
         koch_2[tortoise, size/3]
         tortoise.left[angle]
  

  9 giúp chúng tôi tính toán khoảng cách

  def koch[tortoise, order, size]:
      """
         Make turtle tortoise draw a Koch fractal of 'order' and 'size'.
         Leave the turtle facing the same direction.
      """
  
      if order == 0:          # The base case is just a straight line
          tortoise.forward[size]
      else:
          koch[tortoise, order-1, size/3]   # Go 1/3 of the way
          tortoise.left[60]
          koch[tortoise, order-1, size/3]
          tortoise.right[120]
          koch[tortoise, order-1, size/3]
          tortoise.left[60]
          koch[tortoise, order-1, size/3]
  

  00 và

  def koch[tortoise, order, size]:
      """
         Make turtle tortoise draw a Koch fractal of 'order' and 'size'.
         Leave the turtle facing the same direction.
      """
  
      if order == 0:          # The base case is just a straight line
          tortoise.forward[size]
      else:
          koch[tortoise, order-1, size/3]   # Go 1/3 of the way
          tortoise.left[60]
          koch[tortoise, order-1, size/3]
          tortoise.right[120]
          koch[tortoise, order-1, size/3]
          tortoise.left[60]
          koch[tortoise, order-1, size/3]
  

  01 mà chúng tôi cần di chuyển

• Các dòng 22-30 là không cần thiết, trừ khi chúng ta muốn một cái cây đầy màu sắc

• Trong vòng lặp trò chơi chính ở dòng 49, chúng tôi thay đổi góc trên mọi khung hình và vẽ lại cây mới

• Dòng 18 cho thấy PyGame cũng có thể vẽ các đường và hơn thế nữa. Kiểm tra các tài liệu. Ví dụ: vẽ một vòng tròn nhỏ tại mỗi điểm nhánh của cây có thể được thực hiện bằng cách thêm dòng này ngay bên dưới dòng 18

  1
  2
  3
  4
  5
  6
  7

  8

  1
  2
  3
  4
  5
  6
  7

  9

Một hiệu ứng thú vị khác - cũng mang tính hướng dẫn, nếu bạn muốn củng cố ý tưởng về các trường hợp khác nhau của hàm được gọi ở các độ sâu đệ quy khác nhau - là tạo một danh sách các màu và để mỗi độ sâu đệ quy sử dụng một màu khác nhau để vẽ. [Sử dụng độ sâu của đệ quy để lập chỉ mục danh sách màu. ]

đệ quy lẫn nhau

Ngoài một hàm chỉ gọi chính nó, cũng có thể tạo nhiều hàm gọi lẫn nhau. Điều này hiếm khi thực sự hữu ích, nhưng nó có thể được sử dụng để tạo các máy trạng thái

def koch[tortoise, order, size]:
    if order == 0:
        tortoise.forward[size]
    else:
        for angle in [60, -120, 60, 0]:
           koch[tortoise, order-1, size/3]
           tortoise.left[angle]

0

def koch[tortoise, order, size]:
    if order == 0:
        tortoise.forward[size]
    else:
        for angle in [60, -120, 60, 0]:
           koch[tortoise, order-1, size/3]
           tortoise.left[angle]

1

Bảng chú giải

trường hợp cơ sởMột nhánh của câu lệnh điều kiện trong một hàm đệ quy không làm phát sinh các lệnh gọi đệ quy tiếp theo. đệ quy vô hạnMột hàm gọi chính nó theo cách đệ quy mà không bao giờ đạt đến bất kỳ trường hợp cơ sở nào. Cuối cùng, đệ quy vô hạn gây ra lỗi thời gian chạy. đệ quyQuá trình gọi một chức năng đã được thực thi. lời gọi đệ quyCâu lệnh gọi một hàm đã được thực thi. Đệ quy cũng có thể là gián tiếp — hàm f có thể gọi g gọi h và h có thể gọi lại f. hàm định nghĩa đệ quy định nghĩa một cái gì đó theo chính nó. Để hữu ích, nó phải bao gồm các trường hợp cơ sở không đệ quy. Theo cách này, nó khác với định nghĩa vòng tròn. Các định nghĩa đệ quy thường cung cấp một cách tinh tế để thể hiện các cấu trúc dữ liệu phức tạp, chẳng hạn như một thư mục có thể chứa các thư mục khác hoặc một menu có thể chứa các menu khác

bài tập

1. Sửa đổi chương trình fractal Koch để nó vẽ một bông tuyết Koch, như thế này

   
   

2. 1. Vẽ một fractal đường rách Cesaro, theo thứ tự do người dùng đưa ra. Chúng tôi hiển thị bốn dòng lệnh khác nhau 0,1,2,3. Trong ví dụ này, góc xé là 10 độ

   2. Bốn dòng tạo thành một hình vuông. Sử dụng mã trong phần a] để vẽ hình vuông cesaro. Thay đổi góc mang lại hiệu ứng thú vị — thử nghiệm một chút hoặc có thể cho phép người dùng nhập góc xé
   1. [Dành cho người thiên về toán học]. Trong các ô vuông được hiển thị ở đây, các bản vẽ bậc cao hơn sẽ lớn hơn một chút. [Hãy nhìn vào các dòng dưới cùng của mỗi ô vuông - chúng không thẳng hàng. ] Điều này là do chúng tôi chỉ giảm một nửa phần được vẽ của dòng cho mỗi bài toán con đệ quy. Vì vậy, chúng tôi đã "phát triển" hình vuông tổng thể bằng chiều rộng của [các] vết rách. Bạn có thể giải bài toán hình học sao cho tổng kích thước của trường hợp bài toán con [bao gồm cả vết rách] vẫn giữ nguyên kích thước như ban đầu không?

   
   

3. Tam giác Sierpinki bậc 0 là tam giác đều. Có thể vẽ một hình tam giác bậc 1 bằng cách vẽ 3 hình tam giác nhỏ hơn [hiển thị hơi bị ngắt kết nối ở đây, chỉ để giúp chúng ta hiểu]. Hình tam giác bậc 2 và 3 cao hơn cũng được hiển thị. Vẽ hình tam giác Sierpinki theo bất kỳ thứ tự nào người dùng nhập vào

4. Điều chỉnh chương trình trên để thay đổi màu của ba tam giác con của nó ở một số độ sâu của đệ quy. Hình minh họa dưới đây cho thấy hai trường hợp. ở bên trái, màu được thay đổi ở độ sâu 0 [mức đệ quy ngoài cùng], ở bên phải, ở độ sâu 2. Nếu người dùng cung cấp độ sâu âm, màu sẽ không bao giờ thay đổi. [Gợi ý. thêm một tham số tùy chọn mới

   def koch[tortoise, order, size]:
       """
          Make turtle tortoise draw a Koch fractal of 'order' and 'size'.
          Leave the turtle facing the same direction.
       """
   
       if order == 0:          # The base case is just a straight line
           tortoise.forward[size]
       else:
           koch[tortoise, order-1, size/3]   # Go 1/3 of the way
           tortoise.left[60]
           koch[tortoise, order-1, size/3]
           tortoise.right[120]
           koch[tortoise, order-1, size/3]
           tortoise.left[60]
           koch[tortoise, order-1, size/3]
   

   02 [mặc định là -1] và làm cho tham số này nhỏ hơn trên mỗi cuộc gọi con đệ quy. Sau đó, trong phần mã trước khi bạn lặp lại, hãy kiểm tra xem tham số có bằng 0 không và thay đổi màu. ]

5. Viết hàm,

   def koch[tortoise, order, size]:
       """
          Make turtle tortoise draw a Koch fractal of 'order' and 'size'.
          Leave the turtle facing the same direction.
       """
   
       if order == 0:          # The base case is just a straight line
           tortoise.forward[size]
       else:
           koch[tortoise, order-1, size/3]   # Go 1/3 of the way
           tortoise.left[60]
           koch[tortoise, order-1, size/3]
           tortoise.right[120]
           koch[tortoise, order-1, size/3]
           tortoise.left[60]
           koch[tortoise, order-1, size/3]
   

   03, trả về giá trị nhỏ nhất trong danh sách số lồng nhau. Giả sử không có danh sách trống hoặc danh sách con

6. Viết hàm

   def koch[tortoise, order, size]:
       """
          Make turtle tortoise draw a Koch fractal of 'order' and 'size'.
          Leave the turtle facing the same direction.
       """
   
       if order == 0:          # The base case is just a straight line
           tortoise.forward[size]
       else:
           koch[tortoise, order-1, size/3]   # Go 1/3 of the way
           tortoise.left[60]
           koch[tortoise, order-1, size/3]
           tortoise.right[120]
           koch[tortoise, order-1, size/3]
           tortoise.left[60]
           koch[tortoise, order-1, size/3]
   

   04 trả về số lần xuất hiện của

   def koch[tortoise, order, size]:
       """
          Make turtle tortoise draw a Koch fractal of 'order' and 'size'.
          Leave the turtle facing the same direction.
       """
   
       if order == 0:          # The base case is just a straight line
           tortoise.forward[size]
       else:
           koch[tortoise, order-1, size/3]   # Go 1/3 of the way
           tortoise.left[60]
           koch[tortoise, order-1, size/3]
           tortoise.right[120]
           koch[tortoise, order-1, size/3]
           tortoise.left[60]
           koch[tortoise, order-1, size/3]
   

   05 trong danh sách lồng nhau

7. Viết hàm

   def koch[tortoise, order, size]:
       """
          Make turtle tortoise draw a Koch fractal of 'order' and 'size'.
          Leave the turtle facing the same direction.
       """
   
       if order == 0:          # The base case is just a straight line
           tortoise.forward[size]
       else:
           koch[tortoise, order-1, size/3]   # Go 1/3 of the way
           tortoise.left[60]
           koch[tortoise, order-1, size/3]
           tortoise.right[120]
           koch[tortoise, order-1, size/3]
           tortoise.left[60]
           koch[tortoise, order-1, size/3]
   

   06 trả về một danh sách đơn giản chứa tất cả các giá trị trong danh sách lồng nhau

8. Viết lại thuật toán fibonacci không sử dụng đệ quy. Bạn có thể tìm các số hạng lớn hơn của dãy không?

9. Sử dụng trợ giúp để tìm hiểu những gì

   def koch[tortoise, order, size]:
       """
          Make turtle tortoise draw a Koch fractal of 'order' and 'size'.
          Leave the turtle facing the same direction.
       """
   
       if order == 0:          # The base case is just a straight line
           tortoise.forward[size]
       else:
           koch[tortoise, order-1, size/3]   # Go 1/3 of the way
           tortoise.left[60]
           koch[tortoise, order-1, size/3]
           tortoise.right[120]
           koch[tortoise, order-1, size/3]
           tortoise.left[60]
           koch[tortoise, order-1, size/3]
   

   08 và

   def koch[tortoise, order, size]:
       """
          Make turtle tortoise draw a Koch fractal of 'order' and 'size'.
          Leave the turtle facing the same direction.
       """
   
       if order == 0:          # The base case is just a straight line
           tortoise.forward[size]
       else:
           koch[tortoise, order-1, size/3]   # Go 1/3 of the way
           tortoise.left[60]
           koch[tortoise, order-1, size/3]
           tortoise.right[120]
           koch[tortoise, order-1, size/3]
           tortoise.left[60]
           koch[tortoise, order-1, size/3]
   

   09 làm. Tạo một số thử nghiệm tương tự như những gì đã được thực hiện trong Infinite_recursion. py để kiểm tra hiểu biết của bạn về cách hoạt động của các chức năng mô-đun này

10. Viết chương trình duyệt cấu trúc thư mục [như trong phần cuối của chương này], nhưng thay vì in tên tệp, nó trả về danh sách tất cả đường dẫn đầy đủ của tệp trong thư mục hoặc thư mục con. [Không bao gồm các thư mục trong danh sách này - chỉ các tệp. ] Ví dụ, danh sách đầu ra có thể có các phần tử như thế này

    def koch[tortoise, order, size]:
        if order == 0:
            tortoise.forward[size]
        else:
            for angle in [60, -120, 60, 0]:
               koch[tortoise, order-1, size/3]
               tortoise.left[angle]
    

    2

11. Viết chương trình có tên là

    def koch[tortoise, order, size]:
        """
           Make turtle tortoise draw a Koch fractal of 'order' and 'size'.
           Leave the turtle facing the same direction.
        """
    
        if order == 0:          # The base case is just a straight line
            tortoise.forward[size]
        else:
            koch[tortoise, order-1, size/3]   # Go 1/3 of the way
            tortoise.left[60]
            koch[tortoise, order-1, size/3]
            tortoise.right[120]
            koch[tortoise, order-1, size/3]
            tortoise.left[60]
            koch[tortoise, order-1, size/3]
    

    20 để tạo một tệp trống có tên là

    def koch[tortoise, order, size]:
        """
           Make turtle tortoise draw a Koch fractal of 'order' and 'size'.
           Leave the turtle facing the same direction.
        """
    
        if order == 0:          # The base case is just a straight line
            tortoise.forward[size]
        else:
            koch[tortoise, order-1, size/3]   # Go 1/3 of the way
            tortoise.left[60]
            koch[tortoise, order-1, size/3]
            tortoise.right[120]
            koch[tortoise, order-1, size/3]
            tortoise.left[60]
            koch[tortoise, order-1, size/3]
    

    21 trong mỗi thư mục con của cây thư mục với gốc của cây làm đối số [hoặc thư mục hiện tại làm mặc định]. Bây giờ hãy viết một chương trình tên là

    def koch[tortoise, order, size]:
        """
           Make turtle tortoise draw a Koch fractal of 'order' and 'size'.
           Leave the turtle facing the same direction.
        """
    
        if order == 0:          # The base case is just a straight line
            tortoise.forward[size]
        else:
            koch[tortoise, order-1, size/3]   # Go 1/3 of the way
            tortoise.left[60]
            koch[tortoise, order-1, size/3]
            tortoise.right[120]
            koch[tortoise, order-1, size/3]
            tortoise.left[60]
            koch[tortoise, order-1, size/3]
    

    22 để loại bỏ tất cả các tệp này

    Gợi ý số 1. Sử dụng chương trình từ ví dụ trong phần cuối của chương này làm cơ sở cho hai chương trình đệ quy này. Bởi vì bạn sẽ hủy các tệp trên đĩa của mình, tốt hơn hết bạn nên làm điều này đúng, nếu không bạn có nguy cơ mất các tệp mà bạn quan tâm. Vì vậy, lời khuyên tuyệt vời là ban đầu bạn nên giả mạo việc xóa các tệp — chỉ cần in tên đường dẫn đầy đủ của từng tệp mà bạn định xóa. Khi bạn hài lòng vì logic của mình là đúng và bạn có thể thấy rằng bạn không xóa những thứ sai, bạn có thể thay thế câu lệnh in bằng câu lệnh thực

    Danh sách đệ quy trong R là gì?

    Danh sách có thể đệ quy, nghĩa là bạn có thể có danh sách trong danh sách . Đây là một ví dụ. > b

    Đuôi Python có đệ quy không?

    Chúng ta cần Python loại bỏ khung trước đó khi một hàm đệ quy đuôi gọi chính nó. Tối ưu hóa cuộc gọi đuôi là một phương pháp cho phép đệ quy vô hạn các hàm đệ quy đuôi xảy ra mà không bị tràn ngăn xếp . Tối ưu hóa cuộc gọi đuôi chuyển đổi cuộc gọi đệ quy thành một vòng lặp.

    Trường hợp cơ sở trong đệ quy trong Python là gì?

    Trường hợp cơ bản là điều kiện để dừng đệ quy . Trường hợp đệ quy là phần mà hàm tự gọi.

    Lặp lại có nhanh hơn đệ quy không?

    Lặp nhanh hơn và hiệu quả hơn đệ quy . Việc tối ưu hóa các mã lặp lại dễ dàng hơn và chúng thường có độ phức tạp về thời gian đa thức. Chúng được sử dụng để lặp lại các phần tử có trong cấu trúc dữ liệu như mảng, tập hợp, bản đồ, v.v.