Đệ quy: trường hợp cơ bản và trường hợp đệ quy
Một phương thức gọi chính nó
- Đệ quy là khi một phương thức gọi chính nó để giải quyết một phần nhỏ hơn của cùng vấn đề.
- Trong kỳ thi AP CSA, bạn chủ yếu vẽ sơ đồ (trace) đệ quy (theo dõi các lời gọi bằng tay). Viết các phương thức đệ quy nhỏ giúp bạn vẽ sơ đồ tốt hơn.
- Mọi phương thức đệ quy đều cần hai phần: một trường hợp cơ sở và một trường hợp đệ quy.
Trường hợp cơ sở và trường hợp đệ quy
- Trường hợp cơ sở: đầu vào đơn giản nhất, nơi bạn trả về kết quả không gọi chính mình. Điều này dừng quá trình đệ quy.
- Trường hợp đệ quy: bạn gọi chính phương thức đó với đầu vào nhỏ hơn, sau đó xây dựng kết quả.
- Nếu không có trường hợp cơ sở, phương thức sẽ gọi mãi mãi và gây lỗi (quá tải stack - stack overflow).
Ví dụ: Giai thừa
factorial(n)biểu thịn * (n-1) * ... * 1. Ví dụ nhưfactorial(4) = 24.- Trường hợp cơ sở:
factorial(1)là1. - Trường hợp quy hồi:
factorial(n)làn * factorial(n - 1).
public class Recursion {
public static int factorial(int n) {
if (n <= 1) { // base case
return 1;
}
return n * factorial(n - 1); // recursive case
}
}
Cách các cuộc gọi hoàn tác
- Mỗi cuộc gọi chờ cuộc gọi nhỏ hơn hoàn thành. Sau đó nhân và trả về kết quả.
- Theo dõi
factorial(3). Các cuộc gọi đi xuống, sau đó các câu trả lời quay lại lên trên.
factorial(3) = 3 * factorial(2) <- waits
factorial(2) = 2 * factorial(1) <- waits
factorial(1) = 1 <- base case, returns 1
factorial(2) = 2 * 1 = 2 <- returns 2
factorial(3) = 3 * 2 = 6 <- returns 6
Ví dụ: tổng đến n
sumTo(n)cộng1 + 2 + ... + n. Ví dụsumTo(4) = 10.- Trường hợp cơ sở:
sumTo(0)là0(không có gì để cộng). - Trường hợp quy hồi:
sumTo(n)làn + sumTo(n - 1).
public class Recursion {
public static int sumTo(int n) {
if (n <= 0) { // base case
return 0;
}
return n + sumTo(n - 1); // recursive case
}
}
Quy hồi qua mảng
- Chúng ta cũng có thể thực hiện quy hồi với một chỉ số di chuyển về phía cuối.
- Trường hợp cơ sở: khi chỉ số ở quá vị trí cuối cùng, trả về
0. - Trường hợp quy hồi: cộng
a[i]vào tổng của phần còn lại,arraySum(a, i + 1).
public class Recursion {
public static int arraySum(int[] a, int i) {
if (i >= a.length) { // base case: past the end
return 0;
}
return a[i] + arraySum(a, i + 1);
}
}
- Để tính tổng toàn bộ mảng, bạn bắt đầu từ chỉ số
0:arraySum(a, 0). - Mỗi cuộc gọi xử lý một giá trị và tin tưởng cuộc gọi tiếp theo cho phần còn lại.
Lỗi thường gặp
- Quy hồi cần một trường hợp cơ sở, nếu không sẽ gây ra StackOverflowError.
- Mỗi lần gọi phải tiến gần hơn đến trường hợp cơ sở.
Bây giờ bạn thử
- Mỗi bài tập cung cấp cho bạn một khung phương thức có TODO. Viết cả trường hợp cơ sở và trường hợp quy hồi.
- Một ** Harness** ẩn gọi phương thức của bạn với nhiều giá trị và kiểm tra kết quả.
- Sử dụng Check answer để biên dịch mã của bạn với các bài kiểm tra được cung cấp và xem kết quả. Giữ nguyên giao diện class và phương thức được hiển thị trong file khởi tạo.
Đệ quy: trường hợp cơ bản + trường hợp đệ quy
Các lời gọi tách ra cho đến khi đạt đến một trường hợp cơ bản, sau đó các kết quả sẽ được trả ngược lên trên.
Độ khó 4/5 · 280 xu + phần thưởng nhỏ khi hoàn thành lần đầu tiên hôm nay
Hoàn thiện factorial(int n) sao cho trả về n * (n-1) * ... * 1 bằng đệ quy. Sử dụng trường hợp cơ sở cho n <= 1. Bộ kiểm tra sẽ thử nhiều giá trị khác nhau.
Nhấn Chạy để xem kết quả ở đây.
Độ khó 4/5 · 280 xu + phần thưởng nhỏ khi hoàn thành lần đầu tiên hôm nay
Hoàn thiện sumTo(int n) sao cho trả về 1 + 2 + ... + n bằng đệ quy. Sử dụng trường hợp cơ sở cho n <= 0. Bộ kiểm tra sẽ thử nhiều giá trị khác nhau.
Nhấn Chạy để xem kết quả ở đây.
Độ khó 4/5 · 280 xu + phần thưởng nhỏ khi hoàn thành lần đầu tiên hôm nay
Hoàn thành arraySum(int[] a, int i) để trả về tổng từ a[i] đến cuối, sử dụng đệ quy. Trường hợp cơ bản: khi i vượt qua vị trí cuối cùng, hãy trả về 0. Bộ kiểm tra sẽ thử nghiệm với nhiều mảng.
Nhấn Chạy để xem kết quả ở đây.