ב-Online
 
 
 
 
 
 
 
לפרק את הבייט 
מי מפחד מרקורסיה? 
 
 צילום מסך במעגל סגור: גם זה סוג של רקורסיה    צילום: עידו גנדל    
לפרק את הבייט |
 

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

 
 
 
 
 
 
 
 
 
 
רקורסיה. קוראת לעצמה, לא קוראת לעצמה - אתם סתם מסבכים
 רקורסיה. קוראת לעצמה, לא קוראת לעצמה - אתם סתם מסבכים 
 צילום: flickr, gadl, cc by sa 
 
עבור רוב המתכנתים, הפגישה הראשונה עם רקורסיה זכורה כאירוע לא נעים. מדובר בטכניקה מאד אלגנטית ומאד שימושית לפתרון בעיות תכנות, אך משהו באופן שבו מנסים ללמד אותה גורם לה להיראות כמו מין הוקוס-פוקוס מסובך וחסר היגיון שכדאי לשמור ממנו מרחק. בז'רגון המתכנתים מקובל לתאר פונקציה רקורסיבית כ"פונקציה שקוראת לעצמה". מה זה אמור להביע, לכל הרוחות? ניסיתם פעם לקרוא לעצמכם? מה יצא מזה? השבוע ננסה להסביר את הרעיון של רקורסיה באופן מובן, ועל הדרך גם להבין למה מתכנתים מתחילים מתקשים בו.
 

פונקציה של דוגמאות בעייתיות

 
סיפורנו מתחיל ברעיון של פונקציה. פונקציה (במובן התכנותי של המילה) היא קטע קוד מוגדר ועצמאי יחסית, עם קלט ופלט משלו, ש"יושב" מחוץ לגבולות הקוד שרץ כרגע. למעשה, הוא יכול "לשבת" אפילו מחוץ לקובץ התוכנה! קובצי DLL, למשל, מכילים בעיקר פונקציות שיכולות לשמש כל תוכנה שמעוניינת ויודעת להתממשק איתן. הפעלה של פונקציה על ידי תוכנה, או על ידי פונקציה אחרת, נקראת "קריאה" (במובן Call ולא במובן Read). בעולם התכנות המודרני שום דבר הוא לא פשוט כמו שהיינו רוצים, אבל לפי התפיסה הקלאסית והנפוצה, כאשר תוכנה קוראת לפונקציה היא בעצם מעבירה לה את השליטה ולא עושה כלום עד שהפונקציה מסיימת את תפקידה.

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

סיבה נוספת לבלבול טמונה בעובדה, שהדוגמאות הראשונות שנבחרות להמחשת הרקורסיה הן כמעט תמיד דביליות. המפורסמת מכולן היא העצרת ("!n"), הלא היא מכפלת כל המספרים השלמים שבין 1 ל-n (כולל). לדוגמה, הערך של 4! הוא 4x3x2x1, כלומר 24. מימוש של עצרת באמצעות לולאה בסיסית הוא פשוט, אינטואיטיבי ובפועל גם יעיל ומהיר יותר מהמימוש הרקורסיבי. באמת, בדקנו. התלמיד האומלל, אם כך, תופס את הרקורסיה רק כשיטה לסבך דברים מובנים מאליהם, בערך כמו לבצע פעולת כפל באמצעות המון פעולות חיבור נפרדות. מורה מבין עניין אך חסר טאקט עלול לסבך את המצב עוד יותר ולגלות לתלמיד את הסוד הנורא, שכל אלגוריתם רקורסיבי אפשר לממש גם בלי רקורסיה. אז בשביל מה לטרוח?
 
פונקציות עצרת בדלפי: הרקורסיבית (למעלה) והיעילה (למטה)
 פונקציות עצרת בדלפי: הרקורסיבית (למעלה) והיעילה (למטה)   צילום: עידו גנדל 
 
 

בעיה מהעולם האמיתי

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

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

איך להבין את הרקורסיה

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

כפי שציינו קודם, קשה מאד להבין את התהליך הזה מקריאת הקוד לבדו. אם אתם רוצים להתנסות בצורה הטובה ביותר באופן העבודה של רקורסיה, העתיקו את תמונת ריבוע הפיקסלים מקודם והדפיסו אותה. הדפיסו גם 25 עותקים של הפסודו-קוד שלמעלה. רצוי להדפיס עותקים רבים על אותו דף ולגזור אותם ככרטיסים נוחים לעבודה. בחרו כרטיס אחד שישמש כ"קריאה" הראשונית לפונקציה וכתבו בו, בתוך הסוגריים ליד כותרת הפונקציה, את הערכים 3 ו-3 עבור X ו-Y. זה יהיה הפיקסל המרכזי ממנו מתחילים (מסומן ב-X באיור). כעת, בכל פעם שאתם מגיעים לקריאה ל"צביעה_רקורסיבית", הניחו על הכרטיס הנוכחי כרטיס חדש וכתבו בו את ערכי ה-X וה-Y בהתאם למה שהיה כתוב בראש הכרטיס שממנו התבצעה הקריאה. למשל, כיוון שהקריאה הראשונה היא עם ערך Y זהה וערך X מינוס 1, הקריאה הראשונה מכרטיס X=3, Y=3 תהיה עם X שערכו 2 ו-Y שערכו 3. המשיכו לעבוד על כל כרטיס לפי הסדר, וכשסיימתם כרטיס מסוים פשוט הורידו אותו מהערמה והמשיכו מהמקום אליו הגעתם בכרטיס הקודם. לנוחותכם, הוספנו תיבות סימון לכל שורה, בהן תוכלו לסמן כל פקודה עם ביצועה כדי לזכור איפה הייתם. חשוב לסמן כל קריאה ל"צביעה_רקורסיבית" לפני שעוברים לכרטיס חדש, כדי לצמצם את הבלבול.
 
 
בתמונה הבאה מוצג התהליך השלם בצורת עץ, שמתחיל בכרטיס של x=3, y=3. כל כרטיס הוא עותק של הפונקציה שלנו, כאשר כל "כניסה" שמאלה מסמנת עותקים שנוצרו על ידי העותק שמימינם. שימו לב שלכל כרטיס יש או אפס צאצאים (תנאי העצירה התקיים בו) או ארבעה צאצאים – אחד לכל קריאה רקורסיבית בפונקציה. ערמת הכרטיסים, שצוברת או מאבדת גובה תוך כדי עבודה בשיטה שהצגנו קודם, היא למעשה ייצוג מדויק להפליא של מה שקורה בתוך המחשב. כשהפונקציה קוראת לעצמה היא יוצרת עותקים חדשים, וכשעותק מסיים את תפקידו הוא מחזיר את השליטה לאותו עותק ספציפי שקרא לו. אגב, רקורסיה לא חייבת להתבצע עם פונקציה אחת בלבד – יכולות בהחלט להיות רקורסיות עם שתי פונקציות או יותר שקוראות אלה לאלה.
 
אם נחזור לרגע לאותה שורת תנאי שבתחילת הפונקציה, מדובר באלמנט מרכזי וקריטי בכל רקורסיה – תנאי העצירה. תנאי זה מסמן את ה"תחתית", או ה"קצוות" של העיבוד, שמהם אין לאן להמשיך. אם לא נגדיר אותם בבירור, או אם נעשה טעות כלשהי בהגדרתם, הפונקציה עלולה לקרוא לעותקים של עצמה שוב ושוב ללא סוף. במובן מסוים זה יותר גרוע מאשר לולאה אינסופית, משום שלולאה אינסופית רק מעסיקה את המעבד לשווא, ואילו רקורסיה אינסופית תופסת, בנוסף, כמות עצומה של זיכרון! כיוון שמדובר בעותקים שונים ונפרדים של הפונקציה, כל עותק תופס מקום משלו בזיכרון המחשב עד שזה עולה על גדותיו והתוכנה קורסת.

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

עוד חדשות, כתבות ומאמרי טכנולוגיה בטוויטר של nana10 מחשבים
 
 
 
@@@@@@@@@@@@@@@@@@@ ilan @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
 
@@@@@@@@@@@@@@@@@@@ ilan @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
 
 
תגובות
הוסף תגובה0 תגובות
הוספת תגובה
מאת
 
נושא
 
תוכן
 
 
 
 
תודה! תגובתך התקבלה.
התגובה תתפרסם בכפוף לתנאי האתר.
 
 
 
 
 

כל הזכויות שמורות 2011 © נענע 10 בע"מ
 
 
 
 
כל הזכויות שמורות © Nana10 בע"מ
Video powered by