ปัญหาบันไดแบบ Recursive ใน JavaScript

ปัญหาบันได (Staircase Problem)

มีบันได n ขั้น คนยืนด้านล่างต้องการขึ้นไปด้านบน สามารถเดินได้ทีละ 1 หรือ 2 ขั้น ต้องการหาจำนวนวิธีการเดินขึ้นไปถึงขั้นบนสุด

นี่คือปัญหา Fibonacci แบบคลาสสิก: F(n) = F(n-1) + F(n-2)

• F(1) = 1 วิธี (1)
• F(2) = 2 วิธี (1+1, 2)
• F(3) = 3 วิธี (1+1+1, 1+2, 2+1)
• F(4) = 5 วิธี

โค้ดตัวอย่าง (Iterative - ประหยัดหน่วยความจำ)

const recursiveStaircase = (num = 10) => {
  if (num <= 0) return 0;
  
  const steps = [1, 2]; // F(1), F(2)
  if (num <= 2) return steps[num - 1];
  
  for (let currentStep = 3; currentStep <= num; currentStep++) {
    // ใช้ Array Destructuring สลับค่า
    [steps[0], steps[1]] = [steps[1], steps[0] + steps[1]];
  }
  return steps[1];
};

console.log(recursiveStaircase());  // 89 (default n=10)
console.log(recursiveStaircase(4)); // 5
console.log(recursiveStaircase(13)); // 377

ผลลัพธ์

89 5 377

วิธีอื่นๆ

1. Recursive แบบง่าย (ช้า - Exponential)

const stairRecursive = (n) => {
  if (n <= 1) return 1;
  return stairRecursive(n-1) + stairRecursive(n-2);
};

2. Recursive + Memoization (เร็ว - Linear)

const stairMemo = (n, memo = {}) => {
  if (n <= 1) return 1;
  if (memo[n]) return memo[n];
  return memo[n] = stairMemo(n-1, memo) + stairMemo(n-2, memo);
};

3. สูตร Binet (O(1) - ประมาณค่า)

const stairBinet = (n) => {
  const phi = (1 + Math.sqrt(5)) / 2;
  return Math.round((phi ** (n+1)) / Math.sqrt(5));
};

ขยายปัญหา: เดินได้ 1, 2, 3 ขั้น

const stair3Steps = (n) => {
  if (n <= 1) return 1;
  if (n === 2) return 2;
  let a = 1, b = 1, c = 2; // F(0), F(1), F(2)
  for (let i = 3; i <= n; i++) {
    [a, b, c] = [b, c, a + b + c];
  }
  return c;
};

สรุป

• Iterative (ตัวอย่าง) - เร็วที่สุด O(n) Time, O(1) Space ✓
• Memoization - เขียนง่าย O(n) Time, O(n) Space
• Recursive แบบง่าย - ช้ามาก O(2^n) ไม่แนะนำ