Không đệ quy trong python là gì?

Đối với sinh viên nâng cao hơn, hãy thảo luận về chi phí hệ thống dưới dạng ngăn xếp cần thiết. Ngăn xếp cuộc gọi là cấu trúc dữ liệu được chương trình sử dụng để lưu trữ thông tin về các chương trình con đang hoạt động trong chương trình. Ngăn xếp được sử dụng để chương trình có thể theo dõi vị trí chương trình con sẽ trả lại quyền điều khiển sau khi chương trình kết thúc thực thi

Tôi đã phát hiện ra kỹ thuật này cách đây không lâu khi tình cờ xem một trong những video của Tsoding (kênh Tsoding). https. //www. youtube. com/watch?v=QkuNmL7tz08&t=4756s. Trong video này, Zozen hướng dẫn cách triển khai. Đảo ngược cây nhị phân trong Rust. Anh ấy phát triển phương pháp tổng quát này để chuyển đổi phương án đệ quy sang không đệ quy mà tôi đang đề cập đến. Tôi sẽ đưa ra giải pháp bằng Python. (Để thuận tiện cho tôi)

ý tưởng 1. Ngăn xếp CUỘC GỌI

Trong hầu hết các ngôn ngữ lập trình, bất cứ khi nào một hàm được gọi, tất cả dữ liệu mà hàm đó yêu cầu sẽ được đóng gói cùng nhau và được "đẩy" lên một thứ gọi là - Ngăn xếp CALL (thêm về điều này tại đây. ). Các lệnh gọi hàm đệ quy dựa vào ngăn xếp CALL này để đảm bảo tính loại trừ lẫn nhau giữa các lệnh gọi riêng biệt

ý tưởng 2. Ngăn xếp TRẢ LẠI

Hàm trả về các giá trị cho người gọi bằng cách sử dụng một ngăn xếp khác gọi là ngăn xếp RETURN. Bất cứ khi nào việc thực thi chức năng hoàn tất, nó sẽ “đẩy” giá trị được trả về vào RETURN Stack

Vì hầu hết các ngôn ngữ lập trình đều có giới hạn về kích thước của các ngăn xếp này, nên các giải pháp đệ quy thường gặp phải lỗi “Tràn ngăn xếp” khi các lệnh gọi đệ quy quá sâu

Chúng tôi có thể khắc phục điều này bằng cách đơn giản là mô phỏng quy trình này bằng cách phân bổ các ngăn xếp của riêng chúng tôi vào bộ lưu trữ HEAP. Sẽ dễ dàng hơn để hiển thị điều này bằng các ví dụ-

ví dụ 1. Tháp Hà Nội

Đầu tiên tôi sẽ triển khai tháp hà nội dưới dạng thuật toán đệ quy-

move_disc chỉ là một hàm trợ giúp để định dạng hướng dẫn di chuyển đĩa từ đỉnh tháp frm sang tháp to dưới dạng chuỗi

Nếu bạn thấy việc triển khai đệ quy, bạn có thể quan sát các điểm sau-

1. Mọi thuật toán đệ quy đều có trường hợp cơ sở (trong trường hợp này n = 0)
2. Mỗi thuật toán đệ quy tự thực hiện một lệnh gọi đệ quy với kích thước đầu vào thu nhỏ lại (Ở đây “Thu hẹp” không rõ ràng - nó sẽ tiếp cận trường hợp cơ sở theo một cách nào đó)
3. Với các lệnh gọi đệ quy tới chính nó, nó cũng thực hiện điều gì đó với đầu vào của hàm (trong trường hợp này là in move_disc(from, to))

Chúng ta có thể khái quát hóa các hoạt động này là CALL cho các cuộc gọi đệ quy và HANDLE để thực hiện mọi việc với đầu vào

Sau đây là cấu trúc chung của giải pháp thay thế không đệ quy-

1. Chúng tôi định nghĩa hai hằng số CALL là 0 và HANDLE là 1. (chúng có thể là hai thứ bất kỳ, chỉ cần khác nhau, chúng ta có thể chọn Đúng và Sai chẳng hạn)
2. Sau đó, chúng tôi tạo một call_stack với đầu vào ban đầu là tagged với giá trị CALL
3. Sau đó, chúng tôi bật các yếu tố từ call_stack và tùy thuộc vào frm1, chúng tôi xử lý mọi thứ theo cách khác. Một cho CALL và một cho HANDLE
4. Trong phần CALL, chúng tôi nối thêm CALL và HANDLE tùy thuộc vào thuật toán. CALL cho lệnh gọi đệ quy và HANDLE nếu phải làm gì đó với dữ liệu (Lưu ý rằng phần HANDLE chưa được đánh giá, chúng tôi sử dụng hành động này từ call_stack đến to1). Ngoài ra, chúng tôi nối thêm hành động CALL hoặc HANDLE theo thứ tự ngược lại của giải pháp đệ quy. (Suy ngẫm về lý do tại sao chúng ta làm điều này)
5. Sau đó, Cuối cùng trong phầnHANDLE, chúng tôi thực hiện các thao tác với dữ liệu

Giải pháp không đệ quy cho tháp hà nội-

Thuật toán trên không phụ thuộc vào ngăn xếp cuộc gọi của Ngôn ngữ lập trình, do đó về mặt lý thuyết là không bị chặn và không có lỗi Stack Overflow

ví dụ 2. Fibonacci

Cho đến nay, chúng tôi chỉ in dữ liệu ra bàn điều khiển, nếu chúng tôi muốn mô phỏng các giá trị trả về từ các hàm thì sao?. Chúng tôi sử dụng to5

Vì vậy, cấu trúc tổng quát thay đổi một chút-

1. Chúng tôi khởi tạo to5 là to7 trống
2. Chúng tôi thêm dữ liệu vào return_stack trong phần CALL, thường là cho trường hợp to9
3. Chúng tôi sử dụng dữ liệu từ to5 trong phần HANDLE và sử dụng dữ liệu đó để tính toán thứ gì đó và đẩy thứ gì đó sang to5 để phần HANDLE khác sử dụng
4. Cuối cùng, chúng tôi chỉ trả lại phần tử trên cùng từ to5

Hãy sử dụng điều này để giải quyết vấn đề về fibonacci

Thuật toán Fibonacci đệ quy-

Thuật toán Fibonacci không đệ quy-

Nó khá là nhiều. Hãy giải quyết các vấn đề khác bằng cách sử dụng kỹ thuật này-

ví dụ 3. Đảo ngược cây nhị phân

Các loại để lưu trữ dữ liệu cây nhị phân-

Thuật toán đệ quy-

Thay thế không đệ quy-

Ví dụ 4. Thứ tự đi ngang của cây

Các loại cho dữ liệu Cây nhị phân-

Thuật toán đệ quy-

Thay thế không đệ quy-

Có rất nhiều ví dụ (bao gồm cả ở trên) ở đây

Đúng là giải pháp thay thế không đệ quy dài hơn, nhưng nó rất dễ tạo ra khi bạn có giải pháp đệ quy

Điều gì có nghĩa là không đệ quy?

Thuật toán không đệ quy là gì?

Sự khác biệt giữa đệ quy và không đệ quy là gì?

Đệ quy trong Python là gì?