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

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

פונקציה היא שגרה שמחזירה לתוכנית הקוראת לה ערך מסוים, שהוא תוצאת פעולתה של הפונקציה. הפונקציה יכולה לקבל קלט (פרמטר אחד או יותר) אשר ישפיע על פעולתה. דוגמה: הפונקציה MAX שמקבלת כקלט מספר כלשהו של ערכים מספריים, ומחזירה את הגדול מביניהם.
יש מקרים בהם פונקציה יכולה לקרוא לעצמה . זוהי למעשה תהיה פונקיצה רקורסיבית.
ניקח לדוגמא את פעולת החישוב "עצרת".
במתמטיקה, עצרת (באנגלית factorial), היא פונקציה המתאימה לכל מספר טבעי n את המכפלה של כל המספרים הטבעיים מ-1 עד מ זה בזה. ( הסימון שלה היא סימן קריאה, ! ). למשל, !5 הוא בעצם פעולת 5*4*3*2*1 = 120.
ניתן לממש את פעולה זו באמצעות הפונקציה הבאה (לא רקורסיבית) :
(public int func(int n
{
int out  = 1
(++for (int i=n ;i>0;i
out * =i;
return out ;
}
ניתן לראות את השימוש בFOR לצורך הכפלת הערכים מN עד ל1
כעת נביט בפונקציה רקורסיבית ונראה את השימוש וההבדל:
public int factorial (int n)
{
if (n==0) return 1; // מקרה קצה
else
return n * factorial(n-1); // קריאה רקורסיבית לאותה פונקציה
}
המרכיבים הדרושים לבניית פונקיצה רקורסיבית :
א. לדעת לקבוע עבור כל קלט אם הוא מקרה קצה או לא
ב. לכל מקרה קצה לחשב את הפלט ללא קריאות רקורסיביות נוספות
ג. כל קלט שאינו מקרה קצה עלינו לדעת לחשב את הקלט בעזרת קריאות רקורסיביות
ד. כל סדרה של קריאות רקורסיביות תגמר במקרי קצה
ניתן לסכם ולומר שפעולה רקורסיבית היא אדיאלית לפתור מספר מסוים של בעיות
אבל לא בהכרח שתמיד מומלץ להשתמש בה עקב לעיתים שימוש נרחב יותר בזיכרון ומשאבים אחרים.