מחפש חומר על רקורסיות

[asili2]

מחפש חומר על רקורסיות

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

 

[RBA]

הנה../images/Emo3.gif

 

[maromnn]

חחחחחחחחחחח יפה יפה ../images/Emo6.gif

 

[selalerer]

../images/Emo45.gif אותי זה הצחיק ../images/Emo13.gif

 

[מאה קולפה]

וה-הגדרה

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

 

[EndersG]

רקורסיה-פתרון טוב לעצלנים ונאיבים

לא , אני לא בא לעקוץ שה באמת כך. הרעיון בגישת פתרון רקוקסיבית היא: "אני אבדוק אם יש פתרון כבר מוכן - אם כן , יופי! סיימתי. אחרת אעשה צעד אחד ואתן למישהו אחר לעבוד על השאר. ניקח דוגמא מאוד פשוטה -עצרת, בפסאודו קוד הפתרון נראה כך:

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

אני מקווה שהבנת את הרעיון.

 

[vinney]

הוכחת נכונות אלגוריתם רקורסיבי

בשפה קצת יותר מסודרת מה שאמרת: על מנת להוכיח שרקורסיה עובדת יש לקיים שני דברים: 1. תנאי העצירה תמיד מתקיים (ז"א האלגוריתם עוצר תמיד, אחרת הוא נכון חלקית) אם האלגוריתם עובד עבור קלט N, אז הוא עובד גם עבור קלט N+1. זה הכל

אז במקרה שלך: if (Azeret(N) correct) then (N+1)*Azeret(N) correct (obvious) if N<=0 return 1 - always happens אז אלגוריתם נכון​

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