רקורסיה | אלגוריתם רקורסיבי
English: Recursion

אלגוריתם רקורסיבי

ציור של עץ בעזרת פונקציה רקורסיבית, נכתב בלוגו

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

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

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

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

עצרת

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

כך, לצורך חישוב , האלגוריתם יפעיל את עצמו לקבלת , אז יפעיל את עצמו לקבלת , אז יפעיל את עצמו לקבלת , ואז יפעיל את עצמו לקבלת במקרה זה האלגוריתם יחזיר את הערך "1",שיוכפל ב-2, שיוכפל ב-3, ויוכפל ב-4 לקבלת התוצאה הרצויה – 24.

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

תיאור פורמלי של האלגוריתם:

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

מיהו יהודי

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

מיון

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

חיפוש

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

מספר פיבונאצ'י

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

מגדלי האנוי

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