Cách trả về danh sách trong hàm đệ quy python
“Trong tất cả các ý tưởng tôi đã giới thiệu cho trẻ em, đệ quy nổi bật là một ý tưởng đặc biệt có khả năng gợi lên phản ứng hào hứng. ” Show — Seymour Papert, Tâm bão Các vấn đề (trong cuộc sống và cả trong khoa học máy tính) thường có vẻ lớn và đáng sợ. Nhưng nếu chúng ta tiếp tục sứt mẻ chúng, thường thì chúng ta có thể chia nhỏ chúng thành những phần nhỏ đủ tầm thường để giải quyết. Đây là bản chất của tư duy đệ quy, và mục đích của tôi trong bài viết này là cung cấp cho bạn, độc giả thân mến của tôi, các công cụ khái niệm cần thiết để tiếp cận các vấn đề từ quan điểm đệ quy này Cùng nhau, chúng ta sẽ học cách làm việc với đệ quy trong các chương trình Python của mình bằng cách nắm vững các khái niệm như hàm đệ quy và cấu trúc dữ liệu đệ quy. Chúng ta cũng sẽ nói về việc duy trì trạng thái trong quá trình đệ quy và tránh tính toán lại bằng cách lưu trữ kết quả. Đây sẽ là rất nhiều niềm vui. Trở lên và trở lên Kính gửi ông già Noel Pythonic…Tôi nhận ra rằng với tư cách là các Pythonistas, tất cả chúng ta đều đồng ý với người lớn ở đây, nhưng trẻ em dường như tìm hiểu vẻ đẹp của đệ quy tốt hơn. Vì vậy, chúng ta đừng làm người lớn ở đây một lúc và nói về cách chúng ta có thể sử dụng đệ quy để giúp ông già Noel Bạn đã bao giờ tự hỏi làm thế nào quà Giáng sinh được gửi? . Anh ấy đi đến một ngôi nhà, bỏ quà, ăn bánh quy và sữa, rồi chuyển sang ngôi nhà tiếp theo trong danh sách. Vì thuật toán phân phối quà này dựa trên cấu trúc vòng lặp rõ ràng nên nó được gọi là thuật toán lặp Thuật toán phân phối quà tặng lặp đi lặp lại được triển khai trong Python
>>>
Nhưng tôi cảm thấy cho ông già Noel. Ở tuổi của anh ấy, anh ấy không nên tự mình đi giao tất cả những món quà. Tôi đề xuất một thuật toán mà anh ấy có thể phân chia công việc giao quà cho các yêu tinh của mình
Đây là cấu trúc điển hình của một thuật toán đệ quy. Nếu vấn đề hiện tại đại diện cho một trường hợp đơn giản, hãy giải quyết nó. Nếu không, hãy chia nó thành các bài toán con và áp dụng chiến lược tương tự cho chúng Thuật toán phân phối hiện tại đệ quy được triển khai trong Python
>>> Loại bỏ các quảng cáoHàm đệ quy trong PythonBây giờ chúng ta đã có một số trực giác về đệ quy, hãy giới thiệu định nghĩa chính thức của hàm đệ quy. Hàm đệ quy là một hàm được định nghĩa theo chính nó thông qua các biểu thức tự tham chiếu Điều này có nghĩa là hàm sẽ tiếp tục gọi chính nó và lặp lại hành vi của nó cho đến khi một số điều kiện được đáp ứng để trả về kết quả. Tất cả các hàm đệ quy chia sẻ một cấu trúc chung bao gồm hai phần. trường hợp cơ sở và trường hợp đệ quy Để chứng minh cấu trúc này, hãy viết một hàm đệ quy để tính toán 8
Ở đây, 9 là trường hợp cơ sở của chúng tôi và nó bằng với 0Hàm đệ quy để tính toán 8 được triển khai trong Python 2>>> 3Phía sau hậu trường, mỗi lệnh gọi đệ quy sẽ thêm một khung ngăn xếp (chứa ngữ cảnh thực thi của nó) vào ngăn xếp lệnh gọi cho đến khi chúng ta đạt đến trường hợp cơ sở. Sau đó, ngăn xếp bắt đầu thư giãn khi mỗi cuộc gọi trả về kết quả của nó Duy trì trạng tháiKhi xử lý các hàm đệ quy, hãy nhớ rằng mỗi lệnh gọi đệ quy có ngữ cảnh thực thi riêng, do đó, để duy trì trạng thái trong suốt quá trình đệ quy, bạn phải:
Một cuộc biểu tình sẽ làm cho mọi thứ rõ ràng hơn. Hãy tính toán 2 bằng cách sử dụng đệ quy. Trạng thái mà chúng tôi phải duy trì là (số hiện tại chúng tôi đang thêm, tổng tích lũy cho đến bây giờ)Đây là cách bạn làm điều đó bằng cách xâu chuỗi nó qua mỗi lời gọi đệ quy (i. e. chuyển trạng thái hiện tại được cập nhật cho từng lệnh gọi đệ quy dưới dạng đối số) 5>>> 6Đây là cách bạn duy trì trạng thái bằng cách giữ nó trong phạm vi toàn cầu 0>>> 1Tôi thích phân luồng trạng thái thông qua từng lệnh gọi đệ quy hơn vì tôi thấy trạng thái có thể thay đổi toàn cầu là xấu, nhưng đó là một cuộc thảo luận sau Loại bỏ các quảng cáoCấu trúc dữ liệu đệ quy trong PythonMột cấu trúc dữ liệu là đệ quy nếu nó có thể được định nghĩa theo một phiên bản nhỏ hơn của chính nó. Danh sách là một ví dụ về cấu trúc dữ liệu đệ quy. Hãy để tôi chứng minh. Giả sử rằng bạn chỉ có một danh sách trống theo ý của bạn và thao tác duy nhất bạn có thể thực hiện trên danh sách đó là: 2Sử dụng danh sách trống và thao tác 3, bạn có thể tạo bất kỳ danh sách nào. Ví dụ: hãy tạo 4 3 4
Danh sách không phải là cấu trúc dữ liệu đệ quy duy nhất. Các ví dụ khác bao gồm bộ, cây, từ điển, v.v. Cấu trúc dữ liệu đệ quy và hàm đệ quy đi cùng nhau như bánh mì và bơ. Cấu trúc của hàm đệ quy thường có thể được mô hình hóa sau định nghĩa của cấu trúc dữ liệu đệ quy mà nó lấy làm đầu vào. Hãy để tôi chứng minh điều này bằng cách tính tổng của tất cả các phần tử của danh sách theo cách đệ quy 6>>> 7Đệ quy ngây thơ là ngây thơCác số Fibonacci ban đầu được xác định bởi nhà toán học người Ý Fibonacci vào thế kỷ thứ mười ba để mô hình hóa sự phát triển của quần thể thỏ. Fibonacci phỏng đoán rằng số cặp thỏ được sinh ra trong một năm nhất định bằng với số cặp thỏ được sinh ra trong mỗi hai năm trước đó, bắt đầu từ một cặp thỏ trong năm đầu tiên Để đếm số thỏ được sinh ra vào năm thứ n, ông đã định nghĩa hệ thức truy hồi 8Các trường hợp cơ bản là 9Hãy viết một hàm đệ quy để tính số Fibonacci thứ n 0>>> 1Ngây thơ theo định nghĩa đệ quy của số Fibonacci thứ n là không hiệu quả. Như bạn có thể thấy từ đầu ra ở trên, chúng tôi đang tính toán lại các giá trị một cách không cần thiết. Hãy cố gắng cải thiện 8 bằng cách lưu trữ kết quả của mỗi phép tính Fibonacci Fk 2>>> 3 9 là một trình trang trí lưu trữ các kết quả. Vì vậy, chúng tôi tránh tính toán lại bằng cách kiểm tra rõ ràng giá trị trước khi thử tính toán nó. Một điều cần lưu ý về 9 là vì nó sử dụng từ điển để lưu kết quả vào bộ nhớ cache, nên các đối số vị trí và từ khóa (đóng vai trò là khóa trong từ điển đó) của hàm phải có thể băm đượcLoại bỏ các quảng cáochi tiết khó chịuPython không hỗ trợ loại bỏ cuộc gọi đuôi. Do đó, bạn có thể gây tràn ngăn xếp nếu cuối cùng bạn sử dụng nhiều khung ngăn xếp hơn độ sâu ngăn xếp lệnh gọi mặc định >>> 4Hãy ghi nhớ giới hạn này nếu bạn có một chương trình yêu cầu đệ quy sâu Ngoài ra, cấu trúc dữ liệu có thể thay đổi của Python không hỗ trợ chia sẻ cấu trúc, vì vậy, việc coi chúng như cấu trúc dữ liệu bất biến sẽ ảnh hưởng tiêu cực đến không gian và hiệu quả GC (thu gom rác) của bạn vì cuối cùng bạn sẽ sao chép rất nhiều đối tượng có thể thay đổi một cách không cần thiết. Ví dụ: tôi đã sử dụng mẫu này để phân tách danh sách và lặp lại chúng >>> 5Tôi đã làm điều đó để đơn giản hóa mọi thứ vì mục đích rõ ràng. Hãy nhớ rằng đuôi đang được tạo bằng cách sao chép. Làm điều đó một cách đệ quy trên các danh sách lớn có thể ảnh hưởng tiêu cực đến không gian và hiệu quả GC của bạn VâyTôi đã từng được yêu cầu giải thích đệ quy trong một cuộc phỏng vấn. Tôi lấy một tờ giấy và viết 1 trên cả hai mặt. Người phỏng vấn không hiểu trò đùa, nhưng bây giờ bạn đã đọc bài viết này, hy vọng bạn hiểu 🙂 Happy PythoningNgười giới thiệu
Đánh dấu là đã hoàn thành Xem ngay Hướng dẫn này có một khóa học video liên quan do nhóm Real Python tạo. Xem nó cùng với hướng dẫn bằng văn bản để hiểu sâu hơn. Tư duy đệ quy trong Python 🐍 Thủ thuật Python 💌 Nhận một Thủ thuật Python ngắn và hấp dẫn được gửi đến hộp thư đến của bạn vài ngày một lần. Không có thư rác bao giờ. Hủy đăng ký bất cứ lúc nào. Được quản lý bởi nhóm Real Python Gửi cho tôi thủ thuật Python » Giới thiệu về Abhirag Awasthi Lập trình viên/Nhạc sĩ, không ngừng cố gắng tạo ra thứ gì đó đáng giá, cải thiện kỹ năng của mình trong quá trình này » Tìm hiểu thêm về AbhiragMỗi hướng dẫn tại Real Python được tạo bởi một nhóm các nhà phát triển để nó đáp ứng các tiêu chuẩn chất lượng cao của chúng tôi. Các thành viên trong nhóm đã làm việc trong hướng dẫn này là Aldren Đan Joanna Bậc thầy Kỹ năng Python trong thế giới thực Với quyền truy cập không giới hạn vào Python thực Tham gia với chúng tôi và có quyền truy cập vào hàng nghìn hướng dẫn, khóa học video thực hành và cộng đồng các Pythonistas chuyên gia Nâng cao kỹ năng Python của bạn » Bậc thầy Kỹ năng Python trong thế giới thực Tham gia với chúng tôi và có quyền truy cập vào hàng ngàn hướng dẫn, khóa học video thực hành và cộng đồng Pythonistas chuyên gia Nâng cao kỹ năng Python của bạn » Bạn nghĩ sao? Đánh giá bài viết này Tweet Chia sẻ Chia sẻ EmailBài học số 1 hoặc điều yêu thích mà bạn đã học được là gì? Mẹo bình luận. Những nhận xét hữu ích nhất là những nhận xét được viết với mục đích học hỏi hoặc giúp đỡ các sinh viên khác. Nhận các mẹo để đặt câu hỏi hay và nhận câu trả lời cho các câu hỏi phổ biến trong cổng thông tin hỗ trợ của chúng tôi Phương pháp đệ quy có phải trả về một cái gì đó không?Tất cả các hàm - có đệ quy hay không - có một hoặc nhiều hàm trả về . Trả về có thể có hoặc không bao gồm giá trị. Bạn là người quyết định khi viết hàm. Tất cả các câu lệnh trả về bằng văn bản rõ ràng phải trả về đúng loại.
Python có đệ quy đuôi không?Không có tối ưu hóa đệ quy đuôi tích hợp sẵn trong Python . Tuy nhiên, chúng ta có thể "xây dựng lại" chức năng thông qua Cây cú pháp trừu tượng (AST), loại bỏ đệ quy ở đó và thay thế nó bằng một vòng lặp. |