פונקציה רקורסיבית היא פונקציה שניתן לחשב את ערכה בכל נקודה מתוך ערכי הפונקציה בכמה נקודות קודמות. לדוגמה, נניח שפונקציה f(k) = f(k-2) + f(k-3) המוגדרת על פני מספר שלם לא שלילי. אם יש לנו את הערך של הפונקציה ב-k = 0 ו-k = 2, נוכל למצוא את הערך שלה גם בכל מספר שלם לא שלילי אחר. במילים אחרות, אנו יכולים לומר שפונקציה רקורסיבית מתייחסת לפונקציה שמשתמשת בנקודות קודמות משלה כדי לקבוע מונחים עוקבים ובכך יוצרת רצף מונחים. במאמר זה נלמד על פונקציות רקורסיביות יחד עם דוגמאות מסוימות.
מהי רקורסיה?
רקורסיה מתייחסת לתהליך שבו תהליך רקורסיבי חוזר על עצמו. רקורסיבית היא מעין פונקציה של משתנה אחד ויותר, המצוינת בדרך כלל על ידי תהליך מסוים שמייצר ערכים של אותה פונקציה על ידי יישום מתמשך של יחס מסוים לערכים ידועים של הפונקציה.
כאן נבין את הרקורסיה בעזרת דוגמה.
נניח שאתה הולך לעלות במדרגות כדי להגיע לקומה הראשונה מקומת הקרקע. אז, כדי לעשות זאת, אתה צריך לעשות צעד אחד אחד. יש רק דרך ללכת לצעד השני שהוא לצעד הראשון התלול. נניח שאתה רוצה לעבור לשלב השלישי; אתה צריך לעשות קודם את הצעד השני. כאן, אתה יכול לראות בבירור את תהליך החזרה. כאן, אתה יכול לראות שבכל שלב הבא, אתה מוסיף את השלב הקודם כמו רצף חוזר עם אותו הבדל בין כל שלב. זהו הרעיון האמיתי מאחורי הפונקציה הרקורסיבית.
שלב 2: שלב 1 + השלב הנמוך ביותר.
שלב 3: שלב 2 + שלב 1 + השלב הנמוך ביותר.
שלב 4: שלב 3 + שלב 2 + שלב 1+ השלב הנמוך ביותר, וכן הלאה.
קבוצה של מספרים טבעיים היא הדוגמה הבסיסית לפונקציות רקורסיביות שמתחילות מאחד עובר עד אינסוף, 1,2,3,4,5,6,7,8, 9,…….אינסופי. לכן, קבוצת המספרים הטבעיים מציגה פונקציה רקורסיבית מכיוון שניתן לראות הבדל משותף בין כל איבר כ-1; זה מראה בכל פעם שהמונח הבא חוזר על עצמו במונח הקודם.
מהי פונקציה מוגדרת רקורסיבית?
הפונקציות המוגדרות באופן רקורסיבי מורכבות משני חלקים. החלק הראשון עוסק בהגדרת הטיעון הקטן ביותר, ומצד שני, החלק השני עוסק בהגדרת המונח ה-n. הארגומנט הקטן ביותר מסומן ב-f (0) או f (1), ואילו הארגומנט ה-n מסומן ב-f (n).
עקוב אחר הדוגמה הנתונה.
נניח שרצף הוא 4,6,8,10
הנוסחה המפורשת לרצף לעיל היא f (n)= 2n + 2
הנוסחה המפורשת עבור הרצף לעיל ניתנת על ידי
f (0) = 2
f(n) = f (n-1) + 2
כעת, אנו יכולים לקבל את מונחי הרצף תוך שימוש בנוסחה הרקורסיבית כדלקמן f(2) f (1) + 2
f(2) = 6
f (0) = 2
f(1) = f(0) + 2
f (1) = 2 + 2 = 4
f(2) = f (1) + 2
f(2) = 4 + 2 = 6
f(3) = f (2) + 2
f(3) = 6 + 2 = 8
בעזרת נוסחת הפונקציה הרקורסיבית לעיל, נוכל לקבוע את האיבר הבא.
מה הופך את הפונקציה רקורסיבית?
הפיכת כל פונקציה רקורסיבית צריכה מונח משלה כדי לחשב את האיבר הבא ברצף. לדוגמה, אם אתה רוצה לחשב את האיבר ה-n של הרצף הנתון, תחילה עליך לדעת את האיבר הקודם ואת האיבר שלפני האיבר הקודם. לפיכך, עליך להכיר את המונח הקודם כדי למצוא אם הרצף רקורסיבי או לא רקורסיבי. אז אנחנו יכולים להסיק שאם הפונקציה צריכה את האיבר הקודם כדי לקבוע את האיבר הבא ברצף, הפונקציה נחשבת לפונקציה רקורסיבית.
הנוסחה של הפונקציה הרקורסיבית
אם1, א2, א3, א4, א5, א6, ……..אנ,……היא קבוצות רבות או רצף, אז נוסחה רקורסיבית תצטרך לחשב את כל המונחים שהיו קיימים קודם לכן כדי לחשב את הערך של
אנ= אn-1 +א1
ניתן להגדיר את הנוסחה לעיל גם כנוסחה רקורסיבית של רצף אריתמטי. אתה יכול לראות בבירור ברצף שהוזכר לעיל שזהו רצף אריתמטי, הכולל את האיבר הראשון ואחריו את המונחים האחרים והבדל משותף בין כל איבר. ההבדל המשותף מתייחס למספר שאתה מוסיף או מחסיר לו.
ניתן להגדיר פונקציה רקורסיבית גם כרצף הגיאומטרי, כאשר לקבוצות המספרים או לרצף יש גורם משותף או יחס משותף ביניהם. הנוסחה לרצף הגיאומטרי ניתנת כ
אנ= אn-1 *ר
בדרך כלל, הפונקציה הרקורסיבית מוגדרת בשני חלקים. הראשון הוא ההצהרה של האיבר הראשון יחד עם הנוסחה, ואחר הוא ההצהרה של האיבר הראשון יחד עם הכלל הקשור למונחים העוקבים.
כיצד לכתוב נוסחה רקורסיבית לרצף אריתמטי
כדי לכתוב את הנוסחה הרקורסיבית עבור נוסחת הרצף האריתמטי, בצע את השלבים הנתונים
שלב 1:
בשלב הראשון, עליך לוודא אם הרצף הנתון הוא אריתמטי או לא (בשביל זה, עליך להוסיף או להחסיר שני איברים עוקבים). אם אתה מקבל את אותו פלט, אז הרצף נלקח כרצף אריתמטי.
שלב 2:
כעת, עליך למצוא את ההבדל המשותף לרצף הנתון.
שלב 3:
טקסט גלישת css
נסח את הנוסחה הרקורסיבית באמצעות המונח הראשון ולאחר מכן צור את הנוסחה באמצעות המונח הקודם וההבדל המשותף; כך תקבל את התוצאה הנתונה
אנ= אn-1 +ד
כעת, אנו מבינים את הנוסחה הנתונה בעזרת דוגמה
נניח ש-3,5,7,9,11 הוא רצף נתון
בדוגמה שלמעלה, אתה יכול בקלות למצוא שזה הרצף האריתמטי מכיוון שכל איבר ברצף גדל ב-2. לכן, ההבדל המשותף בין שני איברים הוא 2. אנו מכירים את הנוסחה של רצף רקורסיבי
אנ= אn-1 +ד
נָתוּן,
d = 2
א1= 3
כך,
א2= א(2-1)+ 2 = א1+2 = 3+2 = 5
א3= א(3-1)+ 2 = א2+2 = 5+2 = 7
א4= א(4-1)+ 2 = א3+2 = 7+2 = 9
א5= א(5-1)+ 2 = a + 2 = 9+2 = 11, והתהליך ממשיך.
איך לכתוב נוסחה רקורסיבית לרצף גיאומטרי?
כדי לכתוב את הנוסחה הרקורסיבית עבור נוסחת הרצף הגיאומטרי, בצע את השלבים המפורטים:
שלב 1
בשלב הראשון, עליך לוודא אם הרצף הנתון הוא גיאומטרי או לא (בשביל זה, עליך להכפיל או לחלק כל איבר במספר). אם אתה מקבל את אותו פלט מאיבר אחד לאיבר הבא, הרצף נלקח כרצף גיאומטרי.
שלב 2
כעת, עליך למצוא את היחס המשותף לרצף הנתון.
שלב 3
נסח את הנוסחה הרקורסיבית באמצעות המונח הראשון ולאחר מכן צור את הנוסחה באמצעות המונח הקודם והיחס המשותף; כך תקבל את התוצאה הנתונה
אנ= ר*אn-1
כעת, אנו מבינים את הנוסחה הנתונה בעזרת דוגמה
נניח ש-2,8,32, 128,.הוא רצף נתון
בדוגמה שלמעלה, אתה יכול בקלות למצוא שזה הרצף הגיאומטרי מכיוון שהאיבר העוקב ברצף מתקבל על ידי הכפלה של 4 לאיבר הקודם. אז, היחס המשותף בין שני איברים הוא 4. אנו מכירים את הנוסחה של רצף רקורסיבי
אנ= ר*אn-1
אנ= 4
אn-1= ?
נָתוּן,
r = 4
א1= 2
כך,
א2= א(2-1)* 4 = א1+ * 4 = 2* 4 = 8
א3= א(3-1)* 4 = א2* 4 = 8 * 4 = 32
א4= א(4-1)* 4 = א3* 4 = 32* 4 = 128, והתהליך ממשיך.
דוגמה לפונקציה רקורסיבית
דוגמה 1:
קבע את הנוסחה הרקורסיבית עבור הרצף 4,8,16,32,64, 128,...?
פִּתָרוֹן:
נתון רצף 4,8,16,32,64,128,…..
הרצף הנתון הוא גיאומטרי מכיוון שאם נכפיל את האיבר הקודם, נקבל את האיברים העוקבים.
כדי לקבוע את הנוסחה הרקורסיבית עבור הרצף הנתון, עלינו לכתוב אותה בצורה טבלאית
| מספרי מונחים | מונח רצף | סימון פונקציות | סימון מנוי |
|---|---|---|---|
| 1 | 4 | f(1) | א1 |
| 2 | 8 | f(2) | א2 |
| 3 | 16 | f(3) | א3 |
| 4 | 32 | f(4) | א4 |
| 5 | 64 | f(5) | א5 |
| 6 | 128 | f(6) | א6 |
| נ | . | f(n) | אנ |
לפיכך, הנוסחה הרקורסיבית במושג פונקציה ניתנת על ידי
f(1) = 4, f(n) . f(n- 1)
בסימון מנוי, הנוסחה הרקורסיבית ניתנת על ידי
א1= 4, אנ= 2. אn-1