Chuyển tới nội dung chính

🔄 Đệ Quy - Recursion

Chào mừng đến với bài học về Recursion - phương thức tự gọi chính nó trong Café!

🎯 Món Ăn Hôm Nay​

Tưởng tượng bạn đang đếm số ly cà phê trong kho:

  • Đếm từng ly một → Gọi lại chính mình
  • Dừng khi hết ly → Điều kiện dừng
  • Giống gương soi gương → Lặp vô tận nếu không có điểm dừng

Đó chính là Recursion - hàm tự gọi chính nó!

🔄 Recursion Là Gì?​

Recursion = Đệ quy (method tự gọi chính nó)

public static void demNguoc(int n) {
    if (n == 0) {  // Điều kiện dừng
        System.out.println("Hết!");
        return;
    }
    System.out.println(n);
    demNguoc(n - 1);  // Gọi lại chính nó
}

// Sử dụng
demNguoc(5);  // 5, 4, 3, 2, 1, Hết!

☕ Ẩn Dụ Café:

  • Recursion = Barista dạy barista mới (cứ truyền lại)
  • Base case = Điều kiện dừng (khi nào xong)
  • Recursive case = Bước tiếp theo (làm gì tiếp)
  • Stack = Chồng ly (xếp chồng lên nhau)

📋 Cấu Trúc Recursion​

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

  1. Base Case (Điều kiện dừng): Khi nào dừng
  2. Recursive Case (Bước đệ quy): Gọi lại chính nó
public static int giaiThua(int n) {
    // Base case: Điều kiện dừng
    if (n <= 1) {
        return 1;
    }
    
    // Recursive case: Gọi lại chính nó
    return n * giaiThua(n - 1);
}

👨‍🍳 Câu Chuyện Trong Quán​

Tình huống 1: Đếm Ngược

public class DemNguoc {
    public static void demNguoc(int n) {
        // Base case
        if (n == 0) {
            System.out.println("☕ Bắt đầu pha!");
            return;
        }
        
        // In ra số hiện tại
        System.out.println("Chuẩn bị... " + n);
        
        // Recursive case
        demNguoc(n - 1);
    }

    public static void main(String[] args) {
        System.out.println("⏰ ĐẾM NGƯỢC PHA CÀ PHÊ:\n");
        demNguoc(5);
    }
}

Output:

⏰ ĐẾM NGƯỢC PHA CÀ PHÊ:

Chuẩn bị... 5
Chuẩn bị... 4
Chuẩn bị... 3
Chuẩn bị... 2
Chuẩn bị... 1
☕ Bắt đầu pha!

Tình huống 2: Tính Giai Thừa

public class GiaiThua {
    public static int tinhGiaiThua(int n) {
        // Base case
        if (n <= 1) {
            return 1;
        }
        
        // Recursive case
        return n * tinhGiaiThua(n - 1);
    }

    public static void main(String[] args) {
        System.out.println("📊 TÍNH GIAI THỪA:\n");
        
        for (int i = 1; i <= 5; i++) {
            int ketQua = tinhGiaiThua(i);
            System.out.printf("%d! = %d%n", i, ketQua);
        }
    }
}

Output:

📊 TÍNH GIAI THỪA:

1! = 1
2! = 2
3! = 6
4! = 24
5! = 120

📝 Công Thức Nấu (Code Examples)​

Ví Dụ 1: Fibonacci - Dãy Số​

public class Fibonacci {
    public static int fibonacci(int n) {
        // Base case
        if (n <= 1) {
            return n;
        }
        
        // Recursive case
        return fibonacci(n - 1) + fibonacci(n - 2);
    }

    public static void main(String[] args) {
        System.out.println("🔢 DÃY FIBONACCI:\n");
        
        for (int i = 0; i < 10; i++) {
            System.out.print(fibonacci(i) + " ");
        }
        System.out.println();
    }
}

Output:

🔢 DÃY FIBONACCI:

0 1 1 2 3 5 8 13 21 34

Giải thích:

fibonacci(5)
  = fibonacci(4) + fibonacci(3)
  = (fibonacci(3) + fibonacci(2)) + (fibonacci(2) + fibonacci(1))
  = ((fibonacci(2) + fibonacci(1)) + (fibonacci(1) + fibonacci(0))) + ...

Ví Dụ 2: Tính Tổng Từ 1 Đến N​

public class TinhTong {
    public static int tongSo(int n) {
        // Base case
        if (n == 1) {
            return 1;
        }
        
        // Recursive case
        return n + tongSo(n - 1);
    }

    public static void main(String[] args) {
        int n = 10;
        int ketQua = tongSo(n);
        
        System.out.printf("Tổng từ 1 đến %d = %d%n", n, ketQua);
    }
}

Output:

Tổng từ 1 đến 10 = 55

Ví Dụ 3: Đảo Ngược String​

public class DaoNguocChuoi {
    public static String daoNguoc(String str) {
        // Base case: Chuỗi rỗng hoặc 1 ký tự
        if (str.isEmpty()) {
            return str;
        }
        
        // Recursive case: Lấy ký tự cuối + đảo ngược phần còn lại
        return str.charAt(str.length() - 1) 
               + daoNguoc(str.substring(0, str.length() - 1));
    }

    public static void main(String[] args) {
        String tenMon = "Latte";
        String daoNguoc = daoNguoc(tenMon);
        
        System.out.println("Gốc: " + tenMon);
        System.out.println("Đảo: " + daoNguoc);
    }
}

Output:

Gốc: Latte
Đảo: ettaL

Ví Dụ 4: Tính Lũy Thừa​

public class LuyThua {
    public static int luyThua(int coSo, int soMu) {
        // Base case
        if (soMu == 0) {
            return 1;
        }
        
        // Recursive case
        return coSo * luyThua(coSo, soMu - 1);
    }

    public static void main(String[] args) {
        System.out.println("📐 TÍNH LŨY THỪA:\n");
        
        System.out.println("2^0 = " + luyThua(2, 0));
        System.out.println("2^3 = " + luyThua(2, 3));
        System.out.println("5^4 = " + luyThua(5, 4));
    }
}

Output:

📐 TÍNH LŨY THỪA:

2^0 = 1
2^3 = 8
5^4 = 625

Ví Dụ 5: Đếm Số Chữ Số​

public class DemChuSo {
    public static int demChuSo(int n) {
        // Base case
        if (n < 10) {
            return 1;
        }
        
        // Recursive case
        return 1 + demChuSo(n / 10);
    }

    public static void main(String[] args) {
        int[] soLuong = {5, 50, 500, 5000, 50000};
        
        System.out.println("🔢 ĐếM CHỮ SỐ:\n");
        
        for (int so : soLuong) {
            int dem = demChuSo(so);
            System.out.printf("%,6d → %d chữ số%n", so, dem);
        }
    }
}

Output:

🔢 ĐếM CHỮ SỐ:

     5 → 1 chữ số
    50 → 2 chữ số
   500 → 3 chữ số
 5,000 → 4 chữ số
50,000 → 5 chữ số

Ví Dụ 6: Tìm Ước Chung Lớn Nhất (GCD)​

public class UocChung {
    public static int gcd(int a, int b) {
        // Base case
        if (b == 0) {
            return a;
        }
        
        // Recursive case: Thuật toán Euclid
        return gcd(b, a % b);
    }

    public static void main(String[] args) {
        System.out.println("🔢 ƯỚC CHUNG LỚN NHẤT:\n");
        
        System.out.println("GCD(48, 18) = " + gcd(48, 18));
        System.out.println("GCD(100, 50) = " + gcd(100, 50));
        System.out.println("GCD(17, 13) = " + gcd(17, 13));
    }
}

Output:

🔢 ƯỚC CHUNG LỚN NHẤT:

GCD(48, 18) = 6
GCD(100, 50) = 50
GCD(17, 13) = 1

🔥 Thực Hành Trong Quán​

Bài Tập 1: In Menu Lồng Nhau​

public class MenuLong {
    public static void inMenu(String[] items, int index, int level) {
        // Base case
        if (index >= items.length) {
            return;
        }
        
        // In thụt lề theo level
        for (int i = 0; i < level; i++) {
            System.out.print("  ");
        }
        System.out.println("- " + items[index]);
        
        // Recursive case
        inMenu(items, index + 1, level + 1);
    }

    public static void main(String[] args) {
        String[] menu = {"Cà phê", "Espresso", "Latte", "Mocha", "Cappuccino"};
        
        System.out.println("☕ MENU PHÂN CẤP:\n");
        inMenu(menu, 0, 0);
    }
}

Output:

☕ MENU PHÂN CẤP:

- Cà phê
  - Espresso
    - Latte
      - Mocha
        - Cappuccino

Bài Tập 2: Tính Tổng Các Chữ Số​

public class TongChuSo {
    public static int tongChuSo(int n) {
        // Base case
        if (n == 0) {
            return 0;
        }
        
        // Recursive case
        return (n % 10) + tongChuSo(n / 10);
    }

    public static void main(String[] args) {
        int[] giaTri = {12345, 50000, 99999};
        
        System.out.println("➕ TỔNG CÁC CHỮ SỐ:\n");
        
        for (int gia : giaTri) {
            int tong = tongChuSo(gia);
            System.out.printf("%,6d → Tổng: %d%n", gia, tong);
        }
    }
}

Output:

➕ TỔNG CÁC CHỮ SỐ:

12,345 → Tổng: 15
50,000 → Tổng: 5
99,999 → Tổng: 45

Bài Tập 3: Kiểm Tra Palindrome (Đối Xứng)​

public class KiemTraDoiXung {
    public static boolean laPalindrome(String str) {
        // Base case: Chuỗi rỗng hoặc 1 ký tự
        if (str.length() <= 1) {
            return true;
        }
        
        // Kiểm tra ký tự đầu và cuối
        if (str.charAt(0) != str.charAt(str.length() - 1)) {
            return false;
        }
        
        // Recursive case: Kiểm tra phần giữa
        return laPalindrome(str.substring(1, str.length() - 1));
    }

    public static void main(String[] args) {
        String[] ten = {"Latte", "madam", "noon", "Mocha", "level"};
        
        System.out.println("🔄 KIỂM TRA PALINDROME:\n");
        
        for (String t : ten) {
            boolean ketQua = laPalindrome(t.toLowerCase());
            System.out.printf("%-8s: %s%n", t, ketQua ? "✅ Đối xứng" : "❌ Không");
        }
    }
}

Output:

🔄 KIỂM TRA PALINDROME:

Latte   : ❌ Không
madam   : ✅ Đối xứng
noon    : ✅ Đối xứng
Mocha   : ❌ Không
level   : ✅ Đối xứng

Bài Tập 4: Tìm Max Trong Mảng​

public class TimMax {
    public static int timMax(int[] arr, int index) {
        // Base case: Phần tử cuối
        if (index == arr.length - 1) {
            return arr[index];
        }
        
        // Recursive case
        int maxConLai = timMax(arr, index + 1);
        return Math.max(arr[index], maxConLai);
    }

    public static void main(String[] args) {
        int[] gia = {45000, 60000, 50000, 55000, 48000};
        
        int max = timMax(gia, 0);
        
        System.out.println("💰 BẢNG GIÁ:");
        for (int g : gia) {
            System.out.printf("%,d VND%n", g);
        }
        
        System.out.printf("%n🏆 Giá cao nhất: %,d VND%n", max);
    }
}

⚠️ Lỗi Thường Gặp​

Lỗi 1: Thiếu Base Case (StackOverflowError)​

// ❌ SAI: Không có điều kiện dừng
public static void demMaiMai(int n) {
    System.out.println(n);
    demMaiMai(n - 1);  // ❌ Lỗi! Chạy vô tận
}

// ✅ ĐÚNG: Có base case
public static void dem(int n) {
    if (n == 0) {  // ✅ Điều kiện dừng
        return;
    }
    System.out.println(n);
    dem(n - 1);
}

Lỗi 2: Base Case Sai​

// ❌ SAI: Base case không bao giờ đạt được
public static int giaiThua(int n) {
    if (n == 0) {  // Đúng
        return 1;
    }
    return n * giaiThua(n - 2);  // ❌ Lỗi! Bỏ qua n=1
}

// ✅ ĐÚNG: Base case phù hợp
public static int giaiThua(int n) {
    if (n <= 1) {  // ✅ Bắt cả n=0 và n=1
        return 1;
    }
    return n * giaiThua(n - 1);
}

Lỗi 3: Quá Nhiều Đệ Quy (Hiệu Năng Kém)​

// ❌ SAI: Fibonacci đệ quy thuần túy (chậm)
public static int fib(int n) {
    if (n <= 1) return n;
    return fib(n - 1) + fib(n - 2);  // Tính lại nhiều lần
}

// ✅ ĐÚNG: Dùng memoization hoặc iteration
public static int fibIterative(int n) {
    if (n <= 1) return n;
    
    int a = 0, b = 1;
    for (int i = 2; i <= n; i++) {
        int temp = a + b;
        a = b;
        b = temp;
    }
    return b;
}

Lỗi 4: Không Trả Về Giá Trị Trong Base Case​

// ❌ SAI: Base case không return
public static int tinhTong(int n) {
    if (n == 1) {
        // Thiếu return!
    }
    return n + tinhTong(n - 1);
}

// ✅ ĐÚNG: Base case có return
public static int tinhTong(int n) {
    if (n == 1) {
        return 1;  // ✅ Có return
    }
    return n + tinhTong(n - 1);
}

💡 Bí Quyết Của Barista​

  1. Luôn có base case: Điều kiện dừng rõ ràng
  2. Tiến về base case: Mỗi lần gọi phải gần base case hơn
  3. Đơn giản hóa vấn đề: Chia nhỏ bài toán
  4. Kiểm tra hiệu năng: Recursion có thể chậm
  5. Tránh đệ quy sâu: StackOverflowError nếu quá sâu
  6. Cân nhắc iteration: Đôi khi vòng lặp tốt hơn

🎓 Bạn Đã Học Được​

  • ✅ Recursion = Hàm tự gọi chính nó
  • ✅ Base case = Điều kiện dừng (bắt buộc)
  • ✅ Recursive case = Bước đệ quy
  • ✅ Phải tiến về base case
  • ✅ Ứng dụng: Giai thừa, Fibonacci, đảo ngược, tìm kiếm
  • ✅ Lưu ý: StackOverflowError, hiệu năng
  • ✅ So sánh: Recursion vs Iteration

☕ Món Tiếp Theo​

Đã biết recursion! Giờ học về kế thừa (extends):

👉 Kế Thừa - Extends

💡 Lời Khuyên Cuối: Recursion như công thức truyền miệng - chia sẻ từng bước cho đến khi ai cũng biết!