רקורסיה בשפת C

[Noale]

רקורסיה בשפת C

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

int rev (char *s) { int size=0; while (*s) { rev (++s); size++); } return (size); }​

המרצה לא קיבל את הפתרון הזה. מישהו יכול להגיד לי איפה הבעיה? תודה!

 

[yossiea]

אולי בגלל השגיאה?

יש שם סוגר אחד מיותר. חוץ מזה אין לי מושג למה לא. הרצת את הקוד לפני שהגשת אותו?

 

[Noale]

הסוגר זה טעות בהקלדה עכשיו

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

 

[vinney]

זה שאין מחשב לא אומר שאי אפשר להריץ

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

 

[yossiea]

אחרי בדיקה...

חשוב שתביני. אני הרצתי את הקוד ואין כמו מראה עיניים. כמו שרמזו לך כבר. אמנם זה נראה ממבט ראשון כמו רקורסיה (זה הטעה אותי) אבל בפועל מה שקורה שם זה שמספר הקריאות גדול הרבה יותר מהדרוש ליתר דיוק אם למשל המחרוזת היא באורך 10 תווים את מבצעת בסך הכל 55 קריאות! וכדי להבין למה תתחילי מה-while שם טמונה הבעיה. פשוט אסור לך להכניס את הקריאה הרקורסיבית לתוך ה-while, משום שהקריאה הרקורסיבית תתבצע שוב ושוב כל עוד המחרוזת אינה NULL וזה לא מה שאת רוצה. הרקורסיה היא "במקום" הלולאה! לא בנוסף. את לא צריכה while כדי לצאת מהרקורסיה מספיק if אחד קטן. תנסי להבין את הקוד הזה למשל (משהו שהכנתי על רגל אחת) שמבוסס על מה שכתבת רק בלי ה-while:

int rev(char *s) { if(!*++s) return 1; else return rev(s)+1; }​

 

[vinney]

הערה קטנה, יוסי

אף פעם, אבל אף פעם, אל תניח שום דבר על הקלט. קלט שלך יכול להיות NULL, יכול להיות שורה ריקה, ובשני המקרים הפונקציה שלך תיפול. הכי טוב - לך על הפשט. במקרה שלנו:

int rev(char *s) { if (s == NULL) return 0; if (*s == '\0') return 0; return rev(++s)+1; }​

 

[yossiea]

מקבל...

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