רקורסיה

משולש שרפינסקי – רקורסיה של משולשים אשר יוצרת סריג פרקטלי

רקורסיה הנוצרת בעזרת תוכנה ללכידת מסך המצלמת את עצמה בפעולה

רֵקוּרְסִיָּה (בעברית: נסיגה) היא תופעה שכל מופע שלה מכיל מופע נוסף שלה, כך שהיא מתרחשת ומשתקפת בשלמותה בתוך עצמה שוב ושוב.

רקורסיה יכולה להיות רקורסיית עצירה (או רקורסיית קצה), כאשר יש בה "סף עצירה" – רמה שמתחתיה לא מתקיימת עוד הרקורסיה, או רקורסיה אינסופית כאשר בכל רמה תכיל התופעה תופעות משנה מאותו סוג.

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

הגדרה רקורסיבית

הגדרה היא הגדרה רקורסיבית אם היא מסתמכת על עצמה. דוגמאות:

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

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

בציור זו נראית אישה האוחזת ספל שבתוכו ציור האישה האוחזת ספל וכן הלאה.

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

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

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

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

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

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

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

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

דוגמה לרקורסיה לשונית בעברית היא ראשי תיבות בדיעבד למילה שבת – שינה בשבת תענוג (ילקוט ראובני, פרשת ואתחנן).

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

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

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

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

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

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

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

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

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

עצרת

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

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

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

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

• $\ F(n)=n\cdot F(n-1),n>0$
• $\ F(0)=1$

את פונקציית העצרת, המוגדרת לפי נוסחת המכפלה $\ n!=1\cdot 2\cdot 3\cdots n$, אפשר להגדיר גם באופן רקורסיבי, כך: $\ n!=(n-1)!\cdot n$ עם תנאי עצירה $\ 0!=1$.

מיהו יהודי

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

מיון

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

חיפוש

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

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

סדרת פיבונאצ'י מוגדרת באופן רקורסיבי: האיברים הראשונים הם $\ F_{0}=0$ ו- $\ F_{1}=1$, ולכל $\ n>1$ מגדירים $\ F_{n+1}=F_{n}+F_{n-1}$.

מגדלי האנוי

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

ראו גם

• פרקטל
• מדעי המחשב
• שאילתות היררכיות ורקורסיביות ב-SQL

קישורים חיצוניים

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