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

1. פתרון נאיבי לחישוב כפולה משותפת מינימלית

function ex4(x, y) {
  var start = Math.max(x,y);

  while(1) {
    if (start %x === 0 && start%y === 0) {
      return start;
    }
    start++;
  }
}

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

הפתרון הנכון הוא כמובן להחליף את הלולאה בתרגיל חילוק פשוט באופן הבא:

function gcd(x,y) {
  if (x%y === 0) {
    return y;
  }
  return gcd(y,x%y);
}

function lcm(x,y) {
  return x*y/gcd(x,y);
}

מה ההבדל בין זמני החישוב? בגירסא הקצרה כרום מספיק לחשב 9 מיליון פעמים את התוצאה באותו הזמן שבגירסא הארוכה הוא מספיק לחשב רק 89 פעמים. מוזמנים לבדוק את ההבדלים אצלכם על המחשב ב jsperf הבא:
https://jsperf.com/recursion-vs-iteration-gcd/2