שלח תשובה

זירת השאלות

1958
צפיות
2
תשובות

רקורסיה

,‏ 18 בינואר, 2015

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

תגיות: ,

2 תשובות

  1. Roi Trigerman הגיב:

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

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

    דוגמה: נגיד שאתה צריך לחשב את סכום המספרים מ-1 ועד למספר מסויים שהמשתמש בוחר:

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

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

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


    private static int Calc(int n)
    {
    if(n == 1)
    return 1;
    return n+ Calc(n-1);
    }

    עבור המספר 4 למשל, הפונקציה תחזיר 4 + תוצאת הפונקציה עבור המספר 3 {שזה 3 + תוצאת הפונקציה עבור 2, [שזה 2 + תוצאת הפונקציה עבור 1, (שזה 1)]}.
    או 4+{3+[2+(1)]} = 10

    התוצאה היא פונקציה פשוטה של 3 שורות שמבצעת את החישוב ה"מסובך" הזה.
    מקווה שהיה ברור 🙂

שלח תשובה