Dưới đây là 22 mã Python thực tế, có thể chạy được cho một số hàm đệ quy, được viết theo phong cách để người mới bắt đầu có thể hiểu được và tạo ra đầu ra có thể gỡ lỗi
Đây không phải là những đoạn mã; . Mã nguồn đã được đặt bên trong một trường văn bản để giúp việc cuộn qua bài đăng trên blog này dễ dàng hơn. Bạn có thể nhấp vào trường văn bản, chọn tất cả bằng cách nhấn Ctrl-A, sau đó sao chép mã vào khay nhớ tạm bằng cách nhấn Ctrl-C. Sau khi vào khay nhớ tạm, bạn có thể dán nó vào trình chỉnh sửa hoặc IDE của mình. Ngoài ra còn có các liên kết tải xuống cho từng chương trình
Các hàm đệ quy này cũng được thiết kế để tạo ra kết quả hữu ích, có thể dạy được. Một số hàm có tham số indent để hỗ trợ đầu ra này và bản thân nó không phải là một phần của thuật toán đệ quy
Ackermann
Tải xuống ackermann. py
Hàm Ackermann được đặt tên theo người phát hiện ra nó, Wilhelm Ackermann. Ackermann, học trò của nhà toán học David Hilbert [người tạo ra fractal đường cong Hilbert], đã công bố hàm của mình vào năm 1928. Các nhà toán học Rózsa Péter và Raphael Robinson sau đó đã phát triển phiên bản của hàm đặc trưng trong phần này. Mặc dù hàm Ackermann có một số ứng dụng trong toán học cao cấp, nhưng nó chủ yếu được biết đến là một ví dụ về hàm có tính đệ quy cao. Ngay cả việc tăng nhẹ đối với hai đối số nguyên của nó cũng gây ra sự gia tăng lớn về số lượng lệnh gọi đệ quy mà nó thực hiện
Kênh YouTube Computerphile có một video trên đó với tiêu đề "Chương trình khó tính toán nhất?"
Đầu ra của chương trình này trông như thế này
Tìm kiếm nhị phân
Tải xuống tìm kiếm nhị phân. py
Tìm kiếm nhị phân là một kỹ thuật để định vị mục tiêu trong danh sách được sắp xếp bằng cách xác định lại nhiều lần mục đó nằm trong nửa danh sách nào. Cách công bằng nhất để tìm kiếm giá sách là bắt đầu với một cuốn sách ở giữa, sau đó xác định xem cuốn sách mục tiêu bạn đang tìm nằm ở nửa bên trái hay nửa bên phải
Sau đó, bạn có thể lặp lại quá trình này. nhìn vào cuốn sách ở giữa nửa bạn đã chọn và xác định xem cuốn sách mục tiêu của bạn nằm ở phần tư bên trái hay phần tư bên phải. Bạn có thể làm điều này cho đến khi bạn tìm thấy cuốn sách hoặc tìm thấy vị trí mà cuốn sách nên ở nhưng không có và tuyên bố rằng cuốn sách không tồn tại trên giá sách
Đầu ra của chương trình này trông như thế này
kết hợp
Tải xuống kết hợp. py
Đưa ra một tập hợp các mục, chúng tôi có thể trả về một tập hợp mọi kết hợp của các mục đó. Ví dụ, cho một bộ bốn chữ cái, ABCD, k-kết hợp là
- Các tổ hợp 0 và 4 tổ hợp có một tổ hợp. chuỗi rỗng và ABCD tương ứng
- Các tổ hợp 1 và 3 tổ hợp có bốn tổ hợp. A, B, C, D lần lượt là ABC, ABD, ACD, BCD
- 2 tổ hợp có nhiều tổ hợp nhất ở sáu tổ hợp. AB, AC, AD, BC, BD và CD
Đầu ra của chương trình này trông như thế này
Đếm ngược và đếm ngược
Tải xuống đếmDownAndUp. py
Hàm này minh họa một hàm đệ quy đơn giản và hiển thị thứ tự mã chạy trước và sau lệnh gọi đệ quy
Đầu ra của chương trình này trông như thế này
Tam giác Sierpinki say xỉn
Tải say rượuSierpinkiTriangle. py
Chương trình này sử dụng mô-đun turtle để vẽ một fractal tam giác sierpinki, ngoại trừ một số lỗi nhỏ khiến fractal có vẻ méo mó
Đầu ra của chương trình này trông như thế này
tám nữ hoàng
Tải xuống támQueens. py
Câu đố tám quân hậu là cách sắp xếp tám quân hậu trên một bàn cờ sao cho chúng không thể tấn công lẫn nhau. Chương trình đệ quy này tìm mọi giải pháp có thể trên bàn cờ 8 x 8
Đầu ra của chương trình này trông như thế này
lũy thừa
Tải xuống số mũWithPowerRule. py
Tính toán các số mũ như 2^5 [hoặc 2 x 2 x 2 x 2 x 2] có thể được thực hiện mà không cần sử dụng toán tử ** bằng cách thực hiện các phép nhân lặp lại. Tuy nhiên, có một lối tắt trong đó 2^[m * 2] == 2^m * 2^m. Bạn có thể sử dụng thủ thuật này để thực hiện a^m trong ít hơn m phép nhân
Đầu ra của chương trình này trông như thế này
yếu tố
Tải về đệ quy giai thừa. py
Giai thừa của 4 là 4 × 3 × 2 × 1 và giai thừa của 5 là 5 × 4 × 3 × 2 × 1. Vì vậy, bạn có thể nói rằng 5. = 5 × 4. Đây là đệ quy vì định nghĩa giai thừa của 5 [hoặc bất kỳ số n nào] bao gồm định nghĩa của giai thừa của 4 [số n – 1]. Lần lượt, 4. = 4 × 3. , v.v., cho đến khi bạn phải tính 1. , trường hợp cơ sở, đơn giản là 1
Đầu ra của chương trình này trông như thế này
Fibonacci
Tải xuống đệ quy fibonacci. py
Dãy Fibonacci là một ví dụ cổ điển khác để giới thiệu đệ quy. Về mặt toán học, dãy số nguyên Fibonacci bắt đầu bằng các số 1 và 1 [hoặc đôi khi là 0 và 1]. Số tiếp theo trong dãy bằng tổng hai số liền trước. Điều này tạo ra chuỗi 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, v.v., mãi mãi
Có một thuộc tính đệ quy để tính các số Fibonacci. Ví dụ, nếu bạn muốn tính số Fibonacci thứ 10, bạn cộng các số Fibonacci thứ 9 và thứ 8 với nhau. Để tính các số Fibonacci đó, bạn cộng số thứ 8 và thứ 7, sau đó là số Fibonacci thứ 7 và thứ 6. Sẽ có rất nhiều phép tính lặp lại. lưu ý rằng việc thêm số Fibonacci thứ 9 và thứ 8 liên quan đến việc tính lại số Fibonacci thứ 8. Bạn sẽ tiếp tục đệ quy này cho đến khi đạt được trường hợp cơ sở của các số Fibonacci thứ nhất hoặc thứ hai, luôn là 1
Đầu ra của chương trình này trông như thế này
lũ lụt
Tải xuống vùng lũ. py
Đầu ra của chương trình này trông như thế này
GCD, Mẫu số chung lớn nhất
Tải xuống gcdRecursive. py
Các yếu tố là những con số được nhân lên để tạo ra một số cụ thể. Xét 4 × 6 = 24. Trong phương trình này, 4 và 6 là thừa số của 24. Vì thừa số của một số cũng có thể dùng để chia số đó mà không để lại số dư nên thừa số còn được gọi là ước
Các thừa số của 24 là 1, 2, 3, 4, 6, 8, 12 và 24. Các thừa số của 30 là 1, 2, 3, 5, 6, 10, 15 và 30. Lưu ý rằng bất kỳ số nào sẽ luôn có 1 và chính nó là các ước của nó vì 1 nhân với một số bằng chính số đó. Cũng lưu ý rằng danh sách các thừa số của 24 và 30 có 1, 2, 3 và 6 điểm chung. Thừa số chung lớn nhất là 6, vì vậy 6 là thừa số chung lớn nhất, thường được gọi là ước chung lớn nhất [GCD], của 24 và 30
Euclid, một nhà toán học sống cách đây 2000 năm, đã đưa ra một thuật toán ngắn để tìm GCD của hai số bằng cách sử dụng số học mô-đun. Thuật toán của anh ấy có thể được thực hiện với đệ quy
Đầu ra của chương trình này trông như thế này
Fractal đường cong Hilbert
Tải xuống hilbertCurve. py
Đường cong lấp đầy không gian là đường một chiều uốn quanh cho đến khi nó lấp đầy hoàn toàn không gian hai chiều mà không cắt qua chính nó. Nhà toán học người Đức David Hilbert đã mô tả đường cong Hilbert lấp đầy không gian của ông vào năm 1891
Đầu ra của chương trình này trông như thế này
Phép nhân Karatsuba
Tải xuống phép nhân karatsuba. py
Phép nhân Karatsuba là một thuật toán đệ quy, nhanh được Anatoly Karatsuba phát hiện vào năm 1960, có thể nhân các số nguyên bằng cách sử dụng phép cộng, phép trừ và bảng nhân được tính toán trước của tất cả các tích từ các số có một chữ số
Đầu ra của chương trình này trông như thế này
Fractal bông tuyết Koch
Tải về kochSnowflake. py
Được giới thiệu lần đầu tiên vào năm 1902 bởi nhà toán học Thụy Điển Helge von Koch, đường cong Koch là một trong những fractal sớm nhất được mô tả bằng toán học. xây dựng của nó là đơn giản. lấy một đoạn thẳng dài b và chia nó thành ba phần bằng nhau, mỗi phần dài b / 3. Thay thế phần giữa bằng một "vết sưng" có các cạnh cũng dài b / 3. Vết sưng này làm cho đường cong Koch dài hơn đường ban đầu, vì bây giờ có bốn đoạn đường có độ dài b / 3. [Chúng tôi sẽ loại trừ phần giữa ban đầu của đoạn đường. ] Việc tạo vết sưng này có thể được lặp lại trên bốn đoạn đường mới. Bông tuyết Koch là ba trong số các đường cong Koch này được kết nối với nhau
Đầu ra của chương trình này trông như thế này
Hợp nhất Sắp xếp
Tải xuống mergeSort. py
Nhà khoa học máy tính John von Neumann đã phát triển sắp xếp hợp nhất vào năm 1945 và đó là một thuật toán sắp xếp có mục đích chung, hiệu quả, đặc biệt được sử dụng để sắp xếp các cấu trúc dữ liệu danh sách được liên kết. Nó sử dụng một cách tiếp cận phân chia hợp nhất. mỗi lệnh gọi đệ quy đến mergeSort[] chia danh sách chưa được sắp xếp thành hai nửa cho đến khi chúng được chia thành các danh sách có độ dài bằng 0 hoặc một. Sau đó, khi các cuộc gọi đệ quy trở lại, các danh sách nhỏ hơn này được hợp nhất với nhau theo thứ tự được sắp xếp. Khi cuộc gọi đệ quy cuối cùng đã trở lại, toàn bộ danh sách sẽ được sắp xếp
Ví dụ: bước chia lấy một danh sách, chẳng hạn như [0, 7, 6, 3, 1, 2, 5, 4] và chia thành hai danh sách, chẳng hạn như [0, 7, 6, 3] và [1 . Ở trường hợp cơ sở, các danh sách đã được chia thành các danh sách không hoặc một mục. Sau khi các cuộc gọi đệ quy trở lại, mã sẽ hợp nhất hai danh sách thành một danh sách lớn hơn. Nếu hai danh sách được sắp xếp theo thứ tự [và danh sách không hoặc một mục được sắp xếp theo bản chất của chúng], việc hợp nhất cũng sẽ tạo ra một danh sách được sắp xếp. Kết quả cuối cùng là cuộc gọi mergeSort[] ban đầu trả về danh sách đầy đủ theo thứ tự được sắp xếp
Đầu ra của chương trình này trông như thế này
hoán vị
Tải xuống hoán vị. py
Một hoán vị của một tập hợp là một thứ tự cụ thể của tất cả các phần tử trong tập hợp. Ví dụ: có sáu hoán vị cho tập hợp {A, B, C}. ABC, ACB, BAC, BCA, CAB và CBA. Chúng tôi gọi đây là các hoán vị không lặp lại hoặc hoán vị không thay thế, bởi vì mỗi phần tử không xuất hiện trong hoán vị nhiều hơn một lần
Hãy tưởng tượng bạn phải sắp xếp sơ đồ chỗ ngồi cho một tiệc cưới với những yêu cầu xã giao tế nhị. Một số khách ghét nhau và trong khi những người khác yêu cầu ngồi gần một vị khách có ảnh hưởng. Các ghế ở bàn tạo thành một hàng dài, thay vì một vòng tròn. Sẽ hữu ích cho việc lập kế hoạch của bạn để xem mọi thứ tự có thể có của khách, nghĩa là mọi hoán vị mà không lặp lại nhóm khách. Không có sự lặp lại vì mỗi khách sẽ chỉ xuất hiện trong sơ đồ chỗ ngồi một lần. Hãy sử dụng một ví dụ đơn giản về Alice, Bob và Carol hoặc {A, B, C}
Đầu ra của chương trình này trông như thế này
Sắp xếp nhanh chóng
Tải xuống sắp xếp nhanh. py
Quicksort sử dụng kỹ thuật chia để trị được gọi là phân vùng. Hãy nghĩ về phân vùng theo cách này. hãy tưởng tượng bạn có một chồng sách lớn không được sắp xếp theo thứ tự. Lấy một cuốn sách và đặt nó vào đúng vị trí trên giá có nghĩa là bạn sẽ mất nhiều thời gian để sắp xếp lại giá sách khi nó đầy. Sẽ rất hữu ích nếu bạn lần đầu biến chồng sách thành hai chồng. cọc A đến M và cọc N đến Z. [Trong ví dụ này, M sẽ là trục của chúng ta. ]
Bạn chưa sắp xếp đống, nhưng bạn đã phân vùng nó. Và phân vùng dễ dàng. cuốn sách không nhất thiết phải đi vào đúng vị trí của một trong hai chồng, nó chỉ cần đi vào đúng chồng. Sau đó, bạn có thể phân chia thêm hai cọc này thành bốn cọc. A đến G, H đến M, N đến T, và U đến Z. Điều này được thể hiện trong Hình 5-x. Nếu bạn tiếp tục phân vùng, cuối cùng bạn sẽ có các chồng chứa một cuốn sách [hộp cơ sở] và các chồng hiện được sắp xếp theo thứ tự. Phân vùng lặp đi lặp lại này là cách quicksort hoạt động
Trong triển khai của chúng tôi, mỗi lệnh gọi quicksort[] được cung cấp một mảng các mục để sắp xếp. Nó cũng đưa ra các đối số trái và phải chỉ định phạm vi chỉ mục trong mảng đó để sắp xếp, tương tự như đối số trái và phải của binarySearch[]. Thuật toán chọn một giá trị trục để so sánh với các giá trị khác trong phạm vi, sau đó đặt các giá trị vào phía bên trái của phạm vi [nếu chúng nhỏ hơn giá trị trục] hoặc phía bên phải [nếu chúng lớn hơn . Đây là bước phân vùng. Tiếp theo, hàm quicksort[] được gọi đệ quy trên hai phạm vi nhỏ hơn này cho đến khi một phạm vi được giảm xuống 0. Danh sách ngày càng được sắp xếp nhiều hơn khi các lệnh gọi đệ quy được thực hiện, cho đến khi cuối cùng toàn bộ danh sách được sắp xếp đúng thứ tự
Đầu ra của chương trình này trông như thế này
Chức năng đệ quy ngắn nhất có thể
Tải xuống ngắn nhất. py
Để minh họa, đây là hàm đệ quy ngắn nhất có thể. Nó chỉ đơn thuần là một chức năng gọi chính nó. Nó sẽ dẫn đến lỗi tràn ngăn xếp
Đầu ra của chương trình này trông như thế này
Thảm Sierpinki
Tải xuống thảm sierpinki. py
Thảm sierpinki là một hình vuông có tâm trống và các thảm sierpinki dạng fractal ở 8 khu vực chu vi của hình vuông
Đầu ra của chương trình này trông như thế này
Tam giác Sierpinki
Tải xuống Tam giác sierpinki. py
Tam giác sierpinki là tam giác đều chứa ba tam giác sierpinki. Nó trông giống như triforce từ trò chơi điện tử Zelda
Đầu ra của chương trình này trông như thế này
Tháp Hà Nội
Tải towerOfHanoiSolver. py
Tháp Hà Nội là một câu đố liên quan đến một tháp đĩa xếp chồng lên nhau. Câu đố bắt đầu với đĩa lớn nhất ở dưới cùng và kích thước đĩa giảm dần. Các đĩa có một lỗ ở tâm để chúng có thể được xếp chồng lên nhau thông qua một cây sào. Để giải câu đố, người chơi phải di chuyển chồng đĩa từ cột này sang cột khác trong khi tuân theo ba quy tắc
- Người chơi chỉ có thể di chuyển một đĩa tại một thời điểm
- Người chơi chỉ có thể di chuyển đĩa đến và đi từ đỉnh tháp
- Người chơi không bao giờ có thể đặt đĩa lớn hơn lên trên đĩa nhỏ hơn
Đầu ra của chương trình này trông như thế này
Fractal cây
Tải xuống fractalTree. py
Cây có thể được tạo bằng thuật toán dưới dạng fractal. Những cây này được tạo ra bằng cách mỗi nhánh tạo ra hai nhánh tương tự nhưng nhỏ hơn
Đầu ra của chương trình này trông như thế này
Tìm hiểu thêm về đệ quy
Để tìm hiểu cách các chương trình này hoạt động và tìm hiểu thêm về đệ quy nói chung, bạn có thể xem cuốn sách của tôi, Cuốn sách về đệ quy. Bạn có thể nhận bản ebook miễn phí khi mua sách in từ nhà xuất bản, No Starch Press