שלום,

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

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

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

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

המון תודה.

שרון.

נערך 2014 בינואר 311 שנים על-ידי bnw434

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

נערך 2014 בינואר 311 שנים על-ידי שניצל

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

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

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

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

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

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

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

מיון (מערך A)

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

נערך 2014 בינואר 411 שנים על-ידי Zelig

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

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

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

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

נערך 2014 בינואר 511 שנים על-ידי bnw434

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

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

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

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

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

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

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

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

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

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

כן.

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

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

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

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

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

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

http://www.digitalwhisper.co.il/files/Zines/0x01/DW1-6-Recursion.pdf

http://www.digitalwhisper.co.il/files/Zines/0x04/DW4-5-Recursion.pdf

מקווה שזה יעזור לך

הייתה לי את אותה בעיה כמו לך ולא הצלחתי אפילו תרגילים פשוטים.

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

תראה פה יש הרבה תרגילים פשוטים: http://shaytavor.com/Item.aspx?id=ex013

עצה שלי: תתחיל מפה ותפתור את הכל, אח"כ תתקדם לתרגילים מורכבים יותר

אם אתה לא מבין או מצליח משהו אל תוותר ותשאל פה.

בהצלחה

נערך 2014 בינואר 1011 שנים על-ידי falukky