Đệ quy (Recursion)

1. Đệ quy là gì?

Đệ quy (recursion) là khi một phương thức tự gọi lại chính nó để giải quyết một bài toán, bằng cách chia nhỏ thành các bài toán con giống hệt nhưng nhỏ hơn.

Mọi hàm đệ quy cần có hai thành phần:

1. Trường hợp cơ sở (base case): điều kiện dừng, không gọi đệ quy nữa
2. Trường hợp đệ quy (recursive case): gọi lại chính nó với đầu vào nhỏ hơn, tiến dần đến base case

2. Ví dụ: tính giai thừa

static long factorial(int n) {
    if (n == 0) {         // base case: 0! = 1
        return 1;
    }
    return n * factorial(n - 1); // recursive case: n! = n * (n-1)!
}

public static void main(String[] args) {
    System.out.println(factorial(5)); // 120
}

Diễn giải: factorial(5) = 5 * factorial(4) = 5 * 4 * factorial(3) = ... = 5 * 4 * 3 * 2 * 1 * factorial(0) = 120.

3. Ví dụ: dãy Fibonacci

static int fibonacci(int n) {
    if (n <= 1) { // base case: fib(0) = 0, fib(1) = 1
        return n;
    }
    return fibonacci(n - 1) + fibonacci(n - 2); // recursive case
}

public static void main(String[] args) {
    for (int i = 0; i < 10; i++) {
        System.out.print(fibonacci(i) + " ");
    }
    // 0 1 1 2 3 5 8 13 21 34
}

⚠️ Cách viết đệ quy trên cho Fibonacci đơn giản, dễ hiểu, nhưng kém hiệu quả với n lớn vì tính lại cùng một giá trị nhiều lần - trong thực tế nên dùng vòng lặp hoặc lưu kết quả trung gian (memoization).

4. Nguy cơ: thiếu base case → StackOverflowError

Nếu quên base case, hoặc base case không bao giờ đạt tới, phương thức sẽ gọi chính nó vô hạn - mỗi lời gọi chiếm một khung ngăn xếp (stack frame), dẫn đến hết bộ nhớ ngăn xếp:

static int badRecursion(int n) {
    return badRecursion(n - 1); // KHÔNG có base case -> gọi mãi mãi
}

public static void main(String[] args) {
    badRecursion(5); // StackOverflowError!
}

5. Khi nào nên dùng đệ quy?

Đệ quy thường giúp code ngắn gọn, dễ đọc với các bài toán có cấu trúc tự nhiên đệ quy (duyệt cây, chia để trị, quay lui…). Với các bài toán đơn giản, tuyến tính, vòng lặp (for/while) thường hiệu quả hơn vì không tốn chi phí gọi hàm lặp lại nhiều lần.

Tổng kết

• Đệ quy: một phương thức tự gọi lại chính nó, cần có base case (điều kiện dừng) và recursive case
• Thiếu base case hoặc base case không đạt tới → StackOverflowError
• Đệ quy giúp code ngắn gọn với bài toán có cấu trúc đệ quy tự nhiên; vòng lặp thường hiệu quả hơn cho bài toán tuyến tính đơn giản