רקורסיה

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

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

רקורסיה (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>)))...

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

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

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

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

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

[עריכה] עצרת

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

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

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

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

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