רקורסיה

מתוך ויקיפדיה, האנציקלופדיה החופשית

יש לך הודעות חדשות (השווה לגרסה הקודמת).

רקורסיה (Recursion) היא תופעה שכל מופע שלה מכיל מופע נוסף שלה, כך שהיא מתרחשת ומשתקפת בשלמותה בתוך עצמה שוב ושוב.

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

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

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

[עריכה] הגדרה רקורסיבית

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

[עריכה] רקורסיה חזותית

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

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

[עריכה] רקורסיה תודעתית

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

[עריכה] רקורסיה לשונית

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

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

רקורסיה לשונית תתכן גם בראשי תיבות. לדוגמה: פרויקט גְּנוּ - GNU הוא ראשי תיבות רקורסיביים של "GNU's Not Unix" (גנו הוא לא יוניקס). דוגמה נוספת הם ראשי התיבות PNG , פורמט התמונות, שפרושם המקורי היה: PNG's Not Gif

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

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

[עריכה] רקורסיה משפטית

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

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

[עריכה] פונקציה רקורסיבית

פונקציות מתמטיות רבות הן פונקציות רקורסיביות (או ניתנות לתיאור גם כפונקציות רקורסיביות).

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

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

[עריכה] אלגוריתם רקורסיבי

עץ תיקיות - חיפוש במבנה עץ נעשה בדרך רקורסיבית

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

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

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

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

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

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

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

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

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

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

Fx(n) = n <Expression> Fx+1(<Expression> (<Expression> Fx+2(<Expression>)))...

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

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

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

[עריכה] מספר פיבונאצ'י

דוגמה תכנותית לשימוש ברקורסיה: פונקציה קצרה בשפת C, המחשבת את המספר ה־n־י בסדרת פיבונאצ'י באופן רקורסיבי:



int fib(int n) // returns n'th Fibonacci number
{
    if (n==0) return 1;
    if (n==1) return 1;
    return fib(n-1)+fib(n-2);
}

[עריכה] עצרת

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


Public Function Atzeret(Num As Integer) As Double
Atzeret = 1
If Num > 1 Then Atzeret = Atzeret(Num - 1) * Num
End Function

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

חזרה  NUM  פונקציה
1      1    1
2      2    2
3      3    6
4      4    24

[עריכה] מגדלי האנוי

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

[עריכה] שמונה מלכות

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