Recursion
Đã giới thiệu| English | Ý nghĩa |
|---|---|
| recursive/rɪˈkɜːsɪv/ | đệ quy |
| base case/beɪs keɪs/ | trường hợp cơ sở |
| recursive case/rɪˈkɜːsɪv keɪs/ | trường hợp đệ quy |
| call stack/kɔːl stæk/ | ngăn gọi hàm |
| stack frame/stæk freɪm/ | khung ngăn |
| stack overflow/stæk ˌəʊvəˈfləʊ/ | tràn ngăn |
| memoisation/ˌmeməʊaɪˈzeɪʃn/ | ghi nhớ |
Một định nghĩa chứa chính nó
- Làm thế nào để nói tổ tiên là gì? Cha mẹ bạn là tổ tiên. Tổ tiên của cha mẹ bạn cũng vậy. Hai câu trên xác định một chuỗi vô hạn, và câu thứ hai sử dụng chính từ mà nó đang định nghĩa.
- Đó không phải là lập luận vòng tròn, vì câu đầu tiên đưa ra nơi dừng cho chuỗi. Nếu không có nó, định nghĩa sẽ kéo dài mãi mãi.
- Chương trình có thể được viết giống nhau, và đối với các bài toán có cấu trúc dạng chuỗi đó, một giải pháp đệ quy ngắn hơn đáng kể so với vòng lặp.
- Bài học này về trạng thái cơ sở và trạng thái đệ quy, cách truy vết gọi đệ quy, và ngăn xếp gọi đang hoạt động như thế nào bên dưới.
Hai trạng thái
FUNCTION Factorial(n : INTEGER) RETURNS INTEGER
IF n = 0 OR n = 1 THEN
RETURN 1 // base case
ELSE
RETURN n * Factorial(n - 1) // recursive case
ENDIF
ENDFUNCTION
- Trạng thái cơ sở là phiên bản bài toán đủ nhỏ để trả lời trực tiếp, không cần gọi thêm. Đây là yếu tố dừng đệ quy.
- Trạng thái đệ quy gọi lại hàm với đầu vào nhỏ hơn, tiến gần đến trạng thái cơ sở.
- Cả hai đều bắt buộc. Đệ quy không có trạng thái cơ sở sẽ không bao giờ dừng; một đệ quy không thu hẹp đầu vào sẽ không bao giờ đạt đến trạng thái cơ sở.
Mỗi thuật toán đệ quy bắt buộc phải có base case bởi vì:
Difficulty 1/5 · 100 coins + a small bonus on first completion today
Base case là điều kiện chấm dứt chuỗi lời gọi; không có nó thì đệ quy chạy mãi mãi.
Đệ quy là sự phù hợp tự nhiên cho các bài toán tự tương đồng (cây, chia để trị), nhưng mỗi lời gọi thêm một khung stack — nên nếu không có base case thì sẽ tràn stack.
Difficulty 1/5 · 100 coins + a small bonus on first completion today
Một vòng lặp đếm đơn giản sạch sẽ hơn cho lặp thông thường; đệ quy nổi bật khi bài toán chứa các bản sao nhỏ hơn của chính nó.
Hàm đệ quy cần có gì để kết thúc? Chọn tất cả các đáp án áp dụng.
Difficulty 2/5 · 140 coins + a small bonus on first completion today
Base case payload không đủ: nếu đầu vào không bao giờ co lại, base case sẽ không bao giờ được chạm đến và các frame chất đống cho đến khi stack tràn.
Ví dụ minh họa: truy vết đệ quy
- Truy vết
Factorial(4). - Winding up:
Factorial(4)needs4 * Factorial(3), which needs3 * Factorial(2), which needs2 * Factorial(1). Nothing has been multiplied yet; each call is waiting. - Trạng thái cơ sở:
Factorial(1)trả về 1 mà không gọi bất kỳ thứ gì. - Mở cuộn:
2 * 1 = 2được trả về, sau đó là3 * 2 = 6, rồi4 * 6 = 24. - Hiển thị cả hai hướng. Truy vết chỉ đi xuống hoặc chỉ quay lại sẽ mất một nửa điểm số.
Đệ quy mở rộng từ các lá lên trên
Bước qua fib(4) theo thứ tự các lời gọi thực sự hoàn thành: các lá (trường hợp cơ bản) được giải quyết trước, sau đó mỗi cha kết hợp con cái của nó. Lưu ý fib(2) được tính hai lần — công việc lặp lại đó là lý do tại sao đệ quy thô sơ lại chậm.
Factorial(4) trả về giá trị gì?
Difficulty 2/5 · 140 coins + a small bonus on first completion today
4 × 3 × 2 × 1 = 24.
Máy tính đang làm gì
- Mỗi lần gọi cần bản sao riêng của tham số và biến cục bộ, vì
Factorial(3)vàFactorial(2)là các lần gọi khác nhau với các giá trịnkhác nhau. - Những bản sao sống trong một khung ngăn xếp trên ngăn xếp gọi: một khung cho mỗi lần gọi đang thực thi, chứa tham số, biến cục bộ và địa chỉ trả về.
- Một khung được đẩy vào mỗi lần gọi và lấy ra khi trả về. Đó là lý do các giá trị quay lại theo thứ tự ngược lại với thứ tự gọi: ngăn xếp gọi là một ngăn xếp, đúng như ADT từ chủ đề 10.
Sắp xếp các sự kiện đánh giá Factorial(4) theo thứ tự.
Difficulty 3/5 · 200 coins + a small bonus on first completion today
Không có phép nhân nào diễn ra khi đi xuống; mọi lời gọi đều chờ đợi. Các phép nhân diễn ra tất cả khi stack được mở rộng.
Điều gì sai lầm
- Không có trạng thái cơ sở, hoặc trạng thái cơ sở không bao giờ được chạm tới: đệ quy không bao giờ dừng, các khung chất đống lên, và ngăn xếp gọi hết bộ nhớ. Đó là tràn ngăn xếp.
- Đệ quy sâu: ngay cả đệ quy đúng đắn mức triệu cấp cũng cần triệu khung, nên có thể cạn kiệt bộ nhớ trong khi vòng lặp sẽ không tốn gì.
- Công việc lặp lại: Fibonacci đệ quy thô sơ tính lại cùng các giá trị theo cấp số mũ. Sửa bằng vòng lặp, hoặc bằng ghi nhớ, lưu từng kết quả lần đầu tiên tính toán.
Khớp mỗi thuật ngữ đệ quy với ý nghĩa của nó.
Difficulty 2/5 · 140 coins + a small bonus on first completion today
Đệ quy cần base case để dừng và recursive case để thu gọn bài toán; mỗi lời gọi thêm một stack frame.
Một stack frame cho một lời gọi hàm chứa:
Difficulty 1/5 · 100 coins + a small bonus on first completion today
Mỗi khung lưu tham số, biến cục bộ và nơi tiếp tục thực thi của cuộc gọi đó — để các cuộc gọi không ghi đè lên nhau.
Mỗi cuộc gọi đang thực thi giữ tham số và biến cục bộ của nó trong một ____ riêng trên ngăn xếp cuộc gọi.
Difficulty 1/5 · 100 coins + a small bonus on first completion today
Được đẩy vào khi gọi, bị loại bỏ khi trả về. Đó là lý do tại sao giá trị quay lại theo thứ tự ngược lại so với thứ tự các cuộc gọi được thực hiện.
Đệ quy hay lặp
- Đệ quy phù hợp với các bài toán tự tương đồng, nơi bài toán chứa một bản sao nhỏ hơn của chính nó: duyệt cây, chia để trị như tìm kiếm nhị phân và merge sort, và chuỗi tổ tiên ở trên.
- Lặp phù hợp với mọi thứ khác, và sử dụng không bộ nhớ bổ sung cho sự lặp lại.
- Mọi thứ đệ quy đều có thể viết theo kiểu lặp và ngược lại. Sự lựa chọn phụ thuộc vào cái nào biểu đạt bài toán rõ ràng hơn, cân nhắc với bộ nhớ mà ngăn xếp tốn kém.
Một thủ tục đệ quy bị lỗi tràn ngăn xếp (stack overflow). Giải thích nào sau đây là đúng?
Difficulty 1/5 · 100 coins + a small bonus on first completion today
Tràn ngăn xếp liên quan đến các khung, không phải phép toán. Một con số quá lớn so với thanh ghi là tràn phép toán, một vấn đề hoàn toàn khác.
Ví dụ minh họa: nêu rủi ro
- Một học sinh viết thủ tục đệ quy và gặp tràn ngăn xếp. Nêu hai nguyên nhân có thể.
- Không có trạng thái cơ sở, hoặc trạng thái cơ sở không bao giờ đạt được vì đầu vào không giảm dần qua mỗi lần gọi, nên các cuộc gọi tiếp diễn mãi mãi và các khung tích lũy.
- Đệ quy đúng nhưng quá sâu: mỗi lần gọi rất nhiều giữ khung ngăn xếp riêng, và ngăn xếp gọi hết bộ nhớ trước khi đạt đến trạng thái cơ sở.
- Cả hai nguyên nhân đều liên quan đến việc các khung tích lũy. Hãy nói những gì tích lũy và tại sao nó không bao giờ dừng.
Điểm số dễ mất
- Đệ quy cần cả trạng thái cơ sở và đầu vào giảm dần. Chỉ nêu trạng thái cơ sở mới là một nửa điều kiện.
- Trong truy vết, hiển thị các cuộc gọi đóng cuộn và các giá trị mở cuộn. Cả hai hướng đều mang điểm số.
- Mỗi cuộc gọi có tham số và biến cục bộ riêng của nó, trong khung ngăn xếp riêng. Đó là lý do đệ quy tốn bộ nhớ mà lặp không tốn.
- Tràn ngăn xếp là hết bộ nhớ ngăn xếp do quá nhiều khung, không phải tràn số học.
Bạn đã nắm vững
- một thủ tục đệ quy cần một trạng thái cơ sở giải quyết trực tiếp và một trạng thái đệ quy gọi chính nó với đầu vào nhỏ hơn
- truy vết theo cả hai hướng: các cuộc gọi đóng cuộn đến trạng thái cơ sở, sau đó các giá trị mở cuộn quay lại
- mỗi cuộc gọi có khung ngăn xếp riêng trên ngăn xếp gọi, được đẩy vào khi gọi và lấy ra khi trả về, đó là lý do đệ quy tốn bộ nhớ
- rủi ro: không có trường hợp cơ sở nào có thể truy cập được dẫn đến đệ quy vô hạn và tràn bộ nhớ đệm (stack overflow), đệ quy sâu tiêu thụ bộ nhớ, và công việc lặp lại đòi hỏi vòng lặp hoặc ghi nhớ (memoisation)