רקורסיה

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

עצרת

ערך מורחב – עצרת (מתמטיקה)

בעבור מספר נתון $n$, נוכל לחשב באמצעות אלגוריתם רקורסיבי את העצרת של $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}$.

מגדלי האנוי

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

דוגמאות נוספות

מחשבים

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

ראו גם

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

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

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