רקורסיה ב-JavaScript – כשפונקציה קוראת לעצמה

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

מדריך זה משתמש בידע שאותו פיתחנו בסדרת המדריכים בנושא של פונקציות לטיפול במערכים של JavaScript, ובפרט המדריכים שעוסקים בפונקציות filter ו-forEach.

חישוב עצרת ומספרים באמצעות רקורסיה

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

5 x 4 x 3 x 2 x 1 = 120

ניתן לחשב באמצעות לולאה שרצה מהמספר הנתון ועד ל-1:

let calcFactorial = (num) => {
  let value = 1;
  for(let x=num;x>=1; x--){
    value *= x;
  }
  return value;
}
console.log(calcFactorial(5)); // 120

ואת אותו החישוב ניתן לבצע באמצעות פונקציה שקוראת לעצמה (=רקורסיה).

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

כך נראה הקוד:

let calcFactorial = (num)  => (num * calcFactorial (num  - 1));

והתוצאה היא הודעת שגיאה שתופיע בדפדפן:

Uncaught RangeError: Maximum call stack size exceeded

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

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

let calcFactorial = (num) => {
  if (num === 1) { //  stop recursion
    return 1;
  } else { 
    return (num * calcFactorial(num - 1));
  }
}
console.log(calcFactorial(5)); // 120

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

עיבוד ה-HTML באמצעות פונקציות רקורסיביות

רקורסיה מועילה במיוחד בכל הנוגע לעיבוד ה-DOM (ה-HTML של הדף) בגלל שאותם מבנים יכולים לחזור על עצמם. לדוגמה, מבנה של רשימה בתוך רשימה. משהו כזה:

<ul>
  <li>1</li>
  <li>2</li>
  <li>3<\li>
    <ul>
      <li>3a</li>
      <li>3b</li>
    </ul>
  </li>
</ul>

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

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

let crawlDom = (node) => {
  if (node.tagName === 'LI'){
    node.className = 'yellow';
  }
  node.childNodes.forEach( (nestedNode) => crawlDom(nestedNode));
}
crawlDom(document.querySelector("body"));

פונקציות רקורסיביות לעיבוד XML ו-JSON

פונקציות רקורסיביות משמשות גם לעיבוד של XML ו-JSON בגלל שכמו HTML מבנה הנתונים מכיל התפצלויות שחוזרות על עצמם.

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

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

var taxonomy = [
    {name:  'קופים'      , parent:  'יונקים'},
    {name:  'דגים'      , parent:  'בעלי חיים'},
    {name:  'צמחים'    , parent: null},
    {name:   'יונקים'   , parent:  'בעלי חיים'},
    {name:   'בעלי חיים'   , parent: null},
    {name:  'יונקי כיס', parent:  'יונקים'},
    {name:   'קופים גדולים'  , parent:   'קופים'},
    {name:   'ציפורים'     , parent:   'בעלי חיים'}
];

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

{
    "צמחים": {},
    "בעלי חיים": {
      "דגים": {},
      "יונקים": {
        "יונקי כיס": {},
        "קופים": {
          "קופים גדולים": {}
      }
    },
      "ציפורים": {}
  }
}

לשם כך, נשתמש בפונקציה רקורסיבית:

let makeTree = (array, parent) =>  {	
  let node = {};
  array
    .filter((c) => c.parent === parent)
    .forEach((c) => node[c.name] = makeTree(array, c.name));
	
  return node;
}
console.log(JSON.stringify(makeTree(taxonomy, null), null, 2));

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

מדריכי JavaScript למתקדמים

אהבתם? לא אהבתם? דרגו!

0 הצבעות, ממוצע 0 מתוך 5 כוכבים