Những con búp bê lồng nhau#
Một bộ búp bê lồng nhau: mở con búp bê lớn ra và bên trong có một con nhỏ hơn một chút, cùng hình dạng. Mở con đó ra, và có một con khác. Bạn cứ tiếp tục cho đến khi tới con búp bê bé xíu ở giữa, đặc ruột và không mở ra được. Khi đó bạn xong.
Đệ quy (recursion) là như vậy. Một phương thức đệ quy là phương thức tự gọi chính nó, mỗi lần trên một phiên bản nhỏ hơn của bài toán, cho đến khi đạt tới một phiên bản nhỏ đến mức câu trả lời là hiển nhiên. Con búp bê nhỏ nhất, đặc ruột đó là trường hợp cơ sở (base case): trường hợp mà phương thức trả lời trực tiếp, không gọi lại chính nó. Mọi trường hợp khác là trường hợp đệ quy, hay trường hợp tổng quát.
Cấu trúc điển hình#
Hầu như mọi phương thức đệ quy trong khóa học này đều có cùng hình dạng hai phần:
returnType solve(problem) {
if (problem is small enough) { // base case
return the simple answer;
} else { // recursive case
return combine(something, solve(a smaller problem));
}
}
Trường hợp cơ sở được kiểm tra trước. Nếu thiếu nó, hoặc nếu bài toán thật ra không bao giờ nhỏ đi, phương thức sẽ gọi chính nó mãi mãi. Mỗi lời gọi chiếm bộ nhớ trên ngăn xếp lời gọi (call stack), chồng các lời gọi phương thức đang chờ kết thúc, và Java sớm hết chỗ:
public class Forever {
public static int countDown(int n) {
return countDown(n - 1);
}
public static void main(String[] args) {
try {
countDown(10);
} catch (StackOverflowError e) {
System.out.println("Stopped by " + e.getClass().getSimpleName());
}
}
}
Stopped by StackOverflowError
StackOverflowError là một Error, không phải một Exception: chính máy ảo Java đã hết chỗ. Các chương trình thật không bắt nó; đoạn mã chỉ làm vậy để hiển thị tên của nó thay vì một dấu vết ngăn xếp dài cả nghìn dòng. Cách sửa luôn giống nhau: một trường hợp cơ sở đúng, và một lời gọi đệ quy tiến về phía nó.
Bốn câu hỏi để xây dựng lời giải đệ quy#
Một danh sách kiểm tra được dạy rộng rãi, từ giáo trình Data Abstraction and Problem Solving with Java: Walls and Mirrors của Prichard và Carrano, biến việc viết một phương thức đệ quy thành bốn câu hỏi. Theo cách nói của chúng tôi, hãy hỏi chúng theo thứ tự này:
- Tôi có thể mô tả bài toán bằng một bản sao nhỏ hơn của đúng bài toán đó không? Với giai thừa: 5! là 5 × 4!.
- Mỗi lời gọi đệ quy làm bài toán nhỏ đi như thế nào? Con số giảm đi 1 mỗi lần.
- Phiên bản nào của bài toán đủ nhỏ để trả lời trực tiếp, làm trường hợp cơ sở? 0! là 1, biết mà không cần làm gì.
- Khi bài toán thu nhỏ, nó chắc chắn đạt tới trường hợp cơ sở chứ? Bắt đầu từ bất kỳ n ≥ 0 nào và trừ 1 luôn đạt tới 0. (Một n âm thì không, đó là lý do phương thức nên từ chối nó.)
Nếu bạn trả lời được cả bốn, phương thức gần như tự viết ra. Nếu bạn không trả lời được câu thứ tư, bạn đã tìm ra đệ quy vô hạn của mình trước khi chạy.
Giai thừa, và quan sát ngăn xếp#
Giai thừa: n! là n × (n − 1) × … × 1, và 0! là 1. Điều đó chuyển thẳng thành hình dạng hai phần. Phiên bản dưới đây thêm các câu lệnh in để bạn quan sát mỗi lời gọi chờ lời gọi bên trong nó:
public class Factorial {
public static long factorial(int n, String indent) {
System.out.println(indent + "factorial(" + n + ") called");
long result;
if (n == 0) {
result = 1;
} else {
result = n * factorial(n - 1, indent + " ");
}
System.out.println(indent + "factorial(" + n + ") returns " + result);
return result;
}
public static void main(String[] args) {
System.out.println("4! = " + factorial(4, ""));
}
}
factorial(4) called
factorial(3) called
factorial(2) called
factorial(1) called
factorial(0) called
factorial(0) returns 1
factorial(1) returns 1
factorial(2) returns 2
factorial(3) returns 6
factorial(4) returns 24
4! = 24
Hãy đọc đầu ra thành hai nửa. Khi đi xuống, mỗi lời gọi bị tạm dừng, chờ câu trả lời của một lời gọi nhỏ hơn: factorial(4) không thể nhân cho đến khi biết factorial(3). Đó là ngăn xếp đang cuộn vào. Tại trường hợp cơ sở, các câu trả lời bắt đầu quay lên, mỗi lời gọi hoàn tất phép nhân của nó và đưa kết quả cho lời gọi đang chờ nó. Đó là ngăn xếp đang tháo ra. Lời gọi bắt đầu sau cùng là lời gọi kết thúc đầu tiên, như một chồng đĩa.
ƯCLN: thuật toán Euclid#
Ước chung lớn nhất của hai số là số lớn nhất chia hết cả hai: ƯCLN của 48 và 18 là 6. Euclid đã tìm ra một lối tắt cách đây hơn hai nghìn năm: ƯCLN của a và b bằng ƯCLN của b và phần dư của a ÷ b. Cứ tiếp tục cho đến khi phần dư là 0; số còn lại là đáp án.
public class Gcd {
public static int gcd(int a, int b) {
System.out.println("gcd(" + a + ", " + b + ")");
if (b == 0) {
return a;
}
return gcd(b, a % b);
}
public static void main(String[] args) {
System.out.println("Answer: " + gcd(48, 18));
}
}
gcd(48, 18)
gcd(18, 12)
gcd(12, 6)
gcd(6, 0)
Answer: 6
Bốn lời gọi để trả lời câu hỏi. Trường hợp cơ sở là b == 0, và bài toán thu nhỏ vì phần dư luôn nhỏ hơn số bạn đã chia cho. Đây là ví dụ ƯCLN của khóa học; dò nó trên giấy, mỗi lời gọi một dòng, là một câu hỏi bài thi có khả năng xuất hiện.
Fibonacci, và cái giá của việc gọi hai lần#
Các số Fibonacci bắt đầu 0, 1, và mỗi số sau là tổng của hai số trước: 0, 1, 1, 2, 3, 5, 8, 13… Định nghĩa vốn đã là đệ quy, với hai trường hợp cơ sở:
public class Fib {
static long calls = 0;
public static long fib(int n) {
calls++;
if (n == 0) {
return 0;
}
if (n == 1) {
return 1;
}
return fib(n - 1) + fib(n - 2);
}
public static long fibLoop(int n) {
long prev = 0, curr = 1;
for (int i = 1; i < n; i++) {
long next = prev + curr;
prev = curr;
curr = next;
}
return n == 0 ? 0 : curr;
}
public static void main(String[] args) {
for (int n = 0; n <= 7; n++) {
System.out.print(fib(n) + " ");
}
System.out.println();
for (int n : new int[] {10, 20, 25}) {
calls = 0;
long value = fib(n);
System.out.println("fib(" + n + ") = " + value + " took " + calls + " calls");
}
System.out.println("Loop version: fib(20) = " + fibLoop(20));
}
}
0 1 1 2 3 5 8 13
fib(10) = 55 took 177 calls
fib(20) = 6765 took 21891 calls
fib(25) = 75025 took 242785 calls
Loop version: fib(20) = 6765
Nó đúng, và chậm một cách đáng kinh ngạc. Mỗi lời gọi tạo thêm hai lời gọi, và chúng lặp lại công việc của nhau: fib(20) cần fib(19) và fib(18), nhưng fib(19) tính lại fib(18) từ đầu. Số lời gọi ở trên cho thấy kết quả: 21.891 lời gọi để tìm số thứ 20, và mỗi bước lên làm công việc nhân thêm khoảng 1.6. Vòng lặp ở cuối tính cùng con số đó trong 19 lượt. Đệ quy ở đây thanh lịch nhưng là công cụ sai.
Tìm kiếm nhị phân#
Để tìm một từ trong từ điển in, bạn không bắt đầu từ trang một. Bạn mở ra giữa, xem từ của bạn đứng trước hay sau, và bỏ đi nửa mà nó không thể nằm trong. Rồi bạn lặp lại trên nửa còn lại. Đó là tìm kiếm nhị phân (binary search), và nó chỉ hoạt động trên một mảng đã sắp xếp.
public class BinSearch {
public static int search(int[] arr, int target, int low, int high) {
if (low > high) {
return -1;
}
int mid = (low + high) / 2;
System.out.println(" looking at index " + mid + " (value " + arr[mid] + ") in " + low + ".." + high);
if (arr[mid] == target) {
return mid;
} else if (target < arr[mid]) {
return search(arr, target, low, mid - 1);
} else {
return search(arr, target, mid + 1, high);
}
}
public static void main(String[] args) {
int[] sorted = {3, 8, 15, 21, 34, 42, 57, 68, 79, 91};
System.out.println("Searching for 57:");
System.out.println("Found at " + search(sorted, 57, 0, sorted.length - 1));
System.out.println("Searching for 10:");
System.out.println("Found at " + search(sorted, 10, 0, sorted.length - 1));
}
}
Searching for 57:
looking at index 4 (value 34) in 0..9
looking at index 7 (value 68) in 5..9
looking at index 5 (value 42) in 5..6
looking at index 6 (value 57) in 6..6
Found at 6
Searching for 10:
looking at index 4 (value 34) in 0..9
looking at index 1 (value 8) in 0..3
looking at index 2 (value 15) in 2..3
Found at -1
Hai trường hợp cơ sở: phần tử ở giữa là mục tiêu (trả về chỉ số của nó), hoặc phạm vi rỗng, low > high (trả về −1, không tìm thấy). Mỗi lời gọi đệ quy chỉ giữ một nửa phạm vi, nên một mảng đã sắp xếp một triệu phần tử mất tối đa khoảng 20 lần xem. So sánh với tìm kiếm tuyến tính từ bài hướng dẫn về mảng, có thể phải kiểm tra cả triệu phần tử.
Tháp Hà Nội#
Ba cọc, và một chồng đĩa ở cọc đầu, đĩa lớn nhất ở dưới. Di chuyển cả chồng sang cọc thứ ba. Quy tắc: mỗi lần di chuyển một đĩa, và không bao giờ đặt đĩa lớn hơn lên đĩa nhỏ hơn.
Cái nhìn đệ quy: để di chuyển n đĩa từ A sang C, trước hết di chuyển n − 1 đĩa trên cùng ra chỗ khác sang B, rồi di chuyển đĩa lớn nhất từ A sang C, rồi di chuyển n − 1 đĩa từ B lên trên nó. Các bước “di chuyển n − 1 đĩa” là cùng một bài toán, nhỏ hơn một đĩa. Trường hợp cơ sở là một đĩa: chỉ việc di chuyển nó.
public class Hanoi {
static int moves = 0;
public static void solve(int n, char from, char spare, char to) {
if (n == 1) {
moves++;
System.out.println(moves + ". disc 1 from " + from + " to " + to);
return;
}
solve(n - 1, from, to, spare);
moves++;
System.out.println(moves + ". disc " + n + " from " + from + " to " + to);
solve(n - 1, spare, from, to);
}
public static void main(String[] args) {
solve(3, 'A', 'B', 'C');
System.out.println(moves + " moves");
}
}
1. disc 1 from A to C
2. disc 2 from A to B
3. disc 1 from C to B
4. disc 3 from A to C
5. disc 1 from B to A
6. disc 2 from B to C
7. disc 1 from A to C
7 moves
Ba đĩa mất 7 nước đi. Tổng quát, n đĩa mất 2n − 1 nước đi, đó là lý do truyền thuyết của câu đố về 64 chiếc đĩa vàng cần hơn 580 tỷ năm với một nước đi mỗi giây. Có một lời giải bằng vòng lặp, nhưng nó khó viết và khó hiểu hơn nhiều: đây là bài toán mà đệ quy thắng rõ ràng.
Đệ quy so với vòng lặp#
Vòng lặp (iteration) nghĩa là lặp lại bằng một vòng lặp. Bất cứ thứ gì một phương thức đệ quy làm được, một vòng lặp cũng làm được, đôi khi với sự giúp đỡ của ngăn xếp riêng của bạn. Vì vậy lựa chọn là về độ rõ ràng và chi phí:
| Đệ quy | Vòng lặp | |
|---|---|---|
| Dừng khi | đạt tới trường hợp cơ sở | điều kiện vòng lặp trở thành false |
| Bộ nhớ | một khung ngăn xếp cho mỗi lời gọi đang chờ | vài biến, bất kể bao nhiêu lượt |
| Nếu quy tắc dừng sai | StackOverflowError | một vòng lặp vô hạn |
| Tốc độ | chậm hơn: mỗi lời gọi có chi phí phụ | thường nhanh hơn |
| Phù hợp nhất với | các bài toán tách thành các bản sao nhỏ hơn của chính chúng: Hà Nội, dữ liệu dạng cây, chia để trị | lặp lại đơn giản: tổng, đếm, duyệt một mảng |
Giai thừa và ƯCLN gọn gàng theo cả hai cách. Fibonacci cho thấy đệ quy làm ngây thơ có thể chậm một cách thảm họa. Hà Nội cho thấy đệ quy có thể biến một bài toán khó thành ba dòng. Hãy chọn đệ quy khi nó làm lời giải rõ ràng hơn và độ sâu của các lời gọi vẫn khiêm tốn.
Mọi phương thức đệ quy cần một trường hợp cơ sở được kiểm tra trước, và một lời gọi đệ quy trên bài toán nhỏ hơn được đảm bảo đạt tới nó. Các lời gọi chồng lên nhau trên ngăn xếp trên đường đi xuống và kết thúc theo thứ tự ngược lại trên đường đi lên.
Những chỗ dễ sai#
- Không có trường hợp cơ sở, hoặc có nhưng không bao giờ đạt tới. Kết quả là một
StackOverflowError, phiên bản của vòng lặp vô hạn trong đệ quy. - Một lời gọi đệ quy không làm bài toán nhỏ đi.
factorial(n)gọifactorial(n)chạy mãi mãi. Nó phải làn - 1. - Quên
returnở lời gọi đệ quy. Viếtgcd(b, a % b);mà không córeturnsẽ vứt câu trả lời đi (và một phương thức không phải void sẽ không biên dịch được). - Kiểm tra trường hợp cơ sở sau lời gọi đệ quy. Lời gọi xảy ra trước và không bao giờ dừng. Trường hợp cơ sở đặt ở trên cùng.
- Tìm kiếm nhị phân trên một mảng chưa sắp xếp. Bỏ đi một nửa chỉ hoạt động khi thứ tự cho bạn biết nửa nào.
- Dùng Fibonacci đệ quy thuần túy cho n lớn. Các lời gọi lặp lại tăng theo hàm mũ. Hãy dùng một vòng lặp.
- Dò đầu ra của một phương thức đệ quy chỉ theo thứ tự lời gọi. Bất cứ thứ gì được in sau lời gọi đệ quy xuất hiện theo thứ tự ngược, khi ngăn xếp tháo ra.
Luyện tập#
Hãy trả lời từng câu trên giấy trước khi xem lời giải. Mọi đáp án có chạy mã đều đã được kiểm tra bằng cách biên dịch và chạy mã đó.
- Hãy định nghĩa đệ quy, trường hợp cơ sở và trường hợp đệ quy, mỗi cái một câu.
- Viết một phương thức đệ quy
sumTo(n)trả về 1 + 2 + … + n, vớisumTo(0)trả về 0. Hãy trả lời bốn câu hỏi cho nó. mystery("stack")trả về gì?public static String mystery(String s) { if (s.length() <= 1) { return s; } return mystery(s.substring(1)) + s.charAt(0); }- Dò
gcd(84, 36)bằnggcd(a, b) = gcd(b, a % b)với trường hợp cơ sởb == 0. - Tìm kiếm nhị phân số 15 trong
{3, 8, 15, 21, 34, 42, 57, 68, 79, 91}. Những chỉ số nào được xem, và giá trị nào được trả về? - Viết một
power(base, exp)đệ quy cho số mũ nguyên từ 0 trở lên. Tháp Hà Nội cần bao nhiêu nước đi với 5 đĩa?
Lời giải#
- Đệ quy là một phương thức giải một bài toán bằng cách tự gọi chính nó trên một phiên bản nhỏ hơn của cùng bài toán. Trường hợp cơ sở là phiên bản đủ nhỏ để trả lời trực tiếp, không cần một lời gọi nữa. Trường hợp đệ quy là mọi phiên bản khác, gọi lại phương thức trên thứ gì đó gần trường hợp cơ sở hơn.
- Bài toán nhỏ hơn:
sumTo(n)làn + sumTo(n - 1). Mỗi lời gọi thu nhỏ n đi 1. Trường hợp cơ sở:sumTo(0)là 0. Bắt đầu từ bất kỳ n ≥ 0 nào, trừ 1 luôn đạt tới 0.public class QSum { public static int sumTo(int n) { if (n == 0) { return 0; } return n + sumTo(n - 1); } public static void main(String[] args) { System.out.println(sumTo(5)); System.out.println(sumTo(100)); } }15 5050 - Mỗi lời gọi đặt ký tự đầu tiên của nó sau kết quả của phần còn lại của String, nên các ký tự quay lại theo thứ tự ngược:
public class QMystery { public static String mystery(String s) { if (s.length() <= 1) { return s; } return mystery(s.substring(1)) + s.charAt(0); } public static void main(String[] args) { System.out.println(mystery("stack")); } }kcats - gcd(84, 36) → gcd(36, 12), vì 84 % 36 là 12 → gcd(12, 0), vì 36 % 12 là 0 → trường hợp cơ sở, đáp án là 12.
- low 0, high 9: mid 4 (34). 15 nhỏ hơn, nên tìm 0..3: mid 1 (8). 15 lớn hơn, nên tìm 2..3: mid 2 (15). Tìm thấy: nó trả về 2. Ba phần tử được xem.
- Trường hợp cơ sở: bất cứ thứ gì mũ 0 đều là 1. Trường hợp đệ quy:
base * power(base, exp - 1).public class QPower { public static long power(int base, int exp) { if (exp == 0) { return 1; } return base * power(base, exp - 1); } public static void main(String[] args) { System.out.println(power(2, 10)); System.out.println(power(3, 4)); System.out.println(power(7, 0)); } }
Với Hà Nội, n đĩa mất 2n − 1 nước đi, nên 5 đĩa mất 25 − 1 = 31.1024 81 1
Danh sách kiểm tra trước khi thi#
Đây là các mục trong danh sách chủ đề Bài thi 2 của môn học mà bài hướng dẫn này đề cập. Chỉ đánh dấu mỗi mục khi bạn làm được mà không cần nhìn.
- ☐ Tôi có thể đưa ra định nghĩa của đệ quy và xác định trường hợp cơ sở.
- ☐ Tôi có thể viết một phương thức đệ quy theo cấu trúc điển hình: trường hợp cơ sở trước, rồi một lời gọi đệ quy nhỏ hơn.
- ☐ Tôi có thể dùng bốn câu hỏi để xây dựng lời giải đệ quy.
- ☐ Tôi có thể so sánh vòng lặp với đệ quy và nói khi nào mỗi cái là lựa chọn tốt hơn.
- ☐ Tôi có thể viết và dò các ví dụ: giai thừa, ƯCLN, các số Fibonacci, tìm kiếm nhị phân và Tháp Hà Nội.
Tự kiểm tra trong ứng dụng Kestrel Exams miễn phí
40 câu hỏi luyện tập về trường hợp cơ sở, dò đệ quy và ngăn xếp lời gọi, mọi đáp án mã đều đã được kiểm tra bằng cách biên dịch và chạy. Miễn phí, dùng được khi không có mạng, không cần tài khoản.
Luyện tập đệ quy →Câu hỏi thường gặp#
Đệ quy trong Java là gì?
Đệ quy là một kỹ thuật trong đó một phương thức tự gọi chính nó để giải một phiên bản nhỏ hơn của cùng một bài toán. Một phương thức đệ quy có một trường hợp cơ sở, mà nó trả lời trực tiếp, và một trường hợp đệ quy, gọi lại phương thức trên một đầu vào nhỏ hơn tiến về phía trường hợp cơ sở.
Trường hợp cơ sở trong đệ quy là gì?
Trường hợp cơ sở là phiên bản đơn giản nhất của bài toán, mà phương thức trả lời mà không tự gọi chính nó, chẳng hạn factorial(0) trả về 1. Nó dừng đệ quy. Nếu không có trường hợp cơ sở nào có thể đạt tới, một phương thức đệ quy tự gọi chính nó cho đến khi chương trình thất bại với StackOverflowError.
Bốn câu hỏi để xây dựng lời giải đệ quy là gì?
Diễn giải lại, từ giáo trình Walls and Mirrors của Prichard và Carrano: bài toán có thể được mô tả bằng một bản sao nhỏ hơn của chính bài toán đó không; mỗi lời gọi đệ quy làm bài toán nhỏ đi như thế nào; phiên bản nào đủ nhỏ để trả lời trực tiếp làm trường hợp cơ sở; và, khi bài toán thu nhỏ, có chắc chắn đạt tới trường hợp cơ sở đó không?
Vì sao Fibonacci đệ quy chậm đến vậy?
Vì mỗi lời gọi tạo thêm hai lời gọi lặp lại công việc của nhau. Tính fib(20) bằng đệ quy mất 21.891 lời gọi, và số lượng tăng theo hệ số khoảng 1.6 cho mỗi lần n tăng thêm. Một vòng lặp tính cùng giá trị đó trong khoảng n bước.
Đệ quy và vòng lặp khác nhau như thế nào?
Vòng lặp (iteration) lặp lại bằng một vòng lặp và dừng khi điều kiện vòng lặp trở thành false; đệ quy lặp lại bằng các lời gọi phương thức và dừng ở trường hợp cơ sở. Đệ quy dùng một khung ngăn xếp (stack frame) cho mỗi lời gọi đang chờ và thường chậm hơn, nhưng cho lời giải rõ ràng hơn nhiều với những bài toán tách thành các bản sao nhỏ hơn của chính nó, như Tháp Hà Nội.
Tháp Hà Nội cần bao nhiêu nước đi?
Giải câu đố với n đĩa cần tối thiểu 2^n - 1 nước đi: 7 nước cho 3 đĩa, 31 cho 5 đĩa, và 1.023 cho 10 đĩa.
Có chỗ nào chưa rõ? Có chủ đề nào bạn muốn chúng tôi viết? Hãy cho chúng tôi biết. Chúng tôi đọc mọi tin nhắn, và một lời đề nghị là cách nhanh nhất để có bài hướng dẫn mới: một số bài ở đây ra đời vì có người hỏi.