עזרה - דרכי לימוד חשיבה רקורסיבית

bnw434 · 2014 בינואר 3

שלום,

אני די איטי, ויכול להיות שמשהו בי דפוק, אבל for the love of god מדוע כ"כ קשה לי להבין את הקונספט הזה.

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

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

לשאלתי - התוכלו בבקשה להפנות אותי לחומר מקיף וממצה בתחום, כולל תרגול פתור, בבקשה ?

המון תודה.

שרון.

שניצל · 2014 בינואר 3

תערוך בבקשה את הכותרת למשהו נורמלי, כך שתכיל את תמצית הבקשה שלך.

Zelig · 2014 בינואר 4

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

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

תחשוב על זה ככה: איך ממינים מערך בגודל N? אני לא יודע (ברור שאני יודע...) אבל:

1) נמצא דרך להקטין את הבעיה (אני אחלק את המערך לשני חלקים A ו-B, שבהכרח קטנים יותר.)

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

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

והנה האלגוריתם הרקורסיבי: סוג של merge sort

מיון (מערך A)

אם אורך A הוא 1 או פחות: צא והחזר את A כמו שהוא
אם אורך A הוא 2:
2. אם A0 גדול מ-A1: החלף בין A0 ל-A1
3. צא החזר את A
4. X = מיון(חצי ראשון של A)
5. Y = מיון(חצי שני של A)
6. מזג את X ו-Y לתוך A
7. החזר את A
  
  (אגב החתימה שלי היא מימוש רקורסיבי של quick sort ב-haskell, שפה פונציונלית אשר אוהבת רקורסיות. אתה יכול לראות שהפוקנציה qsort קוראת לעצמה פעמיים.)

bnw434 · 2014 בינואר 5

לממש אני יודע לממש. הבעיות הן כדלהלן -

1) אני מאוד מתבלבל כאשר יש שתי רקורסיות בשיטה.- לדוגמא מבוך או מגדלי הנוי. אני פשוט מסתבך נורא ולא מסוגל לעקוב אחרי הסטאק..

2) להגיע לדרך בה התוכנית צריכה לעבוד.

האם ישנם חומרים בנושא (כולל שאלות ופתרונות ) ??

Gil28 · 2014 בינואר 5

השיטה הכי מסודרת ובטוחה היא לקחת דוגמה קטנה - למשל עבור N=4 ולצייר לך טבלת מעקב:

1. אחרי השלב ברקורסיה

2. אחרי המשתנים שלך

3. לבדוק אם תנאי העצירה מתקיים.

הוכחות באינדוקציה אתה מכיר?

bnw434 · 2014 בינואר 6

השיטה הכי מסודרת ובטוחה היא לקחת דוגמה קטנה - למשל עבור N=4 ולצייר לך טבלת מעקב:
1. אחרי השלב ברקורסיה
2. אחרי המשתנים שלך
3. לבדוק אם תנאי העצירה מתקיים.
הוכחות באינדוקציה אתה מכיר?

כן.

Zelig · 2014 בינואר 6

בעיה עם מבנה רקורסיבי היא בעיה שמוגדרת / נפתרת על ידי שילוב גרסאות פשוטות של אותה בעיה.

דוגמא: ביטוי אריתמטי מורכב מתתי-ביטויים אשר משולבים ע"י פעולה כגון כפל, חיבור, חיסור וכו'.

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

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

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