רקורסיה - איך זה עובד?

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

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

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

אחרי שבדקתי וקראתי הבנתי שהאנשים דיברו רקורסיבית טהורה.

השאלה שלי,
איך רקורסיה עובדת בפייתון?
למה כשמגדירים X = פונקציה[1-:] הפונקציה מתחילה לפרק את הרשימה עד לנקודת הביקורת.
מה קורה ברגע שהיא מגיע לreturn, ציפיתי שהפונקציה תחזיר את הערך למקום שבו קראנו לה לראשונה.

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

עם זאת, תשובה מפורטת תעשה יותר סדר.

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

הרקורסיה מורכבת משני חלקים:

1. תנאי (ביחיד או ברבים) עצירה שהפונקציה תמיד תגיע אליו - אחרת בחלק מהמקרים תהיה רקורסיה אינסופית ולעולם לא תקבל תשובה כי רק תמשיך לנסות לפתור תתי בעיות יותר ויותר קטנות עד אין קץ. למעשה, לא תהיה רקורסיה אינסופית כי פייתון מונעת את זה, אבל בכל מקרה זה לא יפתור לך את הבעיה. תנאי העצירה הוא לרוב מקרה בסיס שקל לפתור (ולרוב שלא ניתן לפתור אותו על סמך נוסחת הרקורסיה כי אין בעיות קטנות יותר) - למשל אם הרשימה ריקה אין לה מקסימום ואם יש בה איבר יחיד הוא כמובן המקסימום. אם אתה מחפש את האיבר הראשון או את האיבר השני בסדרת פיבונאצ’י הרי שהם 1.
2. פירוק הבעיה לתתי בעיות קטנות יותר וחישוב על סמך התשובה שהן מחזירות מה התשובה שלך. חשוב לשים לב שאתה באמת מקטין בכל פעם את הבעיה ובסוף מגיע לתנאי העצירה. למשל, אם תשכח חלילה להוריד איברים מהרשימה, תיכנס לרקורסיה אינסופית (עד שפייתון יזרוק לך שגיאה). צריך לדעת איך להקטין את הבעיה ואיך לפתור על סמך פתרון הבעיה הזו. למשל, עבור סדרת פיבונאצ’י שמוגדרת באופן רקורסיבי קל להבין שפירוק הבעיה יהיה להחזיר את סכום האיבר ה-i-1 והאיבר ה-i-2 - זו ממש הגדרת האיבר ה-i (ולכן זה תרגיל קלאסי להיכרות עם רקורסיה, על-אף שלפתור אותו עם לולאה זה יעיל בהרבה).
   גם ברשימה כנראה יהיה קל להבחין שאם תגלה את המקסימום של כל האיברים פרט לאחד תוכל מיידית להחזיר את המקסימום. אז אתה מוריד איבר אחד. ובפונקציה הבאה הרשימה כבר כוללת איבר אחד פחות וגם היא מורידה עוד איבר. וככה הלאה עד שאתה מגיע לזה שהפונקציה מקבלת רשימה בגודל 1 ומחזירה את האיבר היחיד - ושולחת את זה לפונקציה שקראה לה ובה היו 2 איברים ברשימה - שתחזיר את המקסימום בין שני האיברים האלה בקלות - תוך השוואה אחת. התשובה שתחזור לפונקציה שקראה לה ובה היו 3 איברים תאפשר תוך השוואה אחת להחזיר את התשובה לפונקציה שקראה לה עם רשימה ובה 4 איברים - וכך הלאה. למעשה, כל פונקציה תמתין בסבלנות לתשובה של הפונקציה שלה היא קראה עם בעיה קטנה יותר, עד שיתחילו לזרום תשובות והפונקציות יתחילו להתקפל הביתה.

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

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

נ"ב - ממליצה לכתוב רקורסיה בגוגל, יש שם התחכמות יפה

לי יש שני דברים בראש שעוזרים לי לחשוב על תרגילים שאני רוצה לפתור ברקורסיה:

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

2. הדבר שאני שאני עושה הוא לחשוב על הכל במאין תור ארוך של שורות קוד שאני צריך לבדוק. אבל במקום לבדוק את הראשון וואז את השני אני סוג של מנסה להגיע לסוף (שהוא המקרה הקטן ביותר) ואז לאסוף אותם אחד אחד מהסוף חזרה להתחלה. עבור כל שורה שאני חוזר אחורה אני מקבל את התוצאה שלה (אותה אני יכול לצבור, סתם להחזיק אותה למשל כמו תשובה של True \ Flase וכו.

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

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

תודה!
בטח אשמח שנעבור על משהו ביחד