רקורסיה

[sigal112]

רקורסיה

שלום יש לי שאלה בשפת סי בנושא רקורסיה(פונקציה שקוראת לעצמה) למה היא משמשת ואיך היא מייעלת את העבודה תודה סיגל

 

[yair24]

כעיקרון...

כל מה שאת יכולה לעשות בעזרת לולאות את יכולה לעשות גם ברקורסיה אבל לא להפך. אחד השימושים היעילים שעולה לי כרגע בראש זה ריצה על עץ בינארי. אם את לא יודעת מה זה עץ בינארי אז בקצרה זה מבנה נתונים בעל יעילות חיפוש טובה יותר מאשר רשימה מקושרת. (שכמובן בדומה לרשימות מקושרות, גם העץ הבינארי משתמש בפוינטרים, פעם שאלת שאלה על שימושים של פוינטרים אז הנה עוד שימוש) בריצה על עץ בינארי זה מאוד יעיל להשתמש ברקורסיה. חוץ מהשימוש הזה אפשר לעשות את כל התרגילים המטופשים שמלמדים במיכללות כמו להפוך מחרוזת ברקורסיה, למצוא מספר גדול ביותר במערך וכו´ (אלה תרגילים שסתם נותנים על מנת להבין איך עובדת הרקורסיה ובלולאה רגילה זה הרבה יותר יעיל) כשקוראים לפונקציה אז בסוף הפונקציה מצביע הפקודה יודע לחזור לנקודה שממנה הוא התחיל איך זה קורה? בגלל שכתובת החזרה נשמרת במחסנית. אותו דבר ברקורסיה: כתובת החזרה נשמרת במחסנית ובסוף הקריאה מצביע הפקודה חוזר לנקודה האחרונה שעליה הצביעה (ושמורה במחסנית) זהו היתרון אך גם החסרון של הרקורסיה כי אם תקראי לרקורסיה בצורה שהיא תקרא לעצמה יותר מדי פעמים אז המחסנית תיגמר ואז יגמר הזיכרון ויתחילו בלאגנים הבנת? דוגמא לקריאה כזאת יכולה להיות כזאת: כתוב תכנית רקורסיבית שמקבלת אינדקס, ומחזירה את מספר הפיבונאצ´י שמתאים לאינדקס. ולתת פה את האיבר ה40 בסידרה בתור אינדקס. כאן הרקורסיה ממש נתקעה לי והייתי חייב לאתחל את המחשב (שהיה פנטיום 133). וכשנתתי לו את האיבר ה30 אז לקח לו 2 דקות עד שהוא החזיר לי תשובה. זהו אני מקווה שהסברתי את עצמי בצורה טובה. אם יש לך עוד שאלות אז תשאלי. יאיר

 

[הבֶיצה השמאלית]

כמה נחמד לזלזל במכללות ../images/Emo46.gif

לידיעתך יאיר יקר יש מכללות שמלמדות ברמה שלא נופלת משום אוניברסיטה והריקורסיות שמקבלים שם במבוא למדעי המחשב (סיסמטר א´ שנה א´) הן הרבה יותר מתוחכמות מריקורסיות שראיתי שהיו במבחנים של הטכניון (תסתכל בעצמך במבחנים שלהם באתר). **************************************************************** להלן שאלה לדוגמה בנושא ריקורסיות מהמכללה בה אני לומד: כיתבו פונציה ריקורסיבית

NODE_PTR* ArrayToListOfLists(int *arr, int size)​

המקבלת מערך של מספרים שלמים Arr ואת גודלו size על הפונקציה ליצור ולהחזיר את הרשימה של רשימות הבאות: * הרשימה הראשונה תכיל את איברי המערך החל מהראשון בקפיצות של 1 - למעשה זו רשימה המכילה את כל איברי המערך. * הרשימה השניה תכיל את איברי המערך החל מהראשון בקפיצות של 2. * הרשימה השלישית תכיל את איברי המערך החל מהראשון בקפיצות של 3. וכן הלאה עד * הרשימה האחרונה תכיל את איברי המערך החל מהראשון בקפיצות של size-1 - למעשה זו רשימה המכילה את האיברים הראשון והאחרון במערך בלבד. הערות: 1. הקצאת זיכרון יש לבצע רק באמצעות הפונקציה newNODE ו/או newNODE_PTR 2. יש להשתמש גם בפונקציה ArrayToList ואין להשתמש בפונקציות נוספות. **************************************************************** אני רוצה לראות אם אתה מר יאיר הנכבד פותר את זה כל כך בקלות (ולהזכירך זה בסך הכל סעיף של 10 נקודות).

 

[yair24]

אין צורך להתעצבן ../images/Emo13.gif

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

יאיר

 

[yair24]

אה ועוד משהו...

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

 

[הבֶיצה השמאלית]

תשובות:

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

 

[yair24]

הנה לך עוד אי צדק...

בוא אני אתן לך עוד דוגמא לאי צדק שיש בין המכללות לטכניון ולאוניברסיטאות: בטכניון אתה לומד הרבה פחות שעות מאשר במכללות וזה תמיד ככה! חברים שלי עושים שם משהו כמו 5 -6 קורסים בסמסטר ויש ךהם משהו כמו 25 שעות שבועיות לי בתור סטודנט במכללה רוב הסמסטרים היו 40 שעות שבועיות(!!!) זה טרוף מוחלט ואני משער שגם לך בתור סטודנט במכללה יש את אותה כמות השעות הזאת. ובכל זאת אחרי סיום הלימודים כששומעים שלמדת בטכניון וכששומעים שלמדת במכללה אז הטכניון עושה הרבה יותר רושם. אין מה לעשות. ובכלל כל המבחנים האלה שנותנים במכללה (למשל במכללה שלי) אתה חושב שמישהו באמת בודק אותם? בוא ניקח דוגמא את השאלה ששאלת: הרי יש יותר מדרך אחת לפתור אותה, נראה לך שמישהו באמת מריץ את התכנית שאתה כותב ובודק אם היא עובדת? לא ולא, כי אם כן אז תקבלו את תוצאות המבחנים בשנה הבאה בירושלים הבנויה מה שעושים שם זה בודקים אם אתה הבנת איך עובדת הרקורסיה ואם נתת רעיון שיכול להיות שיעבוד ואז מחרבשים איזה ציון, ויש מרצים שגם את זה לא עושים,אלא סתם מחרבשים ציונים לפי צבע העיניים של הסטודנט... אין מה לעשות זה המצב. ודרך אגב אני לא יודע אם זה ככה גם בטכניון כי שם יש הרבה מרצים ומתרגלים ויכול להיות ששם כן מתיחסים לבדיקת המבחנים ברצינות. יאיר

 

[gilad_no]

מזל שרשמת שאתה בן 24

אחרת הייתי חושב שאתה בן 8. תגיד לי, מה אתה מתבכיין ? אף אחד לא הכריח אותך ללמוד במכללה! אם מעצבן אותך היחס לתלמידי מכללות, לך לטכניון. אני אישית לומד באוניברסיטה הפתוחה ועושה הכל לבד. לא מגיע לשיעורים ואין לי אפילו "25 שעות שבועיות". אף אחד גם לא מכריח אותך להגיע לשיעורים. אם אתה יכול, תלמד בבית. דרך אגב: גם באוניברסיטה יהיה לך יותר זול

 

[yair24]

אתה צודק אם הם לא מפסיקים

את היחס הזה אני עובר לטכניון!!!

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

 

[gilad_no]

יצאת בזול../images/Emo127.gif

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

 

[yariv~2]

1600 לקורס?

תעבור לצפון זמנית ותקבל 80% הנחה.... (אם תעבור ליש"ע תשלם משהו כמו 5%....)

 

[yair24]

ודבר אחרון...

איפה בדיוק ראית שזלזלתי במכללות? אתה יכול לצטט אותי? יאיר