רקורסיה

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

פתרון רקורסיבי:

Procedure Factor(n)
  If n=1 return 1;
  Else
    X = Factor(n-1);
    Return (n*x);
  End;
End;

פתרון בעזרת לולאה:

Procedure Factor(n)
  X = 1;
  For I=1 to n
    X = x*I;
  Return(x);
End;

למה הפתרון הרקורסיבי יעבוד?

נחשב עצרת של 3:

מכיוון ש- 3 לא שווה ל- 0, תתבצע קריאה להעתק חדש של הפונקציה. הפעם עם 2. מכיוון שגם 2 שונה מ- 0, תתבצע קריאה להעתק שלישי של הפונקציה, הפעם עם הערך 1, ולכן ההעתק הזה יחזיר 1, ההעתק השני יכפיל את הערך המוחזר 1 ב 2 ולכן יחזיר להעתק הראשון את הערך 2. ההעתק הראשון יחזיר 2*3 =6 וזאת כמובן התשובה.
מכיוון שלא נוכל לבצע בדיקה כזאת עבור מספרים גדולים דרך העבודה תהיה "אמונה". כשנרצה לבדוק פונקציה כזאת נתייחס לקריאה הרקורסיבית כאילו היא מחזירה את הערך הרצוי, ונבדוק אם ההעתק הראשון. כמו כן יש לבדוק את כל מקרי הקצה, ולבדוק שכל מקרי הקצה האפשריים מטופלים.
במקרה שלנו נבדוק ש1 עצרת באמת שווה 1, ושאם (Factor(2 תחזיר 2, העתק הראשון יחזיר 2*3=6. וזה נכון, לכן הפונקציה תעבוד. כדי לבדוק את הבנתך, תוכל לפתור את שאלות חזרה מספר 2,3.

עוד על רקורסיה: חלקי הרקורסיה.