רקורסיה

רֵקוּרְסִיָּה (בעברית: נסיגה) היא תופעה שכל מופע שלה מכיל מופע נוסף שלה, כך שהיא מתרחשת ומשתקפת בשלמותה בתוך עצמה שוב ושוב.
רקורסיה יכולה להיות רקורסיית עצירה (או רקורסיית קצה), כאשר יש בה "סף עצירה" – רמה שמתחתיה לא מתקיימת עוד רקורסיה, או רקורסיה אינסופית כאשר בכל רמה תכיל התופעה תופעות משנה מאותו סוג.
רקורסיה הדדית מתרחשת בין שתי תופעות או יותר, כאשר האחת מכילה את השנייה וחוזר חלילה: א' מכיל מופע של ב', וב' מכיל מופע של א' (אם נביט על א' וב' כאחד – הם מקיימים רקורסיה רגילה), למשל כאשר מוצבת מראה מול מראה.

רקורסיה חזותית

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

רקורסיה תודעתית

חלום בתוך חלום. לעיתים כאשר אנו ישנים וחולמים, בתוך החלום אנו חולמים שאנחנו ישנים וחולמים, או מצב בו אנו מדמיינים שאנו מדמיינים.

רקורסיה לשונית

רקורסיה לשונית היא משפט עומק אשר מוטמע בתוך משפט המוצא, שיכול להמשיך עוד ועוד.
למשל: "טיפש מי שקנה את הכובע הזה, ולא יודע שכתוב עליו: טיפש מי שקנה את הכובע הזה ולא יודע שכתוב עליו...". או: "נחש נשך את הנחש, שנשך את הנחש...", וכן: "הוא חושב שאני חושב שהוא חושב שאני חושב...".
רקורסיה לשונית תיתכן גם בראשי תיבות. לדוגמה: פרויקט גְּנוּ – GNU הוא ראשי תיבות רקורסיביים של "GNU's Not Unix" (גנו הוא לא יוניקס). מערכת ההפעלה Xinu היא גם ראשי תיבות רקורסיביים של "Xinu Is Not Unix" (זינו היא לא יוניקס) וגם היפוך סדר האותיות בשם Unix.
דוגמה לרקורסיה לשונית בעברית היא ראשי תיבות בדיעבד למילה שבת – שינה בשבת תענוג (ילקוט ראובני, פרשת ואתחנן).
ברקורסיה לשונית מורכבת יותר, שכוללת את כל הפתגם בתוך עצמו, משתמש משורר תהלים בפסוק "אמת מארץ תצמח" (פה, יב). האבודרהם שהבחין ברקורסיה מסביר אותה: "ראשי תיבות – אמת, תיבות שניות – מארץ, תיבות אחרונות – תצמח."

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

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

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

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

מיהו יהודי

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

מיון

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

חיפוש

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

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

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

מגדלי האנוי

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