|
ב[[מתמטיקה]], '''נוסחת נסיגה''' היא נוסחה שמגדירה סדרת איברים, כך שכל איבר בסדרה מוגדרבאופן [[רקורסיה|רקורסיביתרקורסיבי]]. בעזרתלמשל, האיברים[[סדרת הקודמיםפיבונאצ'י]] בה,מוגדרת פרטעל-ידי למספרנוסחת סופיהנסיגה של<math>\ איבריםF_{n+1} ראשונים= F_n+F_{n-1}</math>, שמהוויםיחד אתעם '''תנאי ההתחלה''' <math>\ F_0 = F_1 = 1</math>.
==הגדרה רקורסיבית של סדרה==
הדוגמה הקלאסית לנוסחת נסיגה היא זו של [[סדרת פיבונאצ'י]], שמוגדרת כך: האיבר הראשון שלה הוא 0, השני 1, וכל איבר החל מהשלישי הוא סכום של שני האיברים שקדמו לו.
בהגדרה רקורסיבית יש שני חלקים:
# תנאי התחלה הקובעים את האברים הראשונים בסדרה,
# נוסחת הנסיגה, המגדירה כל איבר בסדרה [[הגדרה רקורסיבית|באופן רקורסיבי]] לפי האברים הקודמים לו.
==מעבר מנוסחת נסיגה להצגה מפורשת ==
אנו מקבלים את הסדרה ....,0,1,1,2,3,5,8.
נוסחת נסיגה מתארת את הקשר בין האברים בסדרה, אבל אינה נותנת תאור ישיר שלהם. כדי לחשב את האיבר ה-n בסדרה (ואפילו כדי להעריך את סדר הגודל שלו), יש לחשב את כל האברים הקודמים. '''פתרון''' של נוסחת הנסיגה הוא מעבר מנוסחה כזו לנוסחה מפורשת ("'''נוסחה ישירה'''" או "'''נוסחה סגורה'''"). ישנן מספר שיטות לעשות כן:
==מבנה נוסחאות נסיגה==
נוסחת נסיגה סטנדרטית מורכבת משני חלקים:
# תנאי התחלה (לפחות אחד)
# רשימת שוויונים ה[[הגדרה רקורסיבית|מוגדרים באופן רקורסיבי]] המכונים "'''כללי נסיגה'''" (לפחות אחד), כך שמ[[איטרציה|הפעלה חוזרת]] '''סופית '''שלהם ניתן להגיע לתנאי ההתחלה
תנאי ההתחלה הם ערכים קבועים וידועים, ומשמשים כ[[תנאי עצירה]] להליך הרקורסיבי של הפעלת כללי הנסיגה.
==פתרון נוסחאות נסיגה==
חישוב איבר על ידי נוסחת נסיגה הוא בעייתי, כי ככל שהאיבר מתקדם יותר בסדרה, כך יש לחשב יותר איברים כדי להגיע אליו. למשל, כדי לחשב את האיבר המיליון ואחד בסדרת פיבונאצ'י, יש לחשב קודם כל את כל מיליון האיברים שלפניו. על כן, מנסים לפתור נוסחאות נסיגה על-מנת למצוא נוסחה שאינה רקורסיבית לאברי הסדרה ("'''נוסחה ישירה'''" או "'''נוסחה סגורה'''"). ישנן מספר שיטות לעשות כן:
===הצבה חוזרת===
| 