Dãy Fibonacci trong JavaScript

Số Fibonacci là các số sao cho mỗi số trong dãy sau hai số đầu là tổng của hai số đi trước. Dãy bắt đầu bằng 1, 1. Ví dụ:

1, 1, 2, 3, 5, 8, 13, 21, 34, …

Chúng ta có thể viết chương trình tạo số Fibonacci thứ n như sau:

function fibNaive(n) {
  if (n <= 1) return n;
  return fibNaive(n - 1) + fibNaive(n - 2);
}

Bạn có thể kiểm tra bằng cách sau:

console.log(fibNaive(7));
console.log(fibNaive(8));
console.log(fibNaive(9));
console.log(fibNaive(4));

Điều này sẽ cho ra kết quả:

13 21 34 3

Hãy xem các lời gọi hàm này thực sự diễn ra như thế nào:

/**
 * f(5)
 * / \
 * f(4) f(3)
 * / \ / \
 * f(3) f(2) f(2) f(1)
 * / \ .......... 
 * f(2) f(1).......... 
 */

Khi gọi f(5), ta sẽ gọi f(2) gần 4 lần và nó sẽ chạy cùng mã lặp lại 4 lần. Đây là trường hợp của bài toán con chồng chéo (overlapping subproblem). Thử chạy hàm đó cho 500. Bạn sẽ bị treo vì tất cả các lời gọi này tốn rất nhiều thời gian.

Khi cần số Fibonacci thứ 5, ta chỉ cần các số Fibonacci thấp hơn một lần nhưng tính toán chúng nhiều lần hơn thế. Ta có thể giảm tính toán dư thừa này nếu chỉ lưu các giá trị đã tính ở đâu đó. Đây là cốt lõi của quy hoạch động (dynamic programming).

Tính một lần và tái sử dụng sau.

Hãy xem triển khai có ghi nhớ (memoized) của hàm fib:

let fibStore = {};
function fibDP(n) {
  if (n <= 1) return n;
  if (fibStore[n]) {
    return fibStore[n];
  }
  fibStore[n] = fibDP(n - 1) + fibDP(n - 2);
  return fibStore[n];
}

Bây giờ ta dùng một store, fibStore để theo dõi các giá trị đã tính. Điều này giảm tính toán dư thừa quá mức và giữ hàm hiệu quả.

Bạn có thể kiểm tra bằng cách sau:

console.log(fibDP(7));
console.log(fibDP(8));
console.log(fibDP(9));
console.log(fibDP(4));

Điều này sẽ cho ra kết quả:

13 21 34 3

Bạn thậm chí có thể kiểm tra với giá trị rất lớn.