אני שמח ששאלתם. רקורסיה היא קריאה לאותה פונקציה לקבלת פלט משמעותי, או בהגדרה מתמטית יותר - קביעת ערך התחלתי לפונקציה, קריאה לערך קודם של הפונקציה, קבלת ערכים קודמים של הפונקציה והכנסתם לפונקציה המקורית. ההסבר מסובך יותר מהדבר עצמו.
פונקצית "עצרת" היא פונקציה שמקבלת מספר טבעי(שלם וחיובי) ומחשבת את מכפלת כל המספרים הטבעיים עד לאותו מספר: <![CDATA[n! = n*(n-1)*(n-2)...(n-(n-1))
5! = 5*(5-1)*(5-2)*(5-3)*(5-4) = 5*4*3*2*1 = 120
]]>
פונקצית "עצרת" יכולה להחשב כפונקציה רקורסיבית - כלומר, פונקציה שקוראת לעצמה: n! = n*(n-1)! אם n הוא 5 אז 5! הוא 5*4!. עכשיו נציב את 4 בפונקציה, אז 4! הוא 4*3!. 5! הוא 5*4!, כלומר, 5*4*3!. נמשיך להציב את 3 בפונקציה ונקבל 3*2!, נציב את 2 בפונקציה ונקבל 2*1!. 1! הוא בעצם מכפלת 1 בעצמו (כי הוא המספר הטבעי הקטן ביותר), לכן 1! הוא 1. <![CDATA[5! = 5*4! = 5*4*3! = 5*4*3*2! = 5*4*3*2*1! = 5*4*3*2*1.
]]>
עשינו שימוש בפונקציה רקורסיבית (ע"י הצבה בפונקציה עצמה) ואכן קיבלנו את התוצאה 5! = 120.
עכשיו אתם בטח תוהים כיצד כותבים קוד של פונקציה רקורסיבית. אתם פשוט כותבים פונקציה שקוראת לעצמה. הנה פונקצית "עצרת"(factorial) בשפת vbscript:
אם תכתבו: <![CDATA[<%
function factorial(n)
if n = 0 then
factorial = 1
exit function
end if
factorial = n * factorial(n-1)
end function
%>
<% response.write factorial(5) %>
]]>
הפלט יהיה 120.
בפונקציה הנ"ל יש את כל הכללים של הפונקציה המתמטית עצרת. אנחנו מגדירים ש-1! שווה ל-1, ומגדירים ש-n! שווה למכפלת n ב-(n-1)!. לכל פונקציה רקורסיבית חייב להיות תנאי לסיום הפונקציה (אחרת תווצר לולאה אינסופית ותתקבל הודעת שגיאה של מחסור בזיכרון), תנאי זה הוא הגדרה בה אין קריאה לפונקציה. תנאי סיום הפונקציה במקרה זה הוא אם n הוא 0 אז n!=1.
אתם בטח רוצים להבין מה קורה בקוד זה. הבא נעקוב אחר פעולותיה של הפונקציה. נציב לדוגמא את המספר 6:
האם n = 0? לא.
הפונקציה מחזירה את הערך factorial(5)*6.
הפונקציה נקראת שוב, הפעם מוצב בה הערך 5: האם n = 0? לא.
הפונקציה מחזירה את הערך factorial(4)*5.
הפונקציה נקראת שוב, הפעם מוצב בה הערך 4: האם n = 0? לא.
הפונקציה מחזירה את הערך factorial(3)*4.
הפונקציה נקראת שוב, הפעם מוצב בה הערך 3: האם n = 0? לא.
הפונקציה מחזירה את הערך factorial(2)*3.
הפונקציה נקראת שוב, הפעם מוצב בה הערך 2: האם n = 0? לא.
הפונקציה מחזירה את הערך factorial(1)*2.
הפונקציה נקראת שוב, הפעם מוצב בה הערך 1: האם n = 0? לא.
הפונקציה מחזירה את הערך factorial(0)*1.
הפונקציה נקראת שוב, הפעם מוצב בה הערך 0: האם n = 0? כן.
הפונקציה מחזירה את הערך 1.
עכשיו נעקוב אחר הדרך למעלה. הפונקציה נקראה 7 פעמים, אך רק בשלב האחרון ניתן פלט, בכל השלבים בהם הוצבו 1,2,3,4,5 ו-6 הפונקציה טרם החזירה ערך.
השלב הראשון שהפונקציה חוזרת אליו הוא השלב הלפני האחרון - היכן שהוצב הערך n=1.
factorial(1) = 1*factorial(0) = 1*1 = 1.
כעת כשידוע הערך (1)factorial הפונקציה תעבור לשלב הקודם:
factorial(2) = 2*factorial(1) = 2*1 = 2.
באותו אופן יחושבו הערכים במעלה השרשרת:
factorial(3) = 3*factorial(2) = 3*2 = 6.
factorial(4) = 4*factorial(3) = 4*6 = 24.
factorial(5) = 5*factorial(4) = 5*24 = 120.
factorial(6) = 6*factorial(5) = 6*120 = 720.
מאחר ו-n=6 היה הראשון להקרא ע"י הפונקציה (והאחרון להקרא מחדש ע"י הפונקציה), הפלט שינתן הוא 720.
פונקציות רקורסיביות נוספות ניתן למצוא במאמר: div & mod
אני מקווה שהצלחתי להסביר את הרקורסיה כמו שצריך ולא סתם גרמתי לכם לכאב ראש נוראי. אם יהיו לכם כל מיני דוגמאות לפונקציות רקורסיביות, אשמח לראותן...
| 
.png)
