Trong hướng dẫn này, bạn sẽ học cách tạo một hàm đệ quy (một hàm tự gọi). Show
Nội phân Chính showShow
Đệ quy là gì?Đệ quy là quá trình xác định một cái gì đó theo chính nó. Một ví dụ thế giới vật lý sẽ là đặt hai gương song song đối diện nhau. Bất kỳ đối tượng ở giữa chúng sẽ được phản ánh đệ quy. Chức năng đệ quy PythonVí dụ về hàm đệ quy Ưu điểm của đệ quy Nhược điểm của đệ quyĐệ quy là gì? Tại sao sử dụng đệ quy? Ví dụ về hàm đệ quy
Ưu điểm của đệ quy The factorial of 3 is 6 Nhược điểm của đệ quy Đệ quy là gì? Tại sao sử dụng đệ quy? factorial(3) # 1st call with 3 3 * factorial(2) # 2nd call with 2 3 * 2 * factorial(1) # 3rd call with 1 3 * 2 * 1 # return from 3rd call as number=1 3 * 2 # return from 2nd call 6 # return from 1st call Đệ quy trong Python Bắt đầu: Đếm xuống 0Tính toán giai thừa Xác định chức năng giai thừa Python So sánh tốc độ của việc triển khai giai thừa Đi qua một danh sách lồng nhau Đi qua một danh sách lồng nhau một cách đệ quyƯu điểm của đệ quy Traceback (most recent call last): File "<string>", line 3, in <module> File "<string>", line 2, in a File "<string>", line 2, in a File "<string>", line 2, in a [Previous line repeated 996 more times] RecursionError: maximum recursion depth exceeded Ưu điểm của đệ quy
Nhược điểm của đệ quy
Bắt đầu: Đếm xuống 0recursive, and the technique of employing a recursive function is called recursion. Tính toán giai thừa
Đệ quy là quá trình xác định một cái gì đó theo chính nó. Một ví dụ thế giới vật lý sẽ là đặt hai gương song song đối diện nhau. Bất kỳ đối tượng ở giữa chúng sẽ được phản ánh đệ quy.
Factorial của một số là sản phẩm của tất cả các số nguyên từ 1 đến số đó. Ví dụ: giai thừa của 6 (ký hiệu là 6!) Là 1*2*3*4*5*6 = 720. Đệ quy là gì?Đầu rarecursion comes from the Latin word recurrere, meaning to run or hasten back, return, revert, or recur. Here are some online definitions of recursion:
Một định nghĩa đệ quy là một trong đó thuật ngữ xác định xuất hiện trong chính định nghĩa. Các tình huống tự giới thiệu thường mọc lên trong cuộc sống thực, ngay cả khi chúng không thể nhận ra ngay lập tức như vậy. Ví dụ, giả sử bạn muốn mô tả tập hợp những người tạo nên tổ tiên của bạn. Bạn có thể mô tả chúng theo cách này:recursive definition is one in which the defined term appears in the definition itself. Self-referential situations often crop up in real life, even if they aren’t immediately recognizable as such. For example, suppose you wanted to describe the set of people that make up your ancestors. You could describe them this way: Lưu ý cách khái niệm đang được xác định, tổ tiên, thể hiện theo định nghĩa riêng của nó. Đây là một định nghĩa đệ quy.ancestors, shows up in its own definition. This is a recursive definition. Trong lập trình, đệ quy có một ý nghĩa rất chính xác. Nó đề cập đến một kỹ thuật mã hóa trong đó một hàm tự gọi. Tại sao sử dụng đệ quy?Hầu hết các vấn đề lập trình là có thể giải quyết mà không cần đệ quy. Vì vậy, nói đúng ra, đệ quy thường không cần thiết. Tuy nhiên, một số tình huống đặc biệt cho vay đối với một định nghĩa tự giới thiệu, ví dụ, định nghĩa của tổ tiên được hiển thị ở trên. Nếu bạn đang nghĩ ra một thuật toán để xử lý một trường hợp như vậy theo chương trình, một giải pháp đệ quy có thể sẽ sạch hơn và súc tích hơn.self-referential definition—for example, the definition of ancestors shown above. If you were devising an algorithm to handle such a case programmatically, a recursive solution would likely be cleaner and more concise. Truyền tải các cấu trúc dữ liệu giống như cây là một ví dụ tốt khác. Bởi vì đây là những cấu trúc lồng nhau, chúng dễ dàng phù hợp với một định nghĩa đệ quy. Một thuật toán không nhận được để đi qua một cấu trúc lồng nhau có khả năng là một chút lộn xộn, trong khi một giải pháp đệ quy sẽ tương đối thanh lịch. Một ví dụ về điều này xuất hiện sau này trong hướng dẫn này. Mặt khác, đệ quy là không phải cho mọi tình huống. Dưới đây là một số yếu tố khác để xem xét:
Thông thường, khả năng đọc của mã sẽ là yếu tố quyết định lớn nhất. Nhưng nó phụ thuộc vào hoàn cảnh. Các ví dụ được trình bày dưới đây sẽ giúp bạn cảm nhận khi nào bạn nên chọn đệ quy. Đệ quy trong PythonKhi bạn gọi một hàm trong Python, trình thông dịch sẽ tạo một không gian tên cục bộ mới để các tên được xác định trong hàm đó don don va chạm với các tên giống hệt nhau được xác định ở nơi khác. Một chức năng có thể gọi một chức năng khác và ngay cả khi cả hai đều xác định các đối tượng có cùng tên, tất cả đều hoạt động tốt vì các đối tượng đó tồn tại trong các không gian tên riêng biệt.namespaces. Điều tương tự sẽ đúng nếu nhiều phiên bản của cùng một hàm đang chạy đồng thời. Ví dụ, hãy xem xét định nghĩa sau:
Khi 9 thực hiện lần đầu tiên, Python tạo ra một không gian tên và gán Traceback (most recent call last): File "<string>", line 3, in <module> File "<string>", line 2, in a File "<string>", line 2, in a File "<string>", line 2, in a [Previous line repeated 996 more times] RecursionError: maximum recursion depth exceeded0 giá trị Traceback (most recent call last): File "<string>", line 3, in <module> File "<string>", line 2, in a File "<string>", line 2, in a File "<string>", line 2, in a [Previous line repeated 996 more times] RecursionError: maximum recursion depth exceeded1 trong không gian tên đó. Sau đó 9 tự gọi mình là đệ quy. Lần thứ hai 9 chạy, trình thông dịch tạo không gian tên thứ hai và gán Traceback (most recent call last): File "<string>", line 3, in <module> File "<string>", line 2, in a File "<string>", line 2, in a File "<string>", line 2, in a [Previous line repeated 996 more times] RecursionError: maximum recursion depth exceeded1 cho Traceback (most recent call last): File "<string>", line 3, in <module> File "<string>", line 2, in a File "<string>", line 2, in a File "<string>", line 2, in a [Previous line repeated 996 more times] RecursionError: maximum recursion depth exceeded0 ở đó. Hai trường hợp này của tên Traceback (most recent call last): File "<string>", line 3, in <module> File "<string>", line 2, in a File "<string>", line 2, in a File "<string>", line 2, in a [Previous line repeated 996 more times] RecursionError: maximum recursion depth exceeded0 khác biệt với nhau và có thể cùng tồn tại mà không cần xung đột vì chúng nằm trong các không gian tên riêng biệt. Thật không may, chạy 9 vì nó tạo ra một kết quả ít truyền cảm hứng hơn, như các dấu vết sau đây cho thấy:>>>
Như đã viết, 9 về lý thuyết sẽ diễn ra mãi mãi, tự gọi mình là mà không có bất kỳ cuộc gọi nào trở lại. Trong thực tế, tất nhiên, không có gì thực sự là mãi mãi. Máy tính của bạn chỉ có quá nhiều bộ nhớ và cuối cùng nó sẽ hết.Python không cho phép điều đó xảy ra. Trình thông dịch giới hạn số lần tối đa một hàm có thể gọi chính nó theo cách đệ quy và khi nó đạt đến giới hạn đó, nó sẽ tăng ngoại lệ 8, như bạn thấy ở trên.Có rất nhiều việc sử dụng cho một chức năng để tự gọi một cách bừa bãi một cách đệ quy mà không cần kết thúc. Nó gợi nhớ đến những hướng dẫn mà đôi khi bạn tìm thấy trên các chai dầu gội đầu: Lather Lather, Rửa sạch, lặp lại. Nếu bạn phải làm theo những hướng dẫn này theo nghĩa đen, bạn sẽ gội đầu mãi mãi! Lỗ hổng logic này rõ ràng đã xảy ra với một số nhà sản xuất dầu gội đầu, bởi vì một số chai dầu gội thay vào đó nói là Lather, rửa sạch, lặp lại khi cần thiết. Cung cấp một điều kiện chấm dứt cho các hướng dẫn. Có lẽ, cuối cùng bạn sẽ cảm thấy mái tóc của mình đủ sạch để xem xét các lần lặp lại bổ sung không cần thiết. Dầu gội sau đó có thể dừng lại. Tương tự, một chức năng tự gọi mình là đệ quy phải có kế hoạch dừng lại. Các chức năng đệ quy thường theo mẫu này:
Bây giờ bạn đã sẵn sàng để xem cách này hoạt động với một số ví dụ. Bắt đầu: Đếm xuống 0Ví dụ đầu tiên là một hàm gọi là 0, lấy số dương làm đối số và in các số từ đối số được chỉ định xuống bằng không:>>>
Lưu ý cách 0 phù hợp với mô hình cho một thuật toán đệ quy được mô tả ở trên:
Phiên bản của 0 được hiển thị ở trên làm nổi bật rõ ràng trường hợp cơ sở và cuộc gọi đệ quy, nhưng có một cách ngắn gọn hơn để thể hiện nó:
Ở đây, một lần thực hiện không nhận được để so sánh: >>>
Lưu ý cách 0 phù hợp với mô hình cho một thuật toán đệ quy được mô tả ở trên:Trường hợp cơ sở xảy ra khi def function(): x = 10 function() 2 bằng không, tại thời điểm đệ quy dừng lại.Trong cuộc gọi đệ quy, đối số ít hơn một giá trị hiện tại của 2, do đó, mỗi đệ quy di chuyển gần hơn với trường hợp cơ sở.Phiên bản của 0 được hiển thị ở trên làm nổi bật rõ ràng trường hợp cơ sở và cuộc gọi đệ quy, nhưng có một cách ngắn gọn hơn để thể hiện nó:Ở đây, một lần thực hiện không nhận được để so sánh: Đây là một trường hợp trong đó giải pháp không nhận được ít nhất là rõ ràng và trực quan như loại đệ quy, và có lẽ nhiều hơn như vậy.reductive, meaning that they reduce to one of the base cases:
Nói cách khác, n! là sản phẩm của tất cả các số nguyên từ 1 đến N, bao gồm. Factorial cho vay để định nghĩa đệ quy rằng các văn bản lập trình gần như luôn luôn bao gồm nó như một trong những ví dụ đầu tiên. Bạn có thể thể hiện định nghĩa của N! đệ quy như thế này:Như với ví dụ được hiển thị ở trên, có những trường hợp cơ sở có thể giải quyết được mà không có đệ quy. Các trường hợp phức tạp hơn là rút gọn, có nghĩa là chúng giảm xuống một trong các trường hợp cơ sở: Các trường hợp cơ sở (n = 0 hoặc n = 1) có thể giải quyết được mà không có đệ quy.Đối với các giá trị của n lớn hơn 1, n! được định nghĩa theo nghĩa (n - 1) !, Vì vậy, giải pháp đệ quy dần dần tiếp cận trường hợp cơ sở. >>> The factorial of 3 is 60 Lưu ý cách 0 phù hợp với mô hình cho một thuật toán đệ quy được mô tả ở trên:>>> The factorial of 3 is 61 Lưu ý cách 0 phù hợp với mô hình cho một thuật toán đệ quy được mô tả ở trên:Trường hợp cơ sở xảy ra khi 2 bằng không, tại thời điểm đệ quy dừng lại.>>> The factorial of 3 is 62 Lưu ý cách 0 phù hợp với mô hình cho một thuật toán đệ quy được mô tả ở trên:>>> The factorial of 3 is 63 Lưu ý cách 0 phù hợp với mô hình cho một thuật toán đệ quy được mô tả ở trên:Trường hợp cơ sở xảy ra khi 2 bằng không, tại thời điểm đệ quy dừng lại.Trong cuộc gọi đệ quy, đối số ít hơn một giá trị hiện tại của def function(): x = 10 function() 2, do đó, mỗi đệ quy di chuyển gần hơn với trường hợp cơ sở.Phiên bản của 0 được hiển thị ở trên làm nổi bật rõ ràng trường hợp cơ sở và cuộc gọi đệ quy, nhưng có một cách ngắn gọn hơn để thể hiện nó:The factorial of 3 is 64 Ở đây, một lần thực hiện không nhận được để so sánh: >>> The factorial of 3 is 65 Đây là một trường hợp trong đó giải pháp không nhận được ít nhất là rõ ràng và trực quan như loại đệ quy, và có lẽ nhiều hơn như vậy. Tính toán giai thừa Ví dụ tiếp theo liên quan đến khái niệm toán học của giai thừa. Bộ phận của một số nguyên dương N, được ký hiệu là N !, được định nghĩa như sau: >>> The factorial of 3 is 66 Nói cách khác, n! là sản phẩm của tất cả các số nguyên từ 1 đến N, bao gồm. >>> The factorial of 3 is 67 Cuối cùng, ở đây, phiên bản sử dụng 9:>>> The factorial of 3 is 68 Trong trường hợp này, việc thực hiện lặp là nhanh nhất, mặc dù giải pháp đệ quy không còn xa phía sau. Phương pháp sử dụng 9 là chậm nhất. Số dặm của bạn có thể sẽ thay đổi nếu bạn thử các ví dụ này trên máy của riêng bạn. Bạn chắc chắn đã giành được cùng một lần, và bạn thậm chí có thể không nhận được thứ hạng tương tự.Nó có quan trọng không? Có một sự khác biệt gần bốn giây trong thời gian thực hiện giữa việc thực hiện lặp lại và cuộc gọi sử dụng 9, nhưng phải mất mười triệu cuộc gọi để xem nó.Nếu bạn sẽ gọi một chức năng nhiều lần, bạn có thể cần tính đến tốc độ thực thi khi chọn triển khai. Mặt khác, nếu hàm sẽ chạy tương đối không thường xuyên, thì sự khác biệt về thời gian thực thi có thể sẽ không đáng kể. Trong trường hợp đó, bạn sẽ tốt hơn khi chọn cách thực hiện dường như thể hiện giải pháp cho vấn đề rõ ràng nhất. Đối với giai thừa, thời gian được ghi ở trên cho thấy việc thực hiện đệ quy là một lựa chọn hợp lý. Thành thật mà nói, nếu bạn mã hóa trong Python, bạn không cần phải thực hiện chức năng giai thừa. Nó đã có sẵn trong mô -đun 1 tiêu chuẩn:>>> The factorial of 3 is 69 Có lẽ bạn có thể quan tâm đến việc biết điều này thực hiện như thế nào trong bài kiểm tra thời gian: >>> factorial(3) # 1st call with 3 3 * factorial(2) # 2nd call with 2 3 * 2 * factorial(1) # 3rd call with 1 3 * 2 * 1 # return from 3rd call as number=1 3 * 2 # return from 2nd call 6 # return from 1st call0 Ồ! 2 hoạt động tốt hơn so với tốt nhất trong ba triển khai khác được hiển thị ở trên bởi khoảng 10 là 10.Một hàm được triển khai trong C sẽ hầu như luôn luôn nhanh hơn một hàm tương ứng được triển khai trong Python thuần túy. Đi qua một danh sách lồng nhauVí dụ tiếp theo liên quan đến việc truy cập từng mục trong cấu trúc danh sách lồng nhau. Hãy xem xét danh sách Python sau: factorial(3) # 1st call with 3 3 * factorial(2) # 2nd call with 2 3 * 2 * factorial(1) # 3rd call with 1 3 * 2 * 1 # return from 3rd call as number=1 3 * 2 # return from 2nd call 6 # return from 1st call1 Như sơ đồ sau đây cho thấy, 3 chứa hai người phụ. Bản thân những người phụ đầu tiên trong số những người phụ này chứa một người phụ trợ khác:Giả sử bạn muốn đếm số lượng các phần tử lá trong danh sách này, các đối tượng 4 cấp thấp nhất, vì bạn đã làm phẳng danh sách. Các yếu tố lá là 5, 6, 7, 8, 9, The factorial of 3 is 600, The factorial of 3 is 601, The factorial of 3 is 602, The factorial of 3 is 603 và The factorial of 3 is 604, vì vậy câu trả lời phải là Traceback (most recent call last): File "<string>", line 3, in <module> File "<string>", line 2, in a File "<string>", line 2, in a File "<string>", line 2, in a [Previous line repeated 996 more times] RecursionError: maximum recursion depth exceeded1.leaf elements in this list—the lowest-level 4 objects—as though you’d flattened out the list. The leaf elements are 5, 6, 7, 8, 9, The factorial of 3 is 600, The factorial of 3 is 601, The factorial of 3 is 602, The factorial of 3 is 603, and The factorial of 3 is 604, so the answer should be Traceback (most recent call last): File "<string>", line 3, in <module> File "<string>", line 2, in a File "<string>", line 2, in a File "<string>", line 2, in a [Previous line repeated 996 more times] RecursionError: maximum recursion depth exceeded1. Chỉ cần gọi The factorial of 3 is 606 trong danh sách không đưa ra câu trả lời chính xác: The factorial of 3 is 606 đếm các đối tượng ở cấp cao nhất của 3, là ba phần tử lá 5, The factorial of 3 is 601 và The factorial of 3 is 604 và hai người phụ The factorial of 3 is 612 và The factorial of 3 is 613: >>> factorial(3) # 1st call with 3 3 * factorial(2) # 2nd call with 2 3 * 2 * factorial(1) # 3rd call with 1 3 * 2 * 1 # return from 3rd call as number=1 3 * 2 # return from 2nd call 6 # return from 1st call2 Những gì bạn cần ở đây là một chức năng đi qua toàn bộ cấu trúc danh sách, bao gồm các nhóm phụ. Thuật toán đi một cái gì đó như thế này:
Lưu ý bản chất tự giới thiệu của mô tả này: Đi qua danh sách. Nếu bạn gặp phải một người phụ, thì tương tự đi qua danh sách đó. Tình huống này cầu xin cho đệ quy! Đi qua một danh sách lồng nhau một cách đệ quyĐệ quy phù hợp với vấn đề này rất độc đáo. Để giải quyết nó, bạn cần có khả năng xác định xem một mục danh sách nhất định có phải là mục lá hay không. Đối với điều đó, bạn có thể sử dụng chức năng Python tích hợp The factorial of 3 is 614. Trong trường hợp của danh sách 3, nếu một mục là một thể hiện của loại The factorial of 3 is 616, thì nó là một người phụ. Nếu không, nó là một mặt hàng lá: >>> factorial(3) # 1st call with 3 3 * factorial(2) # 2nd call with 2 3 * 2 * factorial(1) # 3rd call with 1 3 * 2 * 1 # return from 3rd call as number=1 3 * 2 # return from 2nd call 6 # return from 1st call3 Bây giờ bạn có các công cụ tại chỗ để thực hiện một chức năng đếm các phần tử lá trong danh sách, chiếm những người phụ thuộc một cách đệ quy: factorial(3) # 1st call with 3 3 * factorial(2) # 2nd call with 2 3 * 2 * factorial(1) # 3rd call with 1 3 * 2 * 1 # return from 3rd call as number=1 3 * 2 # return from 2nd call 6 # return from 1st call4 Nếu bạn chạy The factorial of 3 is 617 trên một số danh sách, bao gồm danh sách 3 được xác định ở trên, bạn sẽ nhận được điều này:>>> factorial(3) # 1st call with 3 3 * factorial(2) # 2nd call with 2 3 * 2 * factorial(1) # 3rd call with 1 3 * 2 * 1 # return from 3rd call as number=1 3 * 2 # return from 2nd call 6 # return from 1st call5 Như với ví dụ về giai thừa, việc thêm một số câu lệnh 5 giúp chứng minh chuỗi các cuộc gọi đệ quy và các giá trị trả về:factorial(3) # 1st call with 3 3 * factorial(2) # 2nd call with 2 3 * 2 * factorial(1) # 3rd call with 1 3 * 2 * 1 # return from 3rd call as number=1 3 * 2 # return from 2nd call 6 # return from 1st call6 Ở đây, một bản tóm tắt về những gì mà xảy ra trong ví dụ trên:
Đầu ra từ The factorial of 3 is 617 khi nó được thực hiện trong danh sách 3 bây giờ trông như thế này:>>> factorial(3) # 1st call with 3 3 * factorial(2) # 2nd call with 2 3 * 2 * factorial(1) # 3rd call with 1 3 * 2 * 1 # return from 3rd call as number=1 3 * 2 # return from 2nd call 6 # return from 1st call7 Mỗi lần một cuộc gọi đến The factorial of 3 is 617 chấm dứt, nó sẽ trả lại số lượng các yếu tố lá mà nó được ghi trong danh sách được truyền cho nó. Cuộc gọi cấp cao nhất trả về Traceback (most recent call last): File "<string>", line 3, in <module> File "<string>", line 2, in a File "<string>", line 2, in a File "<string>", line 2, in a [Previous line repeated 996 more times] RecursionError: maximum recursion depth exceeded1, như bình thường. Đi qua một danh sách lồng nhau không được quy địnhGiống như các ví dụ khác được hiển thị cho đến nay, Danh sách này, Traversal không yêu cầu đệ quy. Bạn cũng có thể hoàn thành nó lặp đi lặp lại. Ở đây, một khả năng: factorial(3) # 1st call with 3 3 * factorial(2) # 2nd call with 2 3 * 2 * factorial(1) # 3rd call with 1 3 * 2 * 1 # return from 3rd call as number=1 3 * 2 # return from 2nd call 6 # return from 1st call8 Nếu bạn chạy phiên bản không nhận được này của The factorial of 3 is 617 trên cùng danh sách như được hiển thị trước đó, bạn sẽ nhận được kết quả tương tự: >>> factorial(3) # 1st call with 3 3 * factorial(2) # 2nd call with 2 3 * 2 * factorial(1) # 3rd call with 1 3 * 2 * 1 # return from 3rd call as number=1 3 * 2 # return from 2nd call 6 # return from 1st call5 Chiến lược được sử dụng ở đây sử dụng một ngăn xếp để xử lý những người con được lồng nhau. Khi phiên bản The factorial of 3 is 617 này gặp phải một người phụ, nó sẽ đẩy danh sách hiện đang được tiến hành và chỉ mục hiện tại trong danh sách đó lên một ngăn xếp. Khi nó đã tính trình phụ, hàm bật danh sách cha mẹ và chỉ mục từ ngăn xếp để nó có thể tiếp tục đếm nơi nó rời đi. Trong thực tế, về cơ bản điều tương tự cũng xảy ra trong việc thực hiện đệ quy là tốt. Khi bạn gọi một chức năng đệ quy, Python sẽ lưu trạng thái của thể hiện thực thi trên ngăn xếp để cuộc gọi đệ quy có thể chạy. Khi kết thúc cuộc gọi đệ quy, trạng thái được bật từ ngăn xếp để thể hiện bị gián đoạn có thể tiếp tục. Nó cùng một khái niệm, nhưng với giải pháp đệ quy, Python đang thực hiện công việc tiết kiệm nhà nước cho bạn. Lưu ý mức độ ngắn gọn và có thể đọc được mã đệ quy khi so sánh với phiên bản không nhận được: Đệ quy so với danh sách lồng nhau không được ghi lạiĐây là một trường hợp sử dụng đệ quy chắc chắn là một lợi thế. Phát hiện palindromesViệc lựa chọn có nên sử dụng đệ quy để giải quyết vấn đề phụ thuộc vào phần lớn bản chất của vấn đề. Factorial, ví dụ, tự nhiên chuyển sang thực hiện đệ quy, nhưng giải pháp lặp cũng khá đơn giản. Trong trường hợp đó, nó được cho là một người ném lên. Các vấn đề danh sách truyền tải là một câu chuyện khác. Trong trường hợp đó, giải pháp đệ quy là rất thanh lịch, trong khi loại không tái tạo là cồng kềnh ở mức tốt nhất. Đối với vấn đề tiếp theo, sử dụng đệ quy được cho là ngớ ngẩn. Một palindrom là một từ đọc cùng nhau về phía trước như nó là về phía trước. Các ví dụ bao gồm các từ sau:palindrome is a word that reads the same backward as it does forward. Examples include the following words:
Nếu được yêu cầu nghĩ ra một thuật toán để xác định xem một chuỗi có phải là palindromic hay không, có lẽ bạn sẽ nghĩ ra một cái gì đó giống như đảo ngược chuỗi và xem nó có giống như bản gốc không. Bạn có thể nhận được đơn giản hơn thế. Thậm chí hữu ích hơn, Python từ The factorial of 3 is 632 Cú pháp cắt để đảo ngược một chuỗi cung cấp một cách thuận tiện để mã hóa nó: >>> 0Chiến lược được sử dụng ở đây sử dụng một ngăn xếp để xử lý những người con được lồng nhau. Khi phiên bản The factorial of 3 is 617 này gặp phải một người phụ, nó sẽ đẩy danh sách hiện đang được tiến hành và chỉ mục hiện tại trong danh sách đó lên một ngăn xếp. Khi nó đã tính trình phụ, hàm bật danh sách cha mẹ và chỉ mục từ ngăn xếp để nó có thể tiếp tục đếm nơi nó rời đi.
Phát hiện palindromes
Một palindrom là một từ đọc cùng nhau về phía trước như nó là về phía trước. Các ví dụ bao gồm các từ sau: >>> 1Xe đua Mức độChèo xuồng Reviverpivot item. This can be any item in the list. You then partition the list into two sublists based on the pivot item and recursively sort the sublists. Công dân
Các ký tự đầu tiên và cuối cùng là như nhau. Chất nền giữa các ký tự đầu tiên và cuối cùng là một palindrom.Cắt lát là bạn của bạn ở đây là tốt. Đối với một chuỗi The factorial of 3 is 633, việc lập chỉ mục và cắt, hãy cung cấp cho các nền tảng sau: Hãy tưởng tượng rằng danh sách ban đầu của bạn để sắp xếp chứa tám mục. Nếu mỗi phân vùng dẫn đến những người phụ có chiều dài gần bằng nhau, thì bạn có thể đạt được các trường hợp cơ sở trong ba bước: Phân vùng tối ưu, danh sách tám mụcỞ đầu kia của quang phổ, nếu sự lựa chọn của bạn về mục xoay đặc biệt không may mắn, mỗi phân vùng sẽ dẫn đến một người phụ chứa tất cả các mục gốc ngoại trừ mục Pivot và một người phụ khác trống. Trong trường hợp đó, phải mất bảy bước để giảm danh sách thành các trường hợp cơ sở: Phân vùng dưới mức tối ưu, danh sách tám mụcThuật toán Quicksort sẽ hiệu quả hơn trong trường hợp đầu tiên. Nhưng bạn cần phải biết điều gì đó trước về bản chất của dữ liệu mà bạn sắp xếp để chọn một cách có hệ thống các mục xoay tối ưu. Trong mọi trường hợp, có bất kỳ lựa chọn nào sẽ là tốt nhất cho tất cả các trường hợp. Vì vậy, nếu bạn viết một chức năng Quicksort để xử lý trường hợp chung, thì việc lựa chọn mục Pivot có phần tùy ý. Mục đầu tiên trong danh sách là một lựa chọn phổ biến, như mục cuối cùng. Chúng sẽ hoạt động tốt nếu dữ liệu trong danh sách được phân phối khá ngẫu nhiên. Tuy nhiên, nếu dữ liệu đã được sắp xếp, hoặc thậm chí gần như vậy, thì chúng sẽ dẫn đến phân vùng dưới mức tối ưu như được hiển thị ở trên. Để tránh điều này, một số thuật toán Quicksort chọn mục giữa trong danh sách làm mục Pivot. Một lựa chọn khác là tìm trung vị của các mục đầu tiên, cuối cùng và giữa trong danh sách và sử dụng nó làm mục Pivot. Đây là chiến lược được sử dụng trong mã mẫu dưới đây. Thực hiện phân vùngKhi bạn đã chọn mục Pivot, bước tiếp theo là phân vùng danh sách. Một lần nữa, mục tiêu là tạo ra hai người phụ, một người chứa các mục nhỏ hơn mục trục và cái còn lại chứa những thứ lớn hơn. Bạn có thể thực hiện điều này trực tiếp tại chỗ. Nói cách khác, bằng cách hoán đổi các mục, bạn có thể xáo trộn các mục trong danh sách xung quanh cho đến khi mục xoay ở giữa, tất cả các mục ít hơn ở bên trái và tất cả các mục lớn hơn ở bên phải của nó. Sau đó, khi bạn nhanh chóng xác định những người con đệ quy, bạn đã chuyển các lát của danh sách sang trái và bên phải của mục Pivot. Thay phiên, bạn có thể sử dụng khả năng thao tác danh sách Python, để tạo danh sách mới thay vì hoạt động trong danh sách ban đầu. Đây là cách tiếp cận được thực hiện trong mã dưới đây. Thuật toán như sau:
Lưu ý rằng điều này liên quan đến việc tạo ra một nhóm phụ thứ ba có chứa mục Pivot. Một lợi thế cho phương pháp này là nó xử lý trơn tru trường hợp mục Pivot xuất hiện trong danh sách nhiều lần. Trong trường hợp đó, Danh sách 2 sẽ có nhiều hơn một yếu tố. Sử dụng triển khai QuicksortBây giờ nền tảng đã được đặt ra, bạn đã sẵn sàng chuyển sang thuật toán Quicksort. Ở đây, mã Python: 2Đây là những gì mỗi phần của The factorial of 3 is 638 đang làm:
Dưới đây là một số ví dụ về The factorial of 3 is 638 trong hành động: >>> 3Đối với mục đích thử nghiệm, bạn có thể xác định một hàm ngắn tạo ra danh sách các số ngẫu nhiên giữa 0 và The factorial of 3 is 641: 4Bây giờ bạn có thể sử dụng The factorial of 3 is 642 để kiểm tra The factorial of 3 is 638: >>> 5Đối với mục đích thử nghiệm, bạn có thể xác định một hàm ngắn tạo ra danh sách các số ngẫu nhiên giữa 0 và The factorial of 3 is 641:Bây giờ bạn có thể sử dụng The factorial of 3 is 642 để kiểm tra The factorial of 3 is 638: Để hiểu thêm về cách The factorial of 3 is 638 hoạt động, hãy xem sơ đồ dưới đây. Điều này cho thấy chuỗi đệ quy khi sắp xếp danh sách mười hai phần tử:
The factorial of 3 is 651 Sự kết luậnĐiều đó kết thúc hành trình của bạn thông qua đệ quy, một kỹ thuật lập trình trong đó một chức năng tự gọi.Đệ quy isn bằng bất kỳ phương tiện nào phù hợp cho mọi nhiệm vụ.Nhưng một số vấn đề lập trình hầu như khóc vì nó.Trong những tình huống đó, nó là một kỹ thuật tuyệt vời để có được sự xử lý của bạn.recursion, a programming technique in which a function calls itself. Recursion isn’t by any means appropriate for every task. But some programming problems virtually cry out for it. In those situations, it’s a great technique to have at your disposal. Trong hướng dẫn này, bạn đã học được:
Bạn cũng đã thấy một số ví dụ về các thuật toán đệ quy và so sánh chúng với các giải pháp không nhận được tương ứng. Bây giờ bạn nên ở một vị trí tốt để nhận ra khi đệ quy được kêu gọi và sẵn sàng sử dụng nó một cách tự tin khi nó cần!Nếu bạn muốn khám phá thêm về đệ quy trong Python, thì hãy xem suy nghĩ đệ quy trong Python. |