C++/פונקציות: הבדלים בין גרסאות בדף
תוכן שנמחק תוכן שנוסף
Ybungalobill (שיחה | תרומות) |
Ybungalobill (שיחה | תרומות) מ ←רקורסיה: תמונה |
||
שורה 266:
נמחיש את אופן הקריאות הרקורסיביות באמצעות עץ:
[[תמונה:fibonacci_call_tree_5.
כל צומת בעץ זה מייצג זימון אחד של הפונקציה Fibonacci(5)‎. החצים מייצגים את הזימונים עצמם, לדוגמה: 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)‎.
| |||