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

לקריאת הגרסה האנגלית של המדריך Recursion in PHP - when to use and how

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

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

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

5 x 4 x 3 x 2 x 1 = 120

כל מספר במכפלה קטן ב-1 מהקודם לו עד שמגיעים לספרה 1.

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

אבל אם תנסו להריץ את הפונקציה הרקורסיבית הבאה תקבלו שגיאה:

function calcFactorial($num) 
{
  return ($num * calcFactorial($num-1)); 
}
calcFactorial(5);

זו השגיאה שאני קיבלתי כשניסיתי להריץ את הקוד על המחשב שלי:

Fatal error: Allowed memory size of 1048576000 bytes exhausted (tried to allocate 262144 bytes)

מדוע?

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

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

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

function calcFactorial($num) 
{
  if ($num <= 1) { 
    return 1; 
  } else { 
    return ($num * calcFactorial($num-1)); 
  } 	
}
calcFactorial(5);

כך מנענו את השגיאה, וקיבלנו את התשובה הנכונה.

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

למה לא כדאי להשתמש ברקורסיה?

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

function calcFactorial($num) 
{
  $val = 1;
  for($x = $num; $x >= 1; $x--){
    $val *= $x;
  }
  
  return $val;
}
echo calcFactorial(5);

הלולאה רצה מ-5 ל-1 ומחזירה את תוצאת המכפלה. בנוסף, שימוש בלולאות הוא זול יותר מבחינת משאבי מחשוב מאשר שימוש ברקורסיה.

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

היכן כדאי להשתמש ברקורסיה?

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

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

כל פריט ב-JSON מכיל את הפרטים הבאים:

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

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

$animals = '{"animals":[
  {"name":"apes","parent":"mammals","link":"//animals.com/mammals/apes"},
  {"name":"fishes","parent":"animals","link":"//animals.com/fishes"},
  {"name":"animals","parent":"kingdom","link":"//animals.com"},
  {"name":"mammals","parent":"animals","link":"//animals.com/mammals"},
  {"name":"marsupials","parent":"mammals","link":"//animals.com/mammals/marsupials"},
  {"name":"opossums","parent":"marsupials","link":"//animals.com/mammals/marsupials/opossums"},
  {"name":"big apes","parent":"apes","link":"//animals.com/mammals/big-apes"},
  {"name":"birds","parent":"animals","link":"//animals.com/birds"},
  {"name":"cats","parent":"mammals","link":"//animals.com/mammals/cats"},
  {"name":"big cats","parent":"cats","link":"//animals.com/mammals/cats/big-cats"},
  {"name":"domestic cats","parent":"cats","link":"//animals.com/mammals/cats/domestic-cats"},
  {"name":"persian cats","parent":"domestic cats","link":"//animals.com/mammals/cats/domestic-cats/persian-cats"},
  {"name":"chimpanzee","parent":"big apes","link":"//animals.com/mammals/big-apes/chimpanzee"}
]}';

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

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

הפונקציה הרקורסיבית הראשונה היא makeTree שמסדרת את הרשימה בסדר היררכי בתוך מערך רב-מימדי. הפונקציה מקבלת שני פרמטרים: $arr הוא המערך שבנתה הפונקציה בכל פעם שהיא רצה. $branch הוא שם הקבוצה הנוכחית שמחפשים את הקבוצות שנמצאות מיד מתחתיה בהיררכיה.

// // recursive function to create the hierarchy
function makeTree($arr=[], $branch="") 
{
  $tree=[];
   
  foreach($arr as $item) {
    if($item["parent"] === $branch) {
      $item["children"]  = makeTree($arr,$item["name"]);
      $tree[$branch][] = $item;
    }
  }
 
  return $tree;
}

• הפונקציה מקבלת שני פרמטרים: המערך שהפונקציה בונה בתהליך, $arr, ושם הענף שהיא צריכה לחפש את הילדים שלו, $branch.
• המטרה של הפונקציה היא לבנות מערך רב מימדי , $tree, שכולל את כל הילדים של הצעד הנוכחי.
• הפונקציה רצה על רשימת הפריטים במערך שהיא מקבלת ($arr) עד שהיא מוצאת פריט שההורה שלו זהה ל $branch.
• עבור הפריט שהיא מוצאת היא מחפשת את הפריטים הילדים שאותם היא מוצאת באמצעות קריאה נוספת לפונקציה עם השם של הענף הנוכחי. קריאה נוספת לפונקציה מתוך הפונקציה כל עוד מתקיים התנאי זו הרקורסיה.
• כל אחד מהילדים שהפונקציה מוצאת נוסף למערך הרב ממדי $tree שהפונקציה בונה בתהליך.
• איפה התנאי לעצירה? הפונקציה קוראת לעצמה רק בתנאי שלפריט יש ילדים.

הפונקציה הרקורסיבית השנייה, makeNav, רצה על הפלט של הראשונה ומייצרת את מבנה ה-HTML של רשימת מקוננת של קישורים (רשימה בתוך רשימה). הפונקציה מקבלת בתור פרמטר את המערך שמקורו בפונקצייה makeTree:

// build the multilevel HTML
function makeNav($arr=[]) 
{
  $nav='<ul>';
  
  foreach($arr as $key => $val) {
    if($val["children"] && count($val["children"]) > 0) {
      $nav .= '<li>';
      $nav .= "<a href="{$val['link']}">{$val['name']}</a>";
      $nav .= '<ul>';
      foreach($val["children"] as $item) {
        $nav .= makeNav($item);
      }
      $nav .= '</ul>';
      $nav .= '</li>';
    } else {
      $nav .= '<li>';
      $nav .= "<a href="{$val['link']}">{$val['name']}</a>";
      $nav .= '</li>';
    }
  }
  $nav .= '</ul>';
	
  return $nav;
}

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

$rootName = "kingdom";

$animalsArray = json_decode($animals, true);

$tree = makeTree($animalsArray["animals"], $rootName);

$nav  = makeNav($tree[$rootName]);

echo $nav;

רקורסיה שרצה על מערכת הקבצים

גם מערכת הקבצים עשויה להיות בעלת מבנה שחוזר על עצמו מספר לא ידוע של פעמים (תיקייה בתוך תיקייה בתוך תיקייה), אבל אם נתקלתם בבעיה אז עדיף לפתור אותה באמצעות קלאס מובנה של PHP, recursive directory iterator.

לסיכום

במדריך זה למדנו ש:

• פונקציה רקורסיבית היא פונקציה שקוראת לעצמה עד שהיא מפסיקה.
• רקורסיה פותרת את הבעיה של עבודה עם נתונים המאופיינים במבנה היררכי ומספר לא ידוע של התפצלויות. לדוגמה, מבני נתונים שמקורם ב-XML ו-HTML.
• אם נדמה לך שפונקציה רקורסיבית היא הפתרון לבעיה שאותה אתה מנסה לפתור חשוב שנית. רוב הסיכויים, שתוכל לפתור את הבעיה באמצעות לולאה או באמצעות פתרון תכנותי קיים כדוגמת directory iterator של PHP.

ליתר מדריכי ה-PHP באתר רשתטק

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

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