רקורסיה בפתרון בעיות לחזרה

מהי רקורסיה?

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

תן דוגמה לפונקציה רקורסיבית.

פונקציית חישוב פיבונאצ'י: $$F(n) = F(n-1) + F(n-2)$$

נכון או לא? כל פונקציה רקורסיבית חייבת להיות עם מקרה בסיס.

נכון. מקרה בסיס מונע רקורסיה אינסופית.

מהו מקרה בסיס?

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

השלם: רקורסיה עוזרת בפתרון בעיות ______.

מורכבות עם מבנים חוזרים.

השווה בין רקורסיה לאיטרציה.

- רקורסיה: קוראת לעצמה. - איטרציה: משתמשת בלולאה.

מהו עומק רקורסיה?

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

נכון או לא? ברקורסיה ניתן להחיל כל פונקציה.

לא. רק פונקציות עם מבנה חוזר מתאימות.

מהי בעיית השבר?

בעיה שבה פונקציה קוראת לעצמה עם ערכים קטנים יותר, לדוגמה חישוב $\displaystyle n!$.

דוגמה למקרה בסיס בחישוב $\displaystyle n!$.

$$1! = 1$$

מהן יתרונות הרקורסיה?

- פשטות הקוד. - נוחות בפתרון בעיות מסוימות.

מהי בעיית התור?

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

מהי רקורסיה?

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

שאלת דוגמה לרקורסיה.

חישוב פיבונאצ'י: $\displaystyle F(n) = F(n-1) + F(n-2)$.

מתי כדאי להשתמש ברקורסיה?

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

אילו בעיות נפתרות ברקורסיה?

- חיפוש בינארי - חיפוש בעץ - חישוב פיבונאצ'י - חישוב פאקטוריאל

האם כל בעיה ניתנת לפתרון ברקורסיה?

לא, יש בעיות שמומלץ לפתור בשיטות אחרות כמו לולאות.

מה ההבדל בין רקורסיה פשוטה למורכבת?

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

מהו פאקטוריאל?

פאקטוריאל של מספר $\displaystyle n$ מוגדר כ-$\displaystyle n! = n imes (n-1)!$ עם $\displaystyle 0! = 1$.

שאלה: חישוב $\displaystyle 5!$?

חישוב: $\displaystyle 5! = 5 imes 4! = 5 imes 24 = 120$.

מהי בעיית Towers of Hanoi?

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

האם רקורסיה תמיד יעילה?

לא, שימוש לא נכון יכול לגרום לצריכת זיכרון גבוהה ואיטיות.

מתי יש להשתמש ברקורסיה?

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

מה קורה כשנגיע למקרה בסיסי?

יש לעצור את הרקורסיה ולחזור עם התוצאה שנצברה.

שאלה: מהו המקרה הבסיסי?

המצב שבו ניתן לפתור את הבעיה ללא קריאה נוספת לפונקציה עצמה.

מהי דוגמה לעץ?

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

מה מבדל בין אלגוריתם רקורסיבי לאיטרטיבי?

רקורסיבי: פונקציה קוראת לעצמה. איטרטיבי: משתמש בלולאות.

מה החשיבות של זמן ריצה ברקורסיה?

חשוב להבין את מורכבות הזמן כדי למנוע ביצועים לא יעילים בשימוש במשאבים.