Ý tưởng về đệ quy không phổ biến lắm trong thế giới thực. Vì vậy, nó có vẻ hơi khó hiểu với các lập trình viên mới làm quen. Mặc dù, tôi đoán, họ dần dần quen với khái niệm này. Vì vậy, những gì có thể là một lời giải thích tốt đẹp cho họ để nắm bắt ý tưởng dễ dàng?
Để giải thích đệ quy , tôi sử dụng kết hợp nhiều cách giải thích khác nhau, thường là để cả hai cố gắng:
giải thích khái niệmgiải thích tại sao nó quan trọnggiải thích làm thế nào để có được nó.
Đang xem: đệ quy tiếng anh là gì
Để bắt đầu, Wolfram | Alpha định nghĩa nó theo thuật ngữ đơn giản hơn Wikipedia :
Một biểu thức sao cho mỗi thuật ngữ được tạo bằng cách lặp lại một phép toán cụ thể.
Toán học
Nếu học sinh của bạn (hoặc người bạn giải thích cũng vậy, từ bây giờ tôi sẽ nói học sinh) có ít nhất một số nền tảng toán học, rõ ràng là chúng đã gặp phải đệ quy bằng cách nghiên cứu chuỗi và khái niệm của chúng về đệ quy và của họ quan hệ lặp lại .
Một cách rất tốt để bắt đầu sau đó là thể hiện bằng một loạt và nói rằng nó khá đơn giản là những gì đệ quy nói về:
một hàm toán học …… Nó tự gọi mình để tính toán một giá trị tương ứng với phần tử thứ n …… Và xác định một số ranh giới.
Thông thường, bạn có thể nhận được “huh huh, whatev “” vì họ vẫn không sử dụng nó, hoặc nhiều khả năng chỉ là một tiếng ngáy rất sâu.
Ví dụ mã hóa
Đối với phần còn lại, đây thực sự là phiên bản chi tiết của những gì tôi đã trình bày trong Phụ lục của câu trả lời của tôi cho câu hỏi bạn đã chỉ liên quan đến con trỏ (chơi chữ xấu).
Ở giai đoạn này, học sinh của tôi thường biết cách in một cái gì đó lên màn hình. Giả sử chúng ta đang sử dụng C, họ biết cách in một char bằng cách sử dụng write hoặc printf. Họ cũng biết về các vòng điều khiển.
Tôi thường sử dụng một vài vấn đề lập trình đơn giản và lặp đi lặp lại cho đến khi họ hiểu được:
một máy in bảng chữ cái,một máy in bảng chữ cái đảo ngược,
Nhân tố
Yếu tố là một khái niệm toán học rất đơn giản để hiểu, và việc thực hiện rất gần với biểu diễn toán học của nó. Tuy nhiên, họ có thể không nhận được nó lúc đầu.
Bảng chữ cái
Phiên bản bảng chữ cái rất thú vị để dạy họ suy nghĩ về thứ tự của các câu lệnh đệ quy. Giống như với con trỏ, họ sẽ chỉ ném ngẫu nhiên vào bạn. Vấn đề là đưa họ đến nhận ra rằng một vòng lặp có thể được đảo ngược bằng cách sửa đổi các điều kiện <~ # ~> hoặc <~ # ~> bởi chỉ đảo ngược thứ tự của các câu lệnh trong hàm của bạn. Đó là nơi in bảng chữ cái giúp, vì nó là một cái gì đó trực quan cho họ. Đơn giản chỉ cần họ viết một hàm sẽ in một ký tự cho mỗi cuộc gọi và gọi chính nó một cách đệ quy để viết tiếp theo (hoặc trước đó).
Người hâm mộ của FP, bỏ qua thực tế rằng việc in các thứ vào luồng đầu ra là một tác dụng phụ bây giờ … Chúng ta đừng quá khó chịu trên mặt trận FP. (Nhưng nếu bạn sử dụng một ngôn ngữ có hỗ trợ danh sách, vui lòng ghép nối một danh sách ở mỗi lần lặp và chỉ in kết quả cuối cùng. Nhưng thường thì tôi bắt đầu bằng C, không may là không tốt nhất cho loại vấn đề và khái niệm này) .
lũy thừa
Vấn đề lũy thừa hơi khó khăn hơn một chút ( ở giai đoạn này của việc học). Rõ ràng khái niệm này hoàn toàn giống với một giai thừa và không có sự phức tạp thêm vào … ngoại trừ việc bạn có nhiều tham số. Và điều đó thường đủ để gây nhầm lẫn cho mọi người và ném chúng ngay từ đầu.
Hình thức đơn giản của nó:
có thể được thể hiện như thế này bằng cách tái phát:
Cứng hơn
Khi các vấn đề đơn giản này đã được hiển thị VÀ được thực hiện lại trong hướng dẫn, bạn có thể đưa ra các bài tập khó hơn (nhưng rất cổ điển):
Và nếu bạn có một môi trường đồ họa (hoặc có thể cung cấp cuống mã cho nó hoặc cho đầu ra thiết bị đầu cuối hoặc họ có thể quản lý điều đó rồi), những thứ như: <.__.>Và đối với các ví dụ thực tế, hãy xem xét việc viết: <.__.>một thuật toán truyền tải cây,một trình phân tích cú pháp biểu thức toán học đơn giản,một trò chơi quét mìn.
Lưu ý: Một lần nữa, một số trong số này thực sự không khó hơn … Họ chỉ tiếp cận vấn đề từ cùng một góc độ, hoặc một góc hơi khác. Nhưng thực hành làm cho hoàn hảo.
Người giúp việc
Tham chiếu
Một số đọc không bao giờ đau. Chà, lúc đầu nó sẽ như vậy, và họ sẽ còn cảm thấy lạc lõng hơn nữa. Đó là thứ phát triển trong bạn và nằm ở phía sau đầu bạn cho đến một ngày bạn nhận ra rằng cuối cùng bạn đã nhận được nó. Và sau đó bạn nghĩ lại những thứ bạn đọc. đệ quy , đệ quy trong Khoa học máy tính và quan hệ lặp lại các trang trên Wikipedia sẽ làm ngay bây giờ.
Xem thêm: Neighbours From Hell Compilation On Steam, Neighbours From Hell 1
Cấp/Độ sâu
Giả sử sinh viên của bạn không có nhiều kinh nghiệm mã hóa, hãy cung cấp cuống mã. Sau những lần thử đầu tiên, hãy cung cấp cho họ chức năng in có thể hiển thị mức đệ quy. In giá trị số của cấp độ giúp.
Sơ đồ ngăn xếp ngăn xếp
Việc thụt vào một kết quả được in (hoặc đầu ra của cấp độ) cũng giúp ích, vì nó cung cấp một biểu diễn trực quan khác về những gì chương trình của bạn đang làm, mở và đóng các bối cảnh ngăn xếp như ngăn kéo hoặc thư mục trong Explorer hệ thống tệp.
Từ viết tắt đệ quy
Nếu sinh viên của bạn đã thành thạo một chút về văn hóa máy tính, họ có thể đã sử dụng một số dự án/phần mềm có tên bằng cách sử dụng từ viết tắt đệ quy . Đó là một truyền thống xuất hiện trong một thời gian, đặc biệt là trong các dự án GNU. Một số ví dụ bao gồm:
Đệ quy:
GNU – “GNU không phải Unix”Nagios – “Nagios Ain”t Gonna khăng khăng về vị thánh”PHP – “Bộ xử lý siêu văn bản PHP” (và nguồn gốc là “Trang chủ cá nhân”)Rượu vang – “Rượu không phải là trình giả lập”Zile – “Zile là mất mát Emacs”
Đệ quy lẫn nhau:
HURD – “HIRD của Daemon thay thế Unix” (trong đó HIRD là “HURD của các giao diện đại diện cho độ sâu”)
Có họ cố gắng để đưa ra với riêng của họ.
Tương tự, có nhiều sự xuất hiện của sự hài hước đệ quy, như tìm kiếm đệ quy của Google chỉnh sửa. Để biết thêm thông tin về đệ quy, hãy đọc câu trả lời này .
Cạm bẫy và học hỏi thêm
Một số vấn đề mà mọi người thường đấu tranh và bạn cần biết câu trả lời.
Tại sao, trời ơi Tại sao ???
Tại sao bạn lại làm vậy? Một lý do tốt nhưng không rõ ràng là thường đơn giản hơn để diễn đạt một vấn đề theo cách đó. Một lý do không tốt nhưng rõ ràng là nó thường mất ít thao tác gõ hơn (đừng khiến họ cảm thấy loot l33t vì chỉ sử dụng đệ quy mặc dù …).
Một số vấn đề chắc chắn dễ giải quyết hơn khi sử dụng phương pháp đệ quy. Thông thường, bất kỳ vấn đề nào bạn có thể giải quyết bằng cách sử dụng Phân chia và chinh phục mô hình sẽ phù hợp với thuật toán đệ quy đa nhánh.
N là gì nữa ??
Tại sao n hoặc (bất cứ tên biến của bạn) khác nhau mỗi lần? Người mới bắt đầu thường gặp vấn đề trong việc hiểu biến và tham số là gì và làm thế nào để những thứ có tên n trong chương trình của bạn có thể có các giá trị khác nhau. Vì vậy, bây giờ nếu giá trị này nằm trong vòng điều khiển hoặc đệ quy, điều đó thậm chí còn tồi tệ hơn! Hãy tử tế và không sử dụng cùng một tên biến ở mọi nơi và làm rõ rằng các tham số chỉ là các biến .
Điều kiện kết thúc
Làm thế nào để tôi xác định tình trạng cuối cùng của tôi? Điều đó thật dễ dàng, chỉ cần họ nói to các bước. Chẳng hạn, giai thừa bắt đầu từ 5, rồi 4, rồi … cho đến 0.
Quỷ dữ nằm trong Chi tiết
Đừng nói chuyện với những thứ sớm như tối ưu hóa cuộc gọi đuôi . Tôi biết, tôi biết, TCO rất hay, nhưng lúc đầu họ không quan tâm. Cung cấp cho họ một chút thời gian để quấn đầu xung quanh quá trình theo cách phù hợp với họ. Hãy thoải mái phá vỡ thế giới của họ một lần nữa sau đó, nhưng hãy cho họ nghỉ ngơi.
Tương tự, đừng nói thẳng từ bài giảng đầu tiên về ngăn xếp cuộc gọi và mức tiêu thụ bộ nhớ của nó và … à … tràn ngăn xếp . Tôi thường dạy kèm cho sinh viên một cách riêng tư, người chỉ cho tôi những bài giảng về họ có 50 slide về mọi thứ Có để biết về đệ quy khi họ hầu như không thể viết một vòng lặp chính xác ở giai đoạn này. Đó là một ví dụ tốt về cách một tài liệu tham khảo sẽ giúp sau nhưng ngay bây giờ chỉ cần nhầm lẫn bạn sâu sắc.
Nhưng xin vui lòng, trong thời gian thích hợp, hãy làm rõ rằng có lý do để đi theo lộ trình lặp hoặc đệ quy .
Đệ quy lẫn nhau
Chúng ta đã thấy rằng các hàm có thể được đệ quy và thậm chí chúng có thể có nhiều điểm gọi (8-Queen, Hà Nội, Fibonacci hoặc thậm chí là một thuật toán thăm dò cho một người quét mìn). Nhưng còn các cuộc gọi đệ quy lẫn nha thì sao? Bắt đầu với toán học ở đây là tốt. f(x) = g(x) + h(x) trong đó g(x) = f(x) + l(x) và h và l chỉ làm công cụ.
Xem thêm: Nghĩa Của Từ Tessellation Là Gì ? Sự Giao Thoa Của Nghệ Thuật Và Toán Học
Bắt đầu chỉ với loạt toán học giúp viết và thực hiện dễ dàng hơn vì hợp đồng được xác định rõ ràng bằng các biểu thức. Chẳng hạn, Trình tự nam và nữ của Hofstadter :
Tuy nhiên, về mặt mã, cần lưu ý rằng việc triển khai giải pháp đệ quy lẫn nhau thường dẫn đến sao chép mã và nên được sắp xếp hợp lý thành một dạng đệ quy duy nhất (Xem Peter Norvig ” Giải từng câu đố Sudok .
