C++/פונקציות: הבדלים בין גרסאות בדף
תוכן שנמחק תוכן שנוסף
Ybungalobill (שיחה | תרומות) |
Ybungalobill (שיחה | תרומות) |
||
שורה 262:
פונקציה זו מקבת כפרמטר את אינדקס האיבר בסדרה, מחשבת ומחזירה את ערך האיבר עצמו. כמו בכל פונקציות רקורסיביות במחשב צריך להיות תנאי עצירה לרקורסיה, על מנת שהיא לא תהיה אינסופית. תנאי עצירה זה (המקרה הפשוט) הוא כאשר מספר האיבר בסדרה הוא 0 או 1. במקרה זה אנו יודעים את התשובה ומחזירים את הערך של האיבר בלי לחשבו. במקרה ואינדקס גדול מ-1 אנחנו מחשבים אותו על בסיס האיברים הקודמים לו: אנחנו מחברים את האיבר הקודם Fibonacci(n-1)‎ ואת האיבר לפני הקודם Fibonacci(n-2)‎. הנחנו את תקינות הפרמטר n ולא בדקנו את המקרה בו הוא שלילי.
פונקציה זו היא רקורסיבית מפני שהיא קוראת לעצמה: בכל קריאה שעבורה n גדול מ-1 היא קוראת לעצמה פעמים. עבור כל קריאה לפונקציה כזאת נוצרים עותקים של כל המשתנים המקומיים (כולל הפרמטרים), והם מושמדים כאשר הפונקציה אליה הם שייכים תסתיים. מכיוון ש-Fibonacci קורא לעצמו לפני שהוא מסתיים, נוצר עוד עותק של הפרמטר n ושל כתובת החזרה מהפונקציה. כנאמר, המשתנים המקומיים, הפרמטרים וכתובת החזרה נמצאים על המחסנית. כיוון שהמחסנית היא אזור מוגבל בזיכרון, היא עלולה להתמלא. במקרה זה התוכנית תקרוס בזמן ריצה עקב גלישה מהמחסנית (Stack Overflow). במחשבים של היום, גודל המחסנית מספיק עבור רוב צרכי התוכנות, גם עבור פונקציות רקורסיביות. גלישה מהמחסנית תקרה כאשר יש שגיאה בתנאי העצירה של הרקורסיה והיא תהיה לאינסופית, או כאשר האלגוריתם שכתבנו באמת משתמש בעומק רקורסיה גדול מדיי.
נמחיש את אופן הקריאות הרקורסיביות באמצעות עץ:
[[תמונה:fibonacci_call_tree_5.svg|center]]
כל צומת בעץ זה מייצג זימון אחד של הפונקציה Fibonacci. החצים מייצגים את הזימונים עצמם, לדוגמה: Fibonacci(5)‎ קורא ל-Fibonacci(4)‎ ואחרי ש-Fibonacci(4)‎ מסתיים Fibonacci(5)‎ יקרא ל-Fibonacci(3)‎. אף זימון של פונקציה לא יסתיים כל עוד מתבצע אחד הזימונים המקוננים (הרקורסיביים). הם המיוצגים על ידי הצאצאים של אותו הצומת. לדוגמה, כאשר התוכנית יורדת לעומק הרקורסיה המקסימלי (לתחתית העץ משמאל) קיימים על המחסנית 5 עותקים של כל המשתנים המקומיים. Fibonacci(5)‎ לא יסתיים כל עוד כל תת-העצים מימין ומשמאל לא יסיימו להתבצע.
מניתוח מתמטי של הפונקציה הזו ניתן לקבל שזמן ריצתה שווה ל-<math>\Theta\left(\phi^{n}\right)</math> (זהו מספר הצמתים בעץ שלמעלה). עומק הרקורסיה המרבי, הוא גובה העץ, ומשיקול פשוט ברור שערך זה הוא <math>\Theta\left(n\right)</math>. שני המאפיינים הללו מראים על אי-יעילות האלגוריתם הרקורסיבי לחישוב מספרי פיבונאצ'י. אלגוריתם איטרטיבי (עם לולאה) יתבצע תוך <math>\Theta\left(n\right)</math> ויקח <math>O\left(1\right)</math> מנפח הזיכרון. שימוש בנוסחה למספרי פיבונאצ'י תחושב תוך <math>\Theta\left(\log n\right)</math>. מצד שני, נניח שבידינו מחשב 32 סיביות ועבור המחסנית מוקצה קטע זיכרון בגודל של מגה-בית אחד. במקרה זה הפרמטר n וכתובת החזרה יתפסו ביחד 8 ביתים, ולכן עומק הרקורסיה המקסימלי האפשרי יהיה בקירוב 131000. אבל, גודל מספר הפיבונאצי הזה הוא כ-<math>2^{91000}</math> מה שהרבה מעבר לגודל המשתנה של 32 סיביות, כתוצאה כל שאר הסיביות חוץ מ-32 הראשונות יעלמו. מספר פיבונאצי הגדול ביותר שיחושב בהצלחה, גם עבור אלגוריתם איטרטיבי, יהיה Fibonacci(47)‎.
אך לרקורסיה, מלבד הקלות בפתרון בעיות שונות, ניתן לעיתים גם ליעל את התוכנית. אלגוריתמים רבים המסתמכים על עקרון [[w:אלגוריתם הפרד ומשול|הפרד ומשול]] נכתבים לרוב באמצעות פונקציה רקורסיבית (לדוגמה מיון מהיר, עצי BSP ועוד').
== פרמטרים שרירותיים ==
| |||