רקורסיה-פתרון טוב לעצלנים ונאיבים
לא , אני לא בא לעקוץ שה באמת כך. הרעיון בגישת פתרון רקוקסיבית היא: "אני אבדוק אם יש פתרון כבר מוכן - אם כן , יופי! סיימתי. אחרת אעשה צעד אחד ואתן למישהו אחר לעבוד על השאר. ניקח דוגמא מאוד פשוטה -עצרת, בפסאודו קוד הפתרון נראה כך:
int func_AZERET(int n) { if ( n==1 ) return n; else return n*func_AZERET(n-1) }
אני בטוח שכבר ניתקלת בפתרון הזה ולכן בחרתי אותו הרעיון הוא ש func_AZERET מקבלת מספר N אם הוא 1 היא מכריזה בגאווה : "סיימתי" אחרת היא נותנת לfunc_AZERET אחרת לחשב את התוצאה עבור N-1 ומחשבת את המכפלה עכשיו אנסה להמחיש איך תוכל לעקוב על דף ולהבין מי נגד מי. עכשיו נראה דרך נוחה להריץם את זה על דף :
bgein n=6 n=6 func_AZERET(6)=6*func_AZERET(5) n=5 func_AZERET(5)=5*func_AZERET(4) n=4 func_AZERET(4)=3*func_AZERET(2) n=3 func_AZERET(3)=3*func_AZERET(2) n=1 func_AZERET(1)=1 //yeapy hey
OK הגענו לעצירה ועכשיו מתחילים לעלות במעלה הדף ולכתוב מלמטה למעלה את התוצאות. הרי רקורסיה מבוצעת בתוך מחסנית התכנית ולכן היא מתנהגת כמו מחסנית (אם לא הבנת את המשפט האחרון - לא נורא המשך לקרוא ותבין את הרעיון). אתה ממשיך לכתוב על אותו הדף - אין צורך להעתיק הכל שוב כפי שאני עושה:
bgein n=6 n=6 func_AZERET(6)=6*func_AZERET(5) n=5 func_AZERET(5)=5*func_AZERET(4) n=4 func_AZERET(4)=3*func_AZERET(2) n=3 func_AZERET(3)=3*func_AZERET(2) //(אנחנו יודעי את התוצאה ל2 ולכן ניתן לחשב עבור 3): n=2 func_AZERET(2)=2*func_AZERET(1)=2 //(אנחנו יודעי את התוצאה ל1 ולכן ניתן לחשב עבור 2): n=1 func_AZERET(1)=1 //yeapy hey
n=4 func_AZERET(4)=3*func_AZERET(2) n=2 func_AZERET(2)=2*func_AZERET(1)=2 //(אנחנו יודעי את התוצאה ל1 ולכן ניתן לחשב עבור 2): n=1 func_AZERET(1)=1 //yeapy hey
ממשיכים:
bgein n=6 n=6 func_AZERET(6)=6*func_AZERET(5) n=5 func_AZERET(5)=5*func_AZERET(4) n=4 func_AZERET(4)=3*func_AZERET(2) n=4 func_AZERET(4)=3*func_AZERET(2) //(אנחנו יודעי את התוצאה ל2 ולכן ניתן לחשב עבור 3): n=2 func_AZERET(2)=2*func_AZERET(1)=2 //(אנחנו יודעי את התוצאה ל1 ולכן ניתן לחשב עבור 2): n=1 func_AZERET(1)=1 //yeapy hey
כוד שלב אחד לדוגמא ומשם תסיים לבד:
bgein n=6 n=6 func_AZERET(6)=6*func_AZERET(5) n=5 func_AZERET(5)=5*func_AZERET(4) n=4 func_AZERET(4)=3*func_AZERET(2)=4*6 //(אנחנו יודעי את התוצאה ל3 ולכן ניתן לחשב עבור 4): n=3 func_AZERET(3)=3*func_AZERET(2)=3*2=6 //(אנחנו יודעי את התוצאה ל2 ולכן ניתן לחשב עבור 3): n=2 func_AZERET(2)=2*func_AZERET(1)=2 //(אנחנו יודעי את התוצאה ל1 ולכן ניתן לחשב עבור 2): n=1 func_AZERET(1)=1 //yeapy hey
אני מקווה שהבנת את הרעיון.