רקורסיה

[Me¥tal]

רקורסיה

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

 

[jolp1]

למיטב ידיעתי- כל בעיה מתמטית הניתנת

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

 

[gilad_no]

הכי פשוט, עצרת.

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

 

[odstudio]

רקורסיה או לא?

לכל תוכנית הרצה במע´ ההפעלה, מוגדר איזור זיכרון הנקרא "זכרון מחסנית". ההקצאה ב"זכרון המחסנית" נעשית בסדר LIFO, כלומר - נכנס אחרון, יוצא ראשון - (Last In, First Out). בקריאה לפונקציה מסויימת, מוקצים הפרמטרים המועברים לה ב"זיכרון המחסנית" וכן כל אותם משתנים המוקצים בגוף הפונקציה. בחזרה מן הפונקציה, כל אלה מנוקים מ"זכרון המחסנית". יש לשים לב, כי ל"זכרון המחסנית" יש גודל מסויים, אשר חריגה ממנו תגרום לשגיאת חריגה - Stack Overflow. "רקורסיה" היא קריאה עצמית לפונקציה, המנצלת את פעולת "זכרון המחסנית", על-פי ההסבר שנתתי קודם, לביצוע פעולות הדורשות - מחסנית. ולכן, כל בעייה ניתנת לפתרון גם ללא רקורסיה, ע"י לולאה המשתמשת ב"מחסנית", לאו דווקא "זכרון המחסנית" של התוכנית עצמה. העניין הוא שיש צורך לממש מחסנית זו ע"י המתכנת, ואז להשתמש בה בגוף הלולאה.

 

[odstudio]

אגב...

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

 

[Vodjanoj]

אגב, Calling Convention

זה לא רק קביעת סדר הפרמטרים, המועברים לפונקציה הנקראת. זה גם: 1. קביעת צורה, בה יוחזר ערך הפונקציה הנקראת. 2. קביעת האחריות לניקוי המחסנית, דהיינו מי מסלק את הפרמטרים מהמחסנית בתום ביצוע הפונקציה (הפונקציה הקוראת או הפונקציה הנקראת).

 

[ChipsMan]

נ.ב.

לא תמיד הפרמטרים מועברים במחסנית. יש כמה Calling Conventions כמו fastcall ב-C, ו-register ב-Delphi שבהן פרמטרים מועברים באוגרים (או לפחות חלקם, במקרה ויש הרבה פרמטרים).

 

[Me¥tal]

אפילו למגדלי האנוי

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

 

[malolds]

בעיות מת´

אני מאמין שחוץ מ-´מגדלי האנוי´ יש גם את שני הגדות(עם החסה, הזאב והכבש) וגם את 5 המשבצות.

 

[Me¥tal]

מה זה 5 המשבצות?

 

[malolds]

5 המשבצות

היא בעיה ש... אני יצייר אותה ------------- |-|-| |

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

 

[malolds]

אופס!!!

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

 

[Me¥tal]

לקח לי קצת זמן קודם, אבל הבנתי.

תודה רבה!

 

[Me¥tal]

איך פותרים את שתי הגדות

עם רקורסיה? איך אפשר לכתוב את זה כתהליך רקורסיבי?

 

[erezsh]

חיפוש

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

 

[ihovav]

טעות !!!

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

 

[erezsh]

מה הקשר??

ואם אני כותב לולאה שכל פעם עושה Allocate לכמות מסוימת של זיכרון? זה לא רקורסיה, אבל זה מוגבל בזיכרון. עכשיו תסביר לי מה ההבדל בין לכתוב לזיכרון כמה דברים (PUSH), ולשנות איזה משתנה (SP) , ואז לקפוץ מחדש לתחילת הקוד, לבין לולאה? אז נכון שרקורסיה מחייבת אותך להיות מוגבל בזיכרון.. אבל זה לא אומר שהיא לא סתם לולאה עם קוד נלווה..

 

[ihovav]

הכוונה היא

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

 

[ליאור ב]

יש לי יש לי יש לי...

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

mat[0][0];​

או לערך היחידי במטריצה. (רמז: זה תנאי העצירה ותחילת החזרה החוצה) בהצלחה. למי שמעוניין יש לי את הפתרון ב-JAVA. ליאור ב.