כמו הצמח של סימור, גם רקורסיות יכולות לנגוס בכם אם לא תהיו זהירים. אבל בשונה מפרח טורף לרקורסיה יש גם יתרונות, כמו למשל בדוגמא הבאה בה המחשב יעזור לנו לפתור חידוני 24.

1. מהו חידון 24

הגעתי השבוע לבלוג של מרקוס דומינוס ולמדתי ממנו על חידון קטן וחביב עם מספרים שהוא משחק עם הילדות שלו: קחו 4 ספרות ונסו באמצעות פעולות חיבור, חיסור כפל וחילוק להרכיב מהן את המספר 24. יש ממש קלים כמו 1, 2, 6, 8 או 4, 5, 1, 5, ומצד שני יש את 1, 2, 7, 7 שלוקח יותר זמן למצוא את הפיתרון.

מרקוס אגב משחק את זה עם הילדות בנסיעה עם לוחיות רישוי של מכוניות שעוברות. אולי כדאי גם לכם לנסות במקום עוד סרט באייפון.

עכשיו בואו ננסה לתת ל JavaScript לעבוד בשבילנו ולמצוא את הפתרונות.

2. אלגוריתם רקורסיבי לפיתרון

השיטה לפתור את החידה מבוססת על סוג של אופטימיות המאפיינת רקורסיות:

1. לוקחים שני מספרים (או ביטויים) מהרשימה ובוחרים פעולה.
2. מחליפים את שני המספרים בביטוי שיצרנו.
3. חוזרים על (1) ו (2) עד שנשארים עם ביטוי יחיד ברשימה.
4. אם ערך הביטוי הוא 24 ניצחנו.

האלגוריתם מתאר מעבר מקלט גדול לקלט קטן יותר (צעד הרקורסיה), ותשובה עבור קלט טריוויאלי (תנאי עצירה). פונקציה רקורסיבית היא התבנית באמצעותה נקודד למחשב אלגוריתמים מסוג זה.

במקרה שלנו כל מספר מייצג את עצמו, וביטוי חשבוני ייוצג על ידי אוביקט שהשדה op שלו מכיל פונקציה המייצגת פעולה חשבונית והשדות x ו y יכילו את האופרנדים.

נתחיל בהגדרת 4 פעולות החשבון:

function add(x, y) { return x + y; }
function mul(x, y) { return x * y; }
function sub(x, y) { return x - y; }
function div(x, y) { return x / y; }

add.toString = () => '+';
mul.toString = () => '*';
sub.toString = () => '-';
div.toString = () => '/';

בהינתן ביטוי (מספר או אוביקט כפי שתואר קודם) אפשר לחשב את הערך שלו באמצעות הפונקציה הרקורסיבית הראשונה:

function value(n) {
  if (typeof n === 'number') {
    return n;
  } else {
    return n.op(value(n.x), value(n.y));
  }
}

וכך נקבל:

value(10) === 10
value({ op: mul, x: 2, y: 5 }) === 10
value({ op: add, x: { op: mul, x: 2, y: 5 }, y: 10 }) === 20

3. נעבור לקוד המשחק

הפונקציה המרכזית בתוכנית מקבלת רשימה של ביטויים או מספרים ומבצעת את החלק הראשון והשני של האלגוריתם, כלומר בוחרת שני ערכים, בוחרת פעולה ומפעילה את עצמה מחדש עם הרשימה הקטנה יותר שמורכבת מהביטוי שיצרנו וכל שאר הדברים שלא נבחרו.

נשים לב שבכל שלב הקלט תמיד יקטן ב-1, כי בכל שלב מורידים שני ערכים מהרשימה ומחליפים אותם בביטוי. כך נראה הקוד:

function play(digits) {
  if (digits.length === 1) {
    if (value(digits[0]) === 24) {
      return digits[0];
    }
  }

  for (let i=0; i < digits.length; i++) {
    for (let j=0; j < digits.length; j++) {
      if ( i === j ) { continue; }
      let rest = digits.filter((item, index) => ((index !== i) && (index !== j)));

      let result = (
        play([ { op: add, x: digits[i], y: digits[j] }, ...rest ]) ||
        play([ { op: sub, x: digits[i], y: digits[j] }, ...rest ]) ||
        play([ { op: sub, x: digits[j], y: digits[i] }, ...rest ]) ||
        play([ { op: mul, x: digits[i], y: digits[j] }, ...rest ]) ||
        (j !== 0 && play([ { op: div, x: digits[i], y: digits[j] }, ...rest ])) ||
        (i !== 0 && play([ { op: div, x: digits[j], y: digits[i] }, ...rest ]))
      );
      if (result) { return result; }
    }
  }
}

כל הפעלה של הפונקציה מתפצלת ל-6 אפשרויות לפי 6 פעולות החשבון שמותר להפעיל במשחק. מספיק שאחת האפשרויות תצליח (כלומר תגיע ל-24) כדי שנחזיר אותה מ play. אם אין דרך להגיע לפתרון כל האפשרויות יחזירו undefined וזה יהיה גם ערך ההחזר של הפונקציה עצמה.

הקוד כבר עובד ומדפיס את הערך אבל בצורה לא הכי קריאה:

console.log(play([2, 2, 5, 7]));
// prints:
// { op: { [Function: add] toString: [Function] },
//  x: { op: { [Function: mul] toString: [Function] }, x: 2, y: 7 },
//  y: { op: { [Function: mul] toString: [Function] }, x: 2, y: 5 } }

אחרי שהבנו את המנגנון הרקורסיבי קל לפתור את זה ולהפוך ביטוי כזה למחרוזת באמצעות רקורסיה שלישית:

function to_s(val) {
  if (typeof val === 'number') {
    return String(val)
  }
  const { x, y, op } = val;
  return `(${to_s(x)} ${op} ${to_s(y)})`;
}

ועכשיו נקבל:

// console.log(to_s(play([2, 2, 5, 7])));
// ((2 * 7) + (2 * 5))

4. גבולות הכח

הפיתרון שכתבנו עובד הרבה יותר טוב ממה שאני מצליח לפתור את החידות האלה, אבל עדיין לא מושלם. תנו לו לשבור את הראש עם 3, 3, 8, 8 ותראו שהוא לא יצליח למצוא את התשובה.

תכל'ס אני מבין אותו. גם אני לא הצלחתי למצוא את התשובה בהתחלה. עד שנזכרתי שיש גם שברים בעולם, ולכן התרגיל הבא עובד לאנשים:

8 / (3 - 8/3) == 24

אבל זה לא עובד כל כך טוב ב JavaScript:

> 8/(3-8/3) == 24
false

> 8/(3-8/3)
23.99999999999999

התשובה של JavaScript נובעת מהקושי שלה (ושל שפות מחשב רבות נוספות) לייצג מספרים ראציונאליים. אפשר לראות התנהגות דומה בתרגיל הבא:

> 0.1 + 0.2
0.30000000000000004

מי שכן ירצה לאפשר לתוכנית שלנו לפתור גם את 3, 3, 8, 8, וחידות רבות נוספות שדורשות שברים, יצטרך לכתוב ספריה לעבודה עם מספרים ראציונאליים (או לקחת אחת קיימת ולשלב אותה בתוכנית).