רקורסיה

רקורסיה

מהי?

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

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

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

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

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

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

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

סדרת פיבונאצי תראה כך:   . 

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

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

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

public static [ערך מוחזר] שם_הפונקציה ( [פרמטרים] )

{

if(תנאי עצירה)

return ערך של נקודת התחלה]]

else

return שם_הפונקציה([פרמטרים שונים המקדמים את הפתרון לבעיה])

}

לדוגמה פתרון לבעיית החזקה עם פונקצייה רקורסיבית:

הפעולה תקבל מספר num1 וnum2, הפעולה תחזיר num1 בחזקת num2.

public static int Hezka(int num1, int num2)

        {

            if (num2 == 0)

                return 1;

            if(num2==1)

                return num1;

            else

                return num1 * Hezka(num1, num2-1);

        }

משימות:

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

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