Bài toán thang máy đệ quy trong JavaScript

Giả sử chúng ta có bài toán sau:

Có n bậc thang, một người đứng ở dưới muốn lên đến đỉnh. Người đó có thể leo 1 hoặc 2 bậc tại một thời điểm. Chúng ta cần đếm số cách người đó có thể đến đỉnh.

Chúng ta cần viết một hàm JavaScript nhận vào một số n biểu thị số bậc thang. Hàm nên đếm và trả về số cách leo thang.

Ví dụ

Dưới đây là mã nguồn:

const recursiveStaircase = (num = 10) => {    if (num <= 0) {       return 0;    }    const steps = [1, 2];    if (num <= 2) {       return steps[num - 1];    }    for (let currentStep = 3; currentStep <= num; currentStep += 1) {       [steps[0], steps[1]] = [steps[1], steps[0] + steps[1]];    }    return steps[1]; }; console.log(recursiveStaircase()); console.log(recursiveStaircase(4)); console.log(recursiveStaircase(13));

Kết quả

Đầu ra trên console:

89 5 377

Giải thích: Đây thực chất là dãy Fibonacci. Số cách leo n bậc bằng F(n+1) với F(1)=1, F(2)=1. Hàm dùng cách tiếp cận lặp (iterative) với O(1) không gian, hiệu quả hơn đệ quy thuần túy.