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

asili2

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

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

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

EndersG

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

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

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

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

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