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

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

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

אפשר לסמן את התוכנית בעזרת האלגוריתם הבא:

שעון_מעורר (שעה רצויה = 7:30)

בדיקת שעה נוכחית.

אם (שעה נוכחית = שעה רצויה) ←  Play baby shark do do do do do do

אחרת ← נחכה דקה ונקרא לפונקציה שעון_מעורר (שעה רצויה = 7:30)

מה התוכנית שלנו מבצעת בעצם? הפונקציה קוראת לעצמה שוב ושוב עד לתנאי עצירה מוגדר - הגעה לשעה הנכונה. כל עוד לא הגענו לשעה שנבחרה, היא תעצור ותבדוק שוב בעוד דקה. הפונקציה מקבלת בכל קריאה את אותה הפקודה - הגדרת שעה להתעוררות. אין צורך לקרוא לתוכנית אחרת כי התוכנית שלנו מבצעת את כל הפעולות הנדרשות, והיא תמיד מסתפקת באותו המידע ומחכה בסבלנות לרגע הנכון. אם נגדיר את הפונקציה בצורה שאינה מדויקת מספיק נוכל להגיע למצב שבו התוכנית רצה לנצח מבלי להפעיל את השעון המעורר. לדוגמה - אם תנאי העצירה שלנו יהיה הגעה לשעה שאינה קיימת (כמו למשל 24:15), או שנגדיר קפיצות שמדלגות על השעה המבוקשת (למשל תוכנית שמתעוררת רק בדקות עגולות, כשהשעה המוגדרת להשכמה היא 7:30:30). במצבים כאלה התוכנית שלנו תרוץ בלי הפסקה ונישן שנת מלכים ללא הפרעות עד ליקיצה טבעית.

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

סדרת פיבונאצ'י [3] היא סדרה המוגדרת בצורה רקורסיבית. בסדרה זו האיברים הראשונים הם: F0=0, F1=1, וכל איבר הבא בתור בסדרה הוא סכום שני האיברים הקודמים לו: Fn=Fn-1+Fn-2.

דוגמה מתמטית נוספת לרקורסיה היא עצרת, המסומנת בסימן !. תוצאת העצרת של איבר היא מכפלת כל האיברים מ-1 ועד אליו, כאשר: 0!=1.

כך:

!(n!=n*(n-1)!=n*(n-1)*(n-2

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

רקורסיה יכולה להופיע גם בצורות גאומטריות. ישנן צורות בעלות דמיון עצמי כך שהן מורכבות מעותקים קטנים של עצמן (סוג של פרקטל [4]). אם נבחן חלק של צורה כזו תחת הגדלה, המראה שיתגלה יזכיר בצורתו את הצורה המקורית. כך הצורה מוגדרת מאוסף של צורות, אשר כל אחת מהן היא אוסף של צורות הדומות לצורה הראשית. צורות בעלות דמיון עצמי מוגדרות רקורסיבית בעזרת פעולה שחוזרת על עצמה מספר רב של פעמים. מבנים כאלו מצויים בטבע בתפרחת הכרובית, בפתיתי שלג, בכלי דם ועוד. מבנים כאלו שימושיים מאוד בגרפיקה ממוחשבת, מאחר שהם מאפשרים ליצור צורות מורכבות כמו עלים, עצים, פתיתי שלג וכו'.

בתמונה: כרובית רומנסקו, מין כרובית בעלת דמיון עצמי (צילום: נעה זילברמן)

קיימת שיטת מיון שנקראת "מיון מהיר" (Quicksort), המשתמשת ברקורסיה למיון מערך איברים [5]. תנאי העצירה של השיטה מתקיים כאשר היא נתקלת במערך בעל איבר אחד ומכריזה, "המערך הזה ממוין". כל עוד גודל המערך גדול מ-1 היא בוחרת איבר מהמערך באקראי ומסדרת את המערך כך שכל האיברים הגדולים ממנו ימוקמו מימינו וכל האיברים הקטנים ממנו משמאלו. כך מתקבלים שני מערכים - המערך הקטן והמערך הגדול. האם הם מכילים איבר אחד? אם כן, זהו תנאי העצירה שלנו. אם לא - נפעיל שוב את בחירת האיבר האקראי והסידור מימין ומשמאל וכך הלאה לכל תתי המערכים המוכלים במערך.

דוגמה למיון מערך בשיטת quicksort בעזרת רקורסיה (קרדיט: Matt Chan)

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

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

עריכה: שיר רוזנבלום-מן

מקורות לקריאה נוספת:

[1] תמונת המוצר של חברת דרוסטה

[2] דוגמאות נוספות לאפקט דרוסטה

[3] פוסט שלנו בנושא פיבונאצ'י ויחס הזהב

[4] סרטון על פרקטלים ועל צורות בעלות דמיון עצמי (רמז - זה לא אותו דבר)

[5] הסבר ומימוש לאלגוריתם Quicksort מתוך האתר GeeksforGeeks

[6] להתנסות בקוד - קישור לעמוד Github של העמותה