רקורסיה

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

דוגמה פשוטה של אלגוריתם רקורסיבי היא אלגוריתם לחישוב $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$

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

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

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

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

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

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

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

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

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

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

סדרת פיבונאצ'י מוגדרת באופן רקורסיבי: האברים הראשונים הם $\ 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$ עם תנאי עצירה $\ 0! = 1$ .

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

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

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

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

[עריכה] קישורים חיצוניים

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

רקורסיה

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

תוכן עניינים

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

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

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

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

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

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

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

[עריכה] עצרת

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

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

[עריכה] קישורים חיצוניים

צפיות

כלים אישיים

חיפוש

ניווט

קהילה

תיבת כלים

שפות אחרות