תחי ישראל - אין לנו ארץ אחרת

תחי ישראל -אין לנו ארץ אחרת

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

מחבר:
בתאריך:

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

פונקציה רקורסיבית ב-javascript

מדריך זה משתמש בידע שאותו פיתחנו בסדרת המדריכים בנושא של פונקציות לטיפול במערכים של 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 כוכבים

 

 

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

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

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

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

השימוש שלך באתר מהווה ראייה להסכמתך עם הכללים והתקנות שנוסחו בהסכם תנאי השימוש.

הוסף תגובה חדשה

 

 

ענה על השאלה הפשוטה הבאה כתנאי להוספת תגובה:

איך אומרים בעברית אינטרנט?