Chuyển đổi vòng lặp thành python đệ quy

Theo Ronald Graham, Đệ quy là một phương pháp giải quyết vấn đề trong đó giải pháp phụ thuộc vào các giải pháp cho các trường hợp nhỏ hơn của cùng một vấn đề

dễ đọc hơn vì nó tuân theo định nghĩa của các số Fibonacci

Tuy nhiên, vì độ sâu của ngăn xếp bị hạn chế nên nó sẽ gây tràn cho

lớn. Ngược lại, hàm lặp chạy trong cùng một khung. Hơn nữa, hàm đệ quy có độ phức tạp theo cấp số nhân, trong khi hàm lặp là tuyến tính. Đó là lý do tại sao đôi khi chúng ta cần chuyển thuật toán đệ quy sang thuật toán lặp. Những gì chúng tôi mất trong khả năng đọc, chúng tôi đạt được trong hiệu suất.

3. Chuyển đổi các hàm đệ quy đuôi

Trường hợp đơn giản nhất để xử lý là đệ quy đuôi. Các hàm như vậy hoàn thành tất cả công việc trong phần thân của chúng [nhánh không phải cơ sở] vào thời điểm cuộc gọi đệ quy kết thúc, do đó, không có gì khác để làm vào thời điểm đó ngoài việc trả về giá trị của nó. Nói chung, họ làm theo cùng một mô hình

Bộ tích lũy là biến chứa các giải pháp một phần trong quá trình thực hiện. Chúng đại diện cho các giải pháp cho một chuỗi các vấn đề phụ, được lồng vào nhau. Mỗi cuộc gọi cập nhật bộ tích lũy cho đến khi đệ quy đạt đến trường hợp cơ sở. Tại thời điểm đó, bộ tích lũy nắm giữ giải pháp cho toàn bộ vấn đề mà chúng tôi đã bắt đầu giải quyết ngay từ đầu

3. 1. Phiên bản lặp lại của đệ quy đuôi

Mẫu đệ quy đuôi ở trên có phiên bản lặp sau

Từ đó, chúng tôi xây dựng các quy tắc chung của chuyển đổi

• Khởi tạo bộ tích lũy trước vòng lặp while
• Sử dụng phủ định của điều kiện trường hợp cơ sở làm điều kiện của vòng lặp
• Sử dụng phần thân của hàm đệ quy [ngoại trừ lệnh gọi đệ quy] làm phần thân của vòng lặp while
• Sau vòng lặp, hãy áp dụng bản cập nhật trường hợp cơ sở của bộ tích lũy và trả về giá trị của nó

Thông thường, bản cập nhật trường hợp cơ sở không thay đổi giá trị của bộ tích lũy vì nó thường dẫn đến một hoạt động trung lập, chẳng hạn như cộng 0 hoặc nhân với 1 hoặc không có bản cập nhật nào được áp dụng. Vì vậy, chúng ta có thể bỏ qua phần này trong hầu hết các trường hợp. Tuy nhiên, chúng tôi giữ nó trong mã giả để giải thích cho các chức năng có cập nhật trường hợp cơ sở là không tầm thường. Ví dụ: đó là trường hợp nếu chúng ta có nhiều trường hợp cơ sở và mỗi trường hợp kết hợp một giá trị khác nhau với bộ tích lũy. Đó cũng là trường hợp nếu bản cập nhật trường hợp cơ sở phụ thuộc vào bộ tích lũy

3. 2. Ví dụ

Hãy sử dụng các quy tắc đó và chuyển đổi hàm đệ quy đuôi để tính giai thừa

Bây giờ chúng ta hãy xác định các phần tử của đệ quy đuôi này mà chúng ta sẽ sắp xếp lại trong biến thể lặp

• điều kiện trường hợp cơ sở.
• cập nhật bộ tích lũy trường hợp cơ sở. nhân với 1
• giá trị ban đầu của bộ tích lũy. 1
• cập nhật bộ tích lũy.
• giảm sự cố. từ đến

Với ý nghĩ đó, chúng ta có được hàm lặp sau

Mặc dù phủ định của là

thay vì , chúng tôi sử dụng cái sau vì is restricted to natural numbers.

4. Phương pháp chuyển đổi chung

Chúng tôi đã thấy cách chúng tôi có thể biến các hàm đệ quy đuôi thành tính lặp. Tuy nhiên, có những loại đệ quy khác. Ví dụ: một hàm đệ quy đầu đặt lệnh gọi đệ quy ở đầu phần thân của nó thay vì phần cuối của nó. Các loại khác bao quanh cuộc gọi với các khối mã để xử lý trước đầu vào và xử lý sau giá trị trả về của cuộc gọi. Hơn nữa, một hàm đệ quy có thể thực hiện bất kỳ số lần gọi đệ quy nào trong phần thân của nó, không chỉ một

Thật may mắn cho chúng ta, có một cách tổng quát để biến bất kỳ phép đệ quy nào thành một thuật toán lặp. Phương pháp này dựa trên quan sát rằng các hàm đệ quy được thực thi bằng cách đẩy các khung lên ngăn xếp cuộc gọi và bật chúng ra khỏi ngăn xếp đó. Do đó, nếu chúng ta mô phỏng ngăn xếp của mình, chúng ta có thể thực thi lặp đi lặp lại bất kỳ chức năng đệ quy nào trong một vòng lặp chính. Tuy nhiên, mã kết quả có thể không đẹp. Đó là lý do tại sao trước tiên chúng ta thường cố gắng làm cho hàm của mình có tính đệ quy đuôi. Nếu chúng tôi thành công, chúng tôi có thể nhận được mã khá dễ đọc bằng phương pháp từ Phần 3. Nếu không, chúng tôi sử dụng phương pháp chuyển đổi chung. Vì vậy, trước tiên hãy kiểm tra dạng tổng quát của các hàm đệ quy

4. 1. Hình thức tổng quát của đệ quy

Một  hàm đệ quy có thể thực hiện số lượng lệnh gọi đệ quy tùy ý trong phần thân của nó

________số 8

Mã giả này bao gồm các trường hợp trong đó số lần gọi đệ quy [

] là hằng số hoặc có giới hạn, như trong duyệt cây nhị phân [ . Ngoài ra, một giải pháp trường hợp cơ bản có thể không đổi hoặc phụ thuộc vào depends on the problem’s size. Also, a base-case solution can be constant or depend on vượt qua bài kiểm tra . Hơn nữa, mỗi khối mã không đệ quy có thể trống hoặc một lệnh duy nhất hoặc bao gồm các cuộc gọi đến các chương trình con khác. Mục đích của là chuẩn bị dữ liệu cho lệnh gọi đệ quy thứ . Cuối cùng, việc kết hợp các giải pháp con đệ quy cũng nên được hiểu một cách tổng quát. nó có thể đơn giản như hoặc phức tạp hơn.

4. 2. Đồ thị thực hiện

Mỗi cuộc gọi đến

sẽ tạo một khung. Đó là cấu trúc chứa các tham số đã truyền, biến cục bộ và trình giữ chỗ cho giá trị trả về. Nếu chúng tôi trực quan hóa các khung và theo dõi các cuộc gọi, chúng tôi sẽ thấy rằng hàm đệ quy xác định một biểu đồ có hướng và ẩn. Các nút của nó là các khung, một số trong đó không có cạnh nhìn ra ngoài. Chúng đại diện cho các trường hợp cơ bản của đệ quy của chúng tôi. Những người khác có các cạnh bên trong và bên ngoài. họ mô hình hóa các cuộc gọi giữa các trường hợp cơ sở và cuộc gọi đầu tiên. Hãy xem một phần của biểu đồ cho các số Fibonacci.

Cạnh có hướng từ

đến tương ứng với lệnh gọi đệ quy trong làm cho the active frame. Accordingly, executing a recursive function is the same as traversing the frame graph in a structured way. We cross over each edge hai lần. lần đầu tiên khi thực hiện lệnh gọi tạo khung của và lần thứ hai khi trả về giá trị của lệnh gọi cho . .

4. 3. Thực thi dưới dạng Depth-First Traversal

Vì vậy, chúng tôi bắt đầu trong nút khung của trình gọi ban đầu và thực thi khối mã không đệ quy trước lệnh gọi đệ quy đầu tiên. Tại thời điểm đó, chúng tôi đã tạo một nút con đại diện cho khung của cuộc gọi. Cách thức hoạt động của đệ quy ngụ ý rằng chúng ta nên di chuyển đến nút con và thăm các nút con của nó theo cách tương tự. Sau đó, chúng tôi thu thập giá trị trả về của khung, quay lại nút bắt đầu và chuyển sang nút con tiếp theo. Mục đích là truy cập tất cả các nút và quay lại khung ban đầu, tại thời điểm đó, chúng tôi kết hợp giá trị trả về của con và đưa ra giải pháp

Nhưng, làm thế nào để đồ thị này giúp chúng ta biến một hàm đệ quy thành một hàm lặp? . Phiên bản lặp của truyền tải theo chiều sâu sử dụng ngăn xếp để lưu trữ các nút được đánh dấu để truy cập. Nếu chúng ta triển khai các nút và cạnh theo cách tương ứng với các thành phần của hàm, chúng ta sẽ nhận được phiên bản lặp lại của nó. Ở đó ngăn chứa các nút đóng vai trò là ngăn gọi của một CPU

4. 4. Chi tiết triển khai

Biểu đồ thực thi là ẩn. Điều đó có nghĩa là chúng tôi tạo nó một cách nhanh chóng khi chúng tôi thực thi các khối mã không đệ quy và thực hiện các cuộc gọi đệ quy. Để thực hiện đúng, chúng ta nên triển khai các khung và cạnh theo cấu trúc của hàm đệ quy mà chúng ta đang chuyển đổi

Vì vậy,

sẽ trả về cạnh được liên kết với NRCB không được thực thi đầu tiên và lệnh gọi đệ quy. Nó cũng phải chứa con trỏ tới khung con mà chúng ta có được bằng cách đi theo cạnh. Vì vậy, chức năng này sẽ chia bài toán thành các bài toán con và tạo các khung con. A-frame phải là một cấu trúc dữ liệu có khả năng chứa các biến cục bộ và vấn đề phụ của nó. Nó cũng có thể chuyển giá trị trả về của nó cho cha của nó.

chịu trách nhiệm xác định giá trị. Nếu khung là nút trường hợp cơ sở, thì hàm sẽ trả về giải pháp trường hợp cơ sở thích hợp. Nếu không, thì hàm sẽ kết hợp các giá trị trả về mà khung nhận được từ các phần tử con của nó

4. 5. Ví dụ

Hãy chuyển đổi đệ quy này thành phép lặp

# Using for loopdef for_loop2[n]:
    x = n
    for i in range[1,n,1]:
        x = x*[n-i]
    return x
x = for_loop2[26]
print[x]
# Using Recursiondef recursive2[n]:
    ### base case ###
    if n 

1

Chúng tôi sẽ cập nhật bộ đếm và thực thi NRCB tương ứng trong hàm trả về khung con tiếp theo

2

Chúng tôi kiểm tra xem khung có cạnh ra ngoài chưa được thăm hay không bằng cách xác minh rằng đó không phải là khung trường hợp cơ sở và kiểm tra xem khung có. nrcb_count < 2. Toàn bộ mã sẽ trông như thế này

3

4. 7. Khả năng đọc và ngữ nghĩa

Cung cấp thuật toán duyệt theo chiều sâu chung với các triển khai cụ thể theo đệ quy của các khung, cạnh và các hàm liên quan, chúng tôi nhận được một biến thể lặp của hàm đệ quy mà chúng tôi muốn chuyển đổi. Tuy nhiên, mã lặp kết quả sẽ không dễ đọc và dễ hiểu như mã đệ quy ban đầu

Tuy nhiên, chúng tôi giữ lại một số ngữ nghĩa trong biểu đồ. Bởi vì nó thể hiện cấu trúc đệ quy của vấn đề ban đầu, chúng ta vẫn có thể giải thích nó. Một nút có con của nó đại diện cho phần thân của đệ quy, trong khi trường hợp cơ sở có thể được nhận ra trong các nút không có con

4. 8. Tối ưu hóa và các loại đệ quy

Cuối cùng, chúng tôi lưu ý rằng chúng tôi có thể truy cập một số nút trong biểu đồ nhiều lần. Đó là trường hợp nếu các bài toán con chồng lên nhau, như trường hợp của các số Fibonacci. Cả

và đều phụ thuộc vào nên sẽ được truy cập hai lần. Nhiều lượt truy cập vào cùng một nút dẫn đến tính toán lặp lại và tăng độ phức tạp. Chúng ta có thể giải quyết vấn đề này bằng cách ghi nhớ các giá trị trả về. Bất cứ khi nào chúng tôi tính toán giá trị mà một nút sẽ trả về, chúng tôi sẽ lưu trữ giá trị đó trong nút. Nếu sau đó chúng tôi truy cập cùng một nút, chúng tôi sẽ sử dụng lại giải pháp đã tìm thấy và tránh đánh giá lặp lại. Kỹ thuật này được gọi là ghi nhớ. Một số tác giả coi nó là công cụ của quy hoạch động.

Hơn nữa, hình dạng của biểu đồ thực thi cho thấy sự khác biệt giữa các loại đệ quy khác nhau. Đồ thị của hàm đệ quy chỉ thực hiện một lệnh gọi đệ quy trong phần thân của nó là một đường dẫn. Nếu nó thực hiện hai lệnh gọi và các bài toán con không trùng nhau, biểu đồ kết quả sẽ là một cây nhị phân. Đệ quy đuôi là cụ thể vì giai đoạn tái tổ hợp của nó là một hoạt động nhận dạng. mỗi nút chỉ chuyển tiếp giá trị trả về của con. Đó là lý do tại sao chúng ta không cần ngăn xếp để lặp đi lặp lại

5. Phần kết luận

Trong bài viết này, chúng ta đã nói về việc chuyển đổi đệ quy thành phép lặp. Chúng tôi đã trình bày một cách chung để chuyển đổi bất kỳ hàm đệ quy nào thành hàm lặp. Ngoài ra, chúng tôi đã chỉ ra một phương pháp chỉ đệ quy đuôi. Mặc dù chuyển đổi có thể mang lại cho chúng tôi hiệu suất, mã sẽ mất khả năng đọc theo cách này

tác giả dưới cùng

Nếu bạn có một vài năm kinh nghiệm trong Khoa học máy tính hoặc nghiên cứu và bạn muốn chia sẻ kinh nghiệm đó với cộng đồng, hãy xem Nguyên tắc đóng góp của chúng tôi

Làm cách nào để chuyển đổi vòng lặp thành đệ quy?

Làm cách nào để chuyển đổi thuật toán đệ quy thành thuật toán không đệ quy?

đệ quy đuôi với ví dụ là gì?

Đệ quy và ví dụ là gì?