C++/פונקציות: הבדלים בין גרסאות בדף
תוכן שנמחק תוכן שנוסף
Ybungalobill (שיחה | תרומות) מ ←רקורסיה: תמונה |
Ybungalobill (שיחה | תרומות) |
||
שורה 268:
[[תמונה:fibonacci_call_tree_5.gif|center]]
כל צומת בעץ זה מייצג זימון אחד של הפונקציה Fibonacci
מניתוח מתמטי של הפונקציה הזו ניתן לקבל שזמן ריצתה שווה ל-<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)‎.
במקרים פשוטים ניתן מלכתחילה להמנע מרקורסיה. מדובר במקרים בהם הפונקציה הרקורסיבית מזמנת את עצמה לכל היותר פעם אחת:
<source lang="cpp">
void f(/* params */)
{
if(/* termination condition */)
/* termination code */
else
{
/* pre-call code */
f(/* params */);
/* post-call code */
}
}
</source>
במקום פונקציות רקורסיביות מהסוג הזה ניתן להסתפק בשתי לולאות:
<source lang="cpp">
void f(/* params */)
{
int n = 0;
for( ; !/* termination condition */; n++)
/* pre-call code */
/* termination code */
for(int i = 0; i < n; i++)
/* post-call code */
}
</source>
כאשר אחרי הקריאה לפונקציה הרקורסיבית לא מתבצעות פעולות נוספות, כלומר אין קטע קוד "post-call code", הלולאה השנייה בפתרון האיטרטיבי מתבררת כמיותרת ולכן גם אין צורך במונה "עומק הרקורסיה" n. שימו לב שהפונקציה Fibonacci קוראת לעצמה לכל היותר פעמיים, לכן הפתרון האיטרטיבי שלה הוא לא מהתבנית הזו (ראה תרגילים).
== פרמטרים שרירותיים ==
| |||