// Đệ quy: function gọi chính nó
// Cần 2 thành phần: Base case + Recursive case

function factorial(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 * factorial(n - 1);
}

console.log(factorial(5)); // 120
// 5! = 5 × 4 × 3 × 2 × 1 = 120

// Fibonacci sequence
function fibonacci(n) {
    if (n <= 1) return n;
    return fibonacci(n - 1) + fibonacci(n - 2);
}
console.log(fibonacci(6)); // 8

// Tìm kiếm nhị phân
function binarySearch(arr, target, left = 0, right = arr.length - 1) {
    if (left > right) return -1;
    
    let mid = Math.floor((left + right) / 2);
    
    if (arr[mid] === target) return mid;
    
    if (arr[mid] > target) {
        return binarySearch(arr, target, left, mid - 1);
    } else {
        return binarySearch(arr, target, mid + 1, right);
    }
}

let numbers = [1, 3, 5, 7, 9];
console.log(binarySearch(numbers, 7)); // 3

// Tính tổng mảng đa chiều
function sumNestedArray(arr) {
    let sum = 0;
    for (let item of arr) {
        if (Array.isArray(item)) {
            sum += sumNestedArray(item); // Recursive
        } else {
            sum += item; // Base case
        }
    }
    return sum;
}

let nested = [1, [2, 3], [4, [5, 6]], 7];
console.log(sumNestedArray(nested)); // 28

// Flatten mảng
function flattenArray(arr) {
    let result = [];
    for (let item of arr) {
        if (Array.isArray(item)) {
            result = result.concat(flattenArray(item));
        } else {
            result.push(item);
        }
    }
    return result;
}

console.log(flattenArray(nested)); // [1, 2, 3, 4, 5, 6, 7]

// ⚠️ Tránh Stack Overflow - luôn có base case
function infiniteRecursion(n) {
    return infiniteRecursion(n); // NGUY HIỂM!
}

// ✅ So sánh với vòng lặp
// Đệ quy - code ngắn gọn nhưng chậm hơn
function factorialRecursive(n) {
    if (n <= 1) return 1;
    return n * factorialRecursive(n - 1);
}

// Vòng lặp - nhanh hơn, ít memory hơn
function factorialIterative(n) {
    let result = 1;
    for (let i = 2; i <= n; i++) {
        result *= i;
    }
    return result;
}