Cách Tìm Số Fibonacci Thứ n Bằng Đệ Quy Trong JavaScript

Để tìm số Fibonacci thứ n bằng đệ quy trong JavaScript, bạn có thể viết một hàm đệ quy gọi lại chính nó để tính toán giá trị Fibonacci. Số Fibonacci tại vị trí n được xác định bởi công thức: $F(n)=F(n-1)+F(n-2)$ với điều kiện cơ bản là: $F(0)=0$ $F(1)=1$

Dưới đây là ví dụ về cách thực hiện hàm đệ quy để tìm số Fibonacci thứ n trong JavaScript:

function fibonacci(n) {
    // Điều kiện cơ bản
    if (n <= 0) {
        return 0;
    }
    if (n === 1) {
        return 1;
    }
    // Gọi đệ quy
    return fibonacci(n - 1) + fibonacci(n - 2);
}

// Kiểm tra hàm với n = 10
let n = 10;
console.log(`Số Fibonacci thứ ${n} là ${fibonacci(n)}`); // Output: Số Fibonacci thứ 10 là 55

Giải Thích:

1. Điều kiện cơ bản (Base Case):
   • Nếu $n\le 0$, hàm trả về 0.
   • Nếu $n=1$, hàm trả về 1.
2. Đệ quy (Recursive Case):
   • Nếu $n$ lớn hơn 1, hàm gọi lại chính nó với các tham số $n-1$ và $n-2$ và trả về tổng của hai giá trị này.

Lưu Ý:

• Hiệu suất: Hàm đệ quy cơ bản này có thể không hiệu quả cho các giá trị $n$ lớn do số lần gọi đệ quy tăng theo cấp số nhân, dẫn đến việc tính toán lại các giá trị Fibonacci nhiều lần. Để cải thiện hiệu suất, bạn có thể sử dụng kỹ thuật nhớ (memoization) hoặc phương pháp tính toán Fibonacci bằng cách lặp (iterative method).

Ví dụ Sử Dụng Memoization:

function fibonacci(n, memo = {}) {
    // Kiểm tra nếu giá trị đã được lưu trữ trong memo
    if (n in memo) {
        return memo[n];
    }
    // Điều kiện cơ bản
    if (n <= 0) {
        return 0;
    }
    if (n === 1) {
        return 1;
    }
    // Gọi đệ quy và lưu trữ kết quả trong memo
    memo[n] = fibonacci(n - 1, memo) + fibonacci(n - 2, memo);
    return memo[n];
}

// Kiểm tra hàm với n = 10
let n = 10;
console.log(`Số Fibonacci thứ ${n} là ${fibonacci(n)}`); // Output: Số Fibonacci thứ 10 là 55

Với cách tiếp cận sử dụng memoization, bạn có thể giảm đáng kể số lần gọi hàm đệ quy và cải thiện hiệu suất khi tính toán các giá trị Fibonacci lớn.