Đến nội dung chính
notes.vinhnq.com

Tìm kiếm

Cấu trúc dữ liệu & Thuật toánMid22 phút đọc

Đệ quy, tìm kiếm nhị phân và các thuật toán thông dụng

Ôn 19 thẻ
Trong bài này

Cụm bài Thuật toán cơ bản: 1. Big-O và sắp xếp O(n²) · 2. Đệ quy và tìm kiếm nhị phân · 3. Merge sort, quick sort

Bài này giúp bạn viết đệ quy đúng (base case, truy hồi), biết khi nào nó làm tràn stack JVM, và tăng tốc bằng memoization. Sau đó là tìm kiếm tuyến tính, nhị phân cùng bug tràn số ở mid, và ba bài hay gặp khi phỏng vấn: số nguyên tố, Fibonacci, palindrome. Nên đọc phần 1 trước để quen Big-O; đệ quy ở đây là nền cho merge sort và quick sort ở phần 3.

1. Đệ quy

Ý chính: một hàm đệ quy gọi lại chính nó với đầu vào nhỏ hơn cho tới base case, rồi gộp kết quả ngược lên. Mỗi tầng tốn một stack frame, nên độ sâu quyết định nó có an toàn trong Java hay không.

1.1. Khái niệm

Đệ quy (recursion) là khi một hàm gọi lại chính nó với đầu vào nhỏ hơn. Một hàm đệ quy đúng cần hai thứ:

  1. Base case (trường hợp cơ sở): trường hợp nhỏ nhất có đáp án ngay, không gọi tiếp. Đây là điều kiện dừng.
  2. Quan hệ truy hồi (recurrence): biểu diễn bài toán qua bài con nhỏ hơn, mỗi lần gọi tiến gần hơn tới base case. Nếu không, đệ quy sẽ vô hạn.

1.2. Các bước giải một bài bằng đệ quy

  1. Định nghĩa hàm f: nhận gì, trả về gì.
  2. Xác định base case.
  3. Xác định quan hệ truy hồi: chia thành các bài con gần base case hơn.
  4. Kết hợp kết quả bài con thành kết quả bài lớn.

1.3. Case study: giai thừa

0! = 1, và n! = n · (n-1)! với n > 0. Base case là n == 0; bài con giống hệt bài gốc, chỉ khác tham số nhỏ hơn.

static long factorial(int n) {
    if (n < 0) throw new IllegalArgumentException("n must be >= 0");
    if (n == 0) return 1;                 // base case
    return n * factorial(n - 1);          // recurrence
}

Dùng long vì int tràn ngay từ 13!; long cũng chỉ chứa tới 20!, lớn hơn cần BigInteger.

factorial(4) = 4 * factorial(3)
             = 4 * 3 * factorial(2)
             = 4 * 3 * 2 * factorial(1)
             = 4 * 3 * 2 * 1 * factorial(0)   <- base case
             = 4 * 3 * 2 * 1 * 1
             = 24

Trên JVM, mỗi lần gọi tạo một stack frame (vùng nhớ chứa tham số, biến cục bộ và địa chỉ trả về). Các frame chồng lên tới base case rồi lần lượt được gỡ ra:

sequenceDiagram
  participant M as main
  participant F4 as factorial(4)
  participant F3 as factorial(3)
  participant F2 as factorial(2)
  participant F1 as factorial(1)
  participant F0 as factorial(0)
  M->>F4: gọi
  F4->>F3: gọi
  F3->>F2: gọi
  F2->>F1: gọi
  F1->>F0: gọi
  F0-->>F1: 1
  F1-->>F2: 1
  F2-->>F3: 2
  F3-->>F4: 6
  F4-->>M: 24

1.4. Đặc điểm của đệ quy

Mọi hàm đệ quy đều có câu rẽ nhánh (if-else, switch) tách base case khỏi trường hợp đệ quy, một hoặc nhiều base case, và mỗi lời gọi làm bài toán nhỏ đi.

1.5. Đệ quy và call stack trong JVM (góc nhìn senior)

1.6. Đệ quy có nhớ (memoization)

1.7. Live coding: Fibonacci và tam giác Pascal

Slide đề xuất hai bài LeetCode để luyện tay:

  • “Fibonacci Number”: cho n, trả về F(n) (F(0) = 0, F(1) = 1). Lời giải ở phần 3.2.
  • “Pascal’s Triangle”: sinh numRows hàng đầu của tam giác Pascal. Mỗi hàng bắt đầu và kết thúc bằng 1, số ở giữa bằng tổng hai số ngay trên nó. Cả bản lặp và bản đệ quy đều O(numRows²), đúng bằng số phần tử phải sinh.
Lời giải Pascal’s Triangle: bản vòng lặp và bản đệ quy
static List<List<Integer>> generate(int numRows) {
    List<List<Integer>> rows = new ArrayList<>();
    for (int r = 0; r < numRows; r++) {
        List<Integer> row = new ArrayList<>(r + 1);
        for (int c = 0; c <= r; c++) {
            if (c == 0 || c == r) row.add(1);
            else row.add(rows.get(r - 1).get(c - 1) + rows.get(r - 1).get(c));
        }
        rows.add(row);
    }
    return rows;   // generate(5) = [[1], [1,1], [1,2,1], [1,3,3,1], [1,4,6,4,1]]
}

Bản đệ quy cho một hàng: base case là hàng 0 = [1], hàng r tính từ hàng r - 1.

static List<Integer> pascalRow(int r) {
    if (r == 0) return List.of(1);
    List<Integer> prev = pascalRow(r - 1);
    List<Integer> row = new ArrayList<>(r + 1);
    row.add(1);
    for (int c = 1; c < r; c++) row.add(prev.get(c - 1) + prev.get(c));
    row.add(1);
    return row;
}

2. Tìm kiếm trong mảng

Ý chính: linear search O(n) chạy trên mọi dữ liệu; binary search O(log n) cần mảng đã sắp xếp và mỗi bước bỏ đi một nửa. Cái bẫy kinh điển là tính mid bị tràn số.

So khoá lần lượt với từng phần tử; khớp thì trả index, hết mảng thì trả -1.

static int linearSearch(int[] a, int key) {
    for (int i = 0; i < a.length; i++)
        if (a[i] == key) return i;
    return -1;
}

Điều kiện: mảng đã sắp xếp (giả sử tăng dần). So key với phần tử giữa: nhỏ hơn thì tìm tiếp nửa trái, lớn hơn thì nửa phải, bằng thì dừng. Ba biến low, high, mid đánh dấu đầu, cuối, giữa đoạn đang xét. Đoạn co một nửa mỗi bước nên O(log n): một triệu phần tử chỉ ~20 lần so sánh.

Hình dung: tra từ điển giấy, mở giữa cuốn rồi bỏ hẳn nửa không chứa từ cần tìm.

flowchart TD
  S["low = 0, high = n - 1"] --> C{"low <= high?"}
  C -- "không" --> NF["không tìm thấy"]
  C -- "có" --> M["mid = (low + high) >>> 1"]
  M --> Q{"so a[mid] với key"}
  Q -- "a[mid] < key" --> R["low = mid + 1"] --> C
  Q -- "a[mid] > key" --> L["high = mid - 1"] --> C
  Q -- "bằng" --> F["trả về mid"]

Chạy tay (ví dụ trong slide): tìm key = 11 trong [2, 4, 7, 10, 11, 45, 50, 59, 60, 66, 69, 70, 79] (13 phần tử).

Bước low high mid a[mid] Quyết định
1 0 12 6 50 50 > 11, bỏ nửa phải: high = 5
2 0 5 2 7 7 < 11, bỏ nửa trái: low = 3
3 3 5 4 11 bằng, trả về index 4

Chỉ 3 lần so sánh, linear search cần 5 (index 0 tới 4). Số bước tối đa là ⌊log₂ n⌋ + 1: 13 phần tử 4 bước, một triệu phần tử 20 bước.

Bản vòng lặp (nên dùng thực tế, không tốn stack):

static int binarySearch(int[] a, int key) {
    int low = 0, high = a.length - 1;
    while (low <= high) {
        int mid = (low + high) >>> 1;
        if (a[mid] < key) low = mid + 1;
        else if (a[mid] > key) high = mid - 1;
        else return mid;
    }
    return -(low + 1);   // giống JDK: mã hoá vị trí cần chèn
}

Bản đệ quy (độ sâu O(log n), base case là đoạn rỗng):

static int binarySearch(int[] a, int key, int low, int high) {
    if (low > high) return -1;                       // base case: đoạn rỗng
    int mid = low + (high - low) / 2;
    if (key < a[mid]) return binarySearch(a, key, low, mid - 1);
    if (key > a[mid]) return binarySearch(a, key, mid + 1, high);
    return mid;
}
// gọi: binarySearch(a, key, 0, a.length - 1)

Thư viện chuẩn:

  • Arrays.binarySearch(a, key) và Collections.binarySearch(list, key) trả index nếu thấy, ngược lại trả -(insertionPoint) - 1, nhờ đó biết luôn chỗ cần chèn để giữ thứ tự.
  • Có phần tử trùng thì JDK không đảm bảo trả vị trí nào. Cần vị trí đầu tiên thì tự viết lower bound:
// index nhỏ nhất i sao cho a[i] >= key (bằng a.length nếu không có)
static int lowerBound(int[] a, int key) {
    int lo = 0, hi = a.length;           // nửa mở [lo, hi)
    while (lo < hi) {
        int mid = (lo + hi) >>> 1;
        if (a[mid] < key) lo = mid + 1;
        else hi = mid;
    }
    return lo;
}
  • Collections.binarySearch trên LinkedList vẫn đúng nhưng phải duyệt list để tới mid, nên thành O(n).

3. Một số thuật toán thông dụng

Ý chính: ba bài kinh điển đều có bản “dịch thẳng từ định nghĩa” chậm hoặc có bug trong slide. Bản tốt hơn: thử chia tới √n, Fibonacci bằng vòng lặp hai biến, palindrome bằng hai con trỏ.

3.1. Kiểm tra số nguyên tố

Số nguyên tố là số tự nhiên lớn hơn 1, chỉ chia hết cho 1 và chính nó. Slide thử chia mọi i từ 2 tới n - 1, tức O(n). Chỉ cần tới √n: nếu n = a · b với a ≤ b thì a ≤ √n. Bỏ số chẵn thì nhanh gấp đôi nữa.

static boolean isPrime(int n) {
    if (n < 2) return false;
    if (n % 2 == 0) return n == 2;
    for (int i = 3; (long) i * i <= n; i += 2)   // ép long để i*i không tràn
        if (n % i == 0) return false;
    return true;
}

O(√n): với n = 2.147.483.647 (số nguyên tố lớn nhất vừa int), cách của slide cần ~2 tỷ phép chia, cách này ~23 nghìn. Kiểm tra nhiều số trong một khoảng thì dùng sàng Eratosthenes, O(n log log n).

3.2. Số Fibonacci thứ n

F(0) = 0, F(1) = 1, F(n) = F(n-1) + F(n-2). Đệ quy ngây thơ dịch thẳng định nghĩa nhưng rất chậm:

static long fibNaive(int n) {
    if (n <= 1) return n;
    return fibNaive(n - 1) + fibNaive(n - 2);
}

Cây lời gọi cho thấy F(3), F(2)… bị tính đi tính lại:

flowchart TD
  F5["F(5)"] --> F4["F(4)"]
  F5 --> F3a["F(3)"]
  F4 --> F3b["F(3)"]
  F4 --> F2a["F(2)"]
  F3a --> F2b["F(2)"]
  F3a --> F1a["F(1)"]
  F3b --> F2c["F(2)"]
  F3b --> F1b["F(1)"]

Số lời gọi tăng theo hàm mũ, ~O(1.618ⁿ) (thường nói gọn O(2ⁿ)); fibNaive(50) chạy hàng phút. Đệ quy có nhớ tính mỗi F(k) một lần: O(n) thời gian, O(n) bộ nhớ.

static long fibMemo(int n, Map<Integer, Long> memo) {
    if (n <= 1) return n;
    Long cached = memo.get(n);
    if (cached != null) return cached;
    long value = fibMemo(n - 1, memo) + fibMemo(n - 2, memo);
    memo.put(n, value);
    return value;
}

Còn có cách O(log n) bằng lũy thừa ma trận hoặc “fast doubling”, hay được hỏi ở vòng khó.

3.3. Kiểm tra chuỗi đối xứng (palindrome)

Chuỗi đối xứng đọc xuôi hay ngược đều như nhau, ví dụ "radar", "level".

static boolean isPalindrome(String s, int i, int j) {
    if (i >= j) return true;                     // đã gặp nhau: chuỗi rỗng hoặc 1 ký tự
    if (s.charAt(i) != s.charAt(j)) return false;
    return isPalindrome(s, i + 1, j - 1);
}
// gọi: isPalindrome(s, 0, s.length() - 1)

Bản vòng lặp của slide duyệt toàn bộ chuỗi nên so mỗi cặp hai lần; chỉ cần đi tới giữa:

static boolean isPalindrome(String s) {
    for (int i = 0, j = s.length() - 1; i < j; i++, j--)
        if (s.charAt(i) != s.charAt(j)) return false;
    return true;
}

Vòng lặp: O(n) thời gian, O(1) bộ nhớ. Bản đệ quy cũng O(n) thời gian nhưng tốn O(n) stack, chuỗi vài trăm nghìn ký tự có thể gây StackOverflowError. Biến thể hay hỏi thêm: bỏ qua ký tự không phải chữ/số và không phân biệt hoa thường.

Xem minh hoạ trực quan

Ý chính: xem animation từng bước (từ sách của Y. Daniel Liang), thử nhập key có và không có trong mảng.

Bài tập

Bài 1: Bốn bài đệ quy cơ bản

Đề: dùng đệ quy để (a) in một chuỗi n lần, (b) tính 2ⁿ, (c) tính xⁿ, (d) tính tổng 1 + 2 + ... + n.

Lời giải Bài 1: code và nhận xét từng ý
// (a) base case: n <= 0 thì không in gì
static void printTimes(String s, int n) {
    if (n <= 0) return;
    System.out.print(s);
    printTimes(s, n - 1);
}

// (b) 2^n = 2 * 2^(n-1), 2^0 = 1. O(n)
static long powerOfTwo(int n) {
    if (n == 0) return 1;
    return 2 * powerOfTwo(n - 1);
}

// (c) chia đôi số mũ: x^n = (x^(n/2))^2, nhân thêm x nếu n lẻ. O(log n)
static long pow(long x, int n) {
    if (n == 0) return 1;
    long half = pow(x, n / 2);            // chỉ gọi MỘT lần rồi dùng lại
    return (n % 2 == 0) ? half * half : half * half * x;
}

// (d) sum(n) = n + sum(n-1), sum(0) = 0. O(n) thời gian và O(n) stack
static long sumTo(int n) {
    if (n <= 0) return 0;
    return n + sumTo(n - 1);
}
  • (b) thực tế chỉ cần 1L << n (đúng với n từ 0 đến 62).
  • (c) là lũy thừa nhanh (exponentiation by squaring): độ sâu chỉ log₂ n. Lỗi hay gặp là pow(x, n/2) * pow(x, n/2): gọi hai lần lại thành O(n). Hỗ trợ n âm: trả 1.0 / pow(x, -n) kiểu double, cẩn thận n = Integer.MIN_VALUE vì -n vẫn âm.
  • (d) có công thức đóng n(n+1)/2, O(1). Đệ quy với n = 100.000 có thể gây StackOverflowError. Câu hay để nói khi phỏng vấn: “đệ quy để luyện tư duy, production thì dùng công thức hoặc vòng lặp”.

Bài 2: Dãy truy hồi ba số hạng, tính f(1000)

Bài trên bảng trắng của khoá: f(1) = 3, f(2) = 7, f(3) = 4, và f(n) = f(n-1) + f(n-2) + f(n-3). Ví dụ f(4) = 3 + 7 + 4 = 14. Hỏi f(1000)?

Lời giải Bài 2: phân tích, BigInteger và bản modulo
  • Đệ quy ngây thơ gọi ba nhánh mỗi tầng, ~O(1.84ⁿ) lời gọi: n = 1000 không bao giờ xong.
  • Memoization đưa về O(n); độ sâu 1000 tầng vẫn ổn trên JVM.
  • Tốt nhất: vòng lặp giữ ba giá trị gần nhất, O(n) thời gian, O(1) bộ nhớ.
  • f(1000) có 265 chữ số (mình đã chạy để kiểm tra), tràn long từ rất sớm nên phải dùng BigInteger. Nếu đề yêu cầu modulo 10⁹ + 7 thì dùng long và lấy dư mỗi bước.
static BigInteger f(int n) {
    if (n < 1) throw new IllegalArgumentException("n must be >= 1");
    BigInteger a = BigInteger.valueOf(3), b = BigInteger.valueOf(7), c = BigInteger.valueOf(4);
    if (n == 1) return a;
    if (n == 2) return b;
    if (n == 3) return c;
    for (int i = 4; i <= n; i++) {
        BigInteger next = a.add(b).add(c);
        a = b; b = c; c = next;
    }
    return c;
}

static long fMod(int n, long mod) {
    long a = 3, b = 7, c = 4;
    if (n == 1) return a;
    if (n == 2) return b;
    if (n == 3) return c;
    for (int i = 4; i <= n; i++) {
        long next = (a + b + c) % mod;   // a, b, c < mod nên tổng không tràn long
        a = b; b = c; c = next;
    }
    return c;
}
// fMod(1000, 1_000_000_007L) = 716358599, khớp với f(1000).mod(10^9 + 7)

Ghi nhớ

  • Giải thích được base case và quan hệ truy hồi, và vì sao thiếu một trong hai thì đệ quy vô hạn.
  • Biết khi nào đệ quy an toàn trong Java (độ sâu O(log n)) và khi nào phải chuyển sang vòng lặp hoặc ArrayDeque.
  • Viết được binary search không tràn số và giải thích giá trị trả về -(insertionPoint) - 1 của JDK.
  • Giải thích được vì sao Fibonacci ngây thơ là hàm mũ và memoization đưa về O(n) thế nào.
  • Nhớ các mốc tràn số: int tràn từ 13! và F(47), long chỉ chứa tới 20! và F(92).

Câu hỏi phỏng vấn

Junior

Base case trong đệ quy là gì? Thiếu nó thì sao?

Là trường hợp nhỏ nhất trả lời ngay, không gọi đệ quy tiếp. Thiếu nó thì JVM ném StackOverflowError.

Thiếu base case, hoặc lời gọi không tiến gần tới nó, thì đệ quy vô hạn cho tới khi stack đầy.

Điều kiện để dùng tìm kiếm nhị phân là gì?

Dữ liệu đã sắp xếp (tổng quát hơn: điều kiện đang xét đơn điệu) và truy cập ngẫu nhiên O(1).

Trên linked list, binary search mất lợi thế vì tới phần tử giữa đã tốn O(n).

Mid

Fibonacci đệ quy ngây thơ có độ phức tạp bao nhiêu? Cải thiện thế nào?

Khoảng O(φⁿ) với φ ≈ 1.618 (thường nói O(2ⁿ)) vì bài con bị tính lặp; memoization đưa về O(n).

Quy hoạch động bottom-up cũng O(n) thời gian; giữ hai biến thì bộ nhớ O(1). Lũy thừa ma trận / fast doubling cho O(log n).

Lỗi gì trong mid = (low + high) / 2?

Tràn số nguyên khi low + high > Integer.MAX_VALUE, ra index âm.

Sửa bằng low + (high - low) / 2 hoặc (low + high) >>> 1. JDK từng có đúng bug này trong Arrays.binarySearch.

Space complexity của hàm đệ quy được tính thế nào?

Cộng thêm độ sâu call stack: độ sâu d tốn O(d) bộ nhớ, ngoài bộ nhớ phụ cấp phát rõ ràng.

factorial(n) đệ quy là O(n) space dù không tạo mảng nào; binary search đệ quy là O(log n); bản vòng lặp là O(1).

Arrays.binarySearch trả về gì khi không tìm thấy?

-(insertionPoint) - 1, với insertionPoint là vị trí cần chèn để giữ mảng có thứ tự.

Luôn âm khi không tìm thấy, kể cả khi insertionPoint = 0, nên kiểm tra >= 0 để biết có tìm thấy không. Có phần tử trùng thì không đảm bảo trả về vị trí nào.

Senior

Java có tối ưu tail call không? Hệ quả với code đệ quy?

Không. Đệ quy đuôi vẫn tốn O(n) stack, nên đệ quy sâu tuyến tính phải viết lại bằng vòng lặp.

JVM giữ đầy đủ stack frame (một phần vì stack trace và mô hình bảo mật). Đệ quy có độ sâu tuyến tính theo input (danh sách dài, cây suy biến, DFS trên đồ thị lớn) có thể StackOverflowError ở production; chuyển sang vòng lặp hoặc dùng ArrayDeque làm stack trên heap. -Xss chỉ là cách vá.

Bắt StackOverflowError để xử lý tiếp có ổn không?

Nói chung là không: đó là Error, báo hiệu trạng thái ứng dụng không nên cố phục hồi.

Khi bắt được thì stack đã gần cạn, các thao tác trong catch (log, cấp phát) có thể lỗi tiếp, và các invariant (lock, trạng thái nửa chừng) có thể đã hỏng. Cách đúng là giới hạn độ sâu đầu vào hoặc viết lại không dùng đệ quy.

Có một API phải kiểm tra rất nhiều số có phải nguyên tố không. Bạn thiết kế thế nào?

Tuỳ phạm vi: số nhỏ thì sàng Eratosthenes dựng sẵn, số lớn tới 64 bit thì Miller-Rabin tất định.

  • Số nhỏ (≤ 10⁷), gọi nhiều lần: dựng sàng một lần khi khởi động (bitset ~1,25 MB), mỗi truy vấn O(1).
  • Số lớn tới 64 bit: Miller-Rabin tất định với bộ base cố định, hoặc BigInteger.isProbablePrime.
  • Thử chia tới √n chỉ hợp với số ít và nhỏ.
  • Nói rõ trade-off giữa bộ nhớ, thời gian khởi động và độ trễ mỗi request.

Từ vựng tiếng Anh

Term Phát âm Nghĩa Ví dụ câu trong phỏng vấn
base case /beɪs keɪs/ trường hợp cơ sở “The base case is n equals zero, which returns one.”
recurrence relation /rɪˈkɜːrəns rɪˈleɪʃən/ quan hệ truy hồi “The recurrence is f of n equals f of n minus one plus f of n minus two.”
call stack /kɔːl stæk/ ngăn xếp lời gọi “Each recursive call pushes a new frame onto the call stack.”
stack overflow /stæk ˈoʊvərfloʊ/ tràn stack “Deep recursion on a long list can cause a stack overflow.”
memoization /ˌmɛmoʊɪˈzeɪʃən/ đệ quy có nhớ “With memoization each subproblem is solved only once.”
overlapping subproblems /ˌoʊvərˈlæpɪŋ ˈsʌbˌprɑːbləmz/ bài con chồng lặp “Fibonacci has overlapping subproblems, so DP helps.”
tail call /teɪl kɔːl/ lời gọi đuôi “The JVM doesn’t eliminate tail calls.”
integer overflow /ˈɪntɪdʒər ˈoʊvərfloʊ/ tràn số nguyên “Computing the midpoint as low plus high can cause integer overflow.”
insertion point /ɪnˈsɜːrʃən pɔɪnt/ vị trí chèn “Arrays.binarySearch encodes the insertion point as a negative number.”
monotonic /ˌmɑːnəˈtɑːnɪk/ đơn điệu “You can binary search any monotonic predicate, not just arrays.”

Ghi chép dựa trên khoá Fundamentals of Backend (Ronin Engineer), viết lại theo cách hiểu của mình.