Ý 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 để họ nắm bắt ý tưởng dễ dàng?

Thông tin thêm đang được chia sẻ về chủ đề này tại Tài nguyên để cải thiện sự hiểu biết của bạn về đệ quy? Đệ quy là khi một hàm có thể gọi chính nó. "Nếu bạn hoàn toàn hiểu không gian tên và phạm vi và cách các tham số được truyền cho một hàm, thì bạn đã biết đệ quy rồi. Tôi có thể hiển thị các ví dụ, nhưng bạn sẽ có thể tự mình tìm ra cách chúng hoạt động." Các sinh viên thường đấu tranh với đệ quy không quá nhiều vì nó khó hiểu, nhưng vì họ không nắm vững phạm vi / không gian tên biến. Trước khi đi sâu vào đệ quy, hãy đảm bảo rằng các sinh viên có thể theo dõi chính xác thông qua một chương trình mà bạn đã cố tình đưa ra các biến ở các phạm vi khác nhau cùng tên để gây nhầm lẫn cho họ. — dspyz 1 vi.wikipedia.org/wiki/Turtles_all_the_way_down — Thomas Eding 1 Để hiểu đệ quy, trước tiên bạn phải hiểu đệ quy — Goerman

Câu trả lời:

110

Để 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ó.Bạ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ể.

Bạn đang xem: Đệ quy tiếng anh là gì

Toán học

Nếu học sinh của bạn (hoặc người bạn giải thích quá, 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 loạt và khái niệm về đệ quy và quan hệ lặp lại của chúng .

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, nó thực sự là một phiên bản chi tiết về những gì tôi thể hiện trong Phụ lục của câu trả lời của tôi cho câu hỏi mà bạn chỉ ra 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 writehoặ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,

yếu 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 chúng đế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 chỉ bằng cá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 (hoặc trước đó).

Các fan 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, hãy thoải mái nối với một danh sách ở mỗi lần lặp và chỉ in kết quả cuối cùng. .

Lũy thừa

Vấn đề lũy thừa hơi khó khăn hơn ( ở giai đoạn học tập này). 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ó:


*

*

Khó hơn

Khi các vấn đề đơn giản này đã được hiển thị VÀ được triển khai 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ế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.

Xem thêm: Official Dispatch Là Gì ? Đâu Là Khái Niệm Đúng Nhất? Công Official Dispatch Là Gì

Người giúp việc

Một tài liệu tham khảo

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

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 trình thám hiểm 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ác 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 Unix thay thế Daemon" (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ư sửa lỗi tìm kiếm đệ quy của Google . Để biết thêm thông tin về đệ quy, đọ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 mô hình Phân chia và Chinh phục sẽ phù hợp với thuật toán đệ quy đa nhánh.

Lại là gì nữa ??

Tại sao mỗi lần tôi nhoặc (bất cứ tên biến của bạn) khác nhau? Người mới bắt đầu thường có một vấn đề hiểu một biến và tham số là gì và làm thế nào để những thứ có tên ntrong 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à 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ủ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.

Ma quỷ là trong các 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 các sinh viên một cách riêng tư, những người chỉ cho tôi những bài giảng nơi họ có 50 slide về mọi thứ cần biết về đệ quy khi họ hầu như không thể viết một vòng lặp chính xác trong 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 này nhưng ngay bây giờ chỉ khiến bạn bối rối .

Nhưng xin vui lòng, trong thời gian thích hợp, làm rõ rằng có những lý do để đi theo con đường lặp hoặc đệ quy .

Đệ quy lẫn nhau

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, các chuỗi Nam và Nữ của Hofstadter :

Bài viết liên quan

Trả lời

Email của bạn sẽ không được hiển thị công khai. Các trường bắt buộc được đánh dấu *