Đệ quy & Sắp xếp: giải bài toán bằng cách chia nhỏ

Đệ quy là gì?

Đệ quy (recursion) là khi một hàm gọi chính nó với dữ liệu nhỏ hơn, cho tới khi gặp trường hợp cơ sở (base case) thì dừng. Ví dụ thực tế: mở hộp bên trong hộp bên trong hộp — cho tới hộp cuối cùng không còn hộp nào nữa.

// File: recursion.js
// Tính giai thừa: 5! = 5 × 4 × 3 × 2 × 1
function factorial(n) {
  // Base case: khi n = 0 hoặc 1, dừng lại
  if (n <= 1) return 1

  // Recursive case: gọi chính mình với n nhỏ hơn
  return n * factorial(n - 1)
}

console.log(factorial(5)) // 120

// Quá trình chạy:
// factorial(5) = 5 × factorial(4)
//              = 5 × 4 × factorial(3)
//              = 5 × 4 × 3 × factorial(2)
//              = 5 × 4 × 3 × 2 × factorial(1)
//              = 5 × 4 × 3 × 2 × 1 = 120

Ví dụ thực tế: đếm ngược và Fibonacci

// File: examples.js
// Đếm ngược
function countdown(n) {
  if (n <= 0) { console.log("Hết!"); return }
  console.log(n)
  countdown(n - 1)
}
countdown(5) // 5, 4, 3, 2, 1, Hết!

// Fibonacci: 0, 1, 1, 2, 3, 5, 8, 13...
// Mỗi số = tổng 2 số trước
function fibonacci(n) {
  if (n <= 0) return 0
  if (n === 1) return 1
  return fibonacci(n - 1) + fibonacci(n - 2)
}
console.log(fibonacci(7)) // 13

Thuật toán sắp xếp: Bubble Sort & Selection Sort

Sắp xếp (sorting) là bài toán cơ bản nhất trong lập trình. Cho một mảng lộn xộn, sắp xếp lại từ nhỏ đến lớn.

// File: sorting.js
// Bubble Sort: so sánh từng cặp kề nhau, đổi chỗ nếu sai thứ tự
// Lặp lại cho tới khi không đổi nữa → đã sắp xếp xong
function bubbleSort(arr) {
  const n = arr.length
  for (let i = 0; i < n - 1; i++) {
    for (let j = 0; j < n - 1 - i; j++) {
      if (arr[j] > arr[j + 1]) {
        // Đổi chỗ (swap)
        const temp = arr[j]
        arr[j] = arr[j + 1]
        arr[j + 1] = temp
      }
    }
  }
  return arr
}

console.log(bubbleSort([64, 25, 12, 22, 11]))
// [11, 12, 22, 25, 64]

• Giải thích đệ quy bằng ví dụ giai thừa/Fibonacci
• Viết hàm đệ quy có base case
• Triển khai Bubble Sort
• Phân biệt O(n²) và O(n log n)