C++/פונקציות

פונקציות הן אבני הבניין של תכנות פרוצדורלי. כל פונקציה היא חלק מהתוכנה שיכול לקבל פרמטרים ויכול להחזיר ערך. לכל פונקציה כזאת נוכל לקרוא בכל מיני מקומות שונים בתוכנית. בזמן הקריאה לפונקציה, התוכנית עוצרת במקום הקריאה ועוברת לביצוע קוד הפונקציה. כאשר הפונקציה מסתיימת התוכנית חוזרת למקום בו נכתב הזימון כאשר יש בידיה את הערך שהוחזר על ידי הפונקציה.

לפי פרדיגמת התכנות הפרוצדורלי יש לפרק את התוכנית לכמה שיותר פונקציות קטנות שכל אחת מהן תבצע מינימום פעולות פשוטות. פונקציות נקראות גם כן תת-תוכניות, שם זה מרמז על כך שהן חלקים מהתוכנית הגדולה כאשר כל פונקציה מתפקדת כתוכנית קטנה בפני עצמה.

עד כה כבר הכרתם פונקציות שכבר קיימות בספריות של C++‎, לדוגמה sqrt שמקבלת מספר כפרמטר ומחזירה את השורש הריבועי שלו. כמו כן נאמר שגם main היא פונקציה. ההבדל בין פונקציה sqrt לפונקציה main הוא שפונקציה sqrt כבר נכתבה ואנחנו רק השתמשנו בה (זימנו אותה), ואילו את main אנחנו כתבנו בעצמנו, בזאת הגדרנו מה היא תעשה, ומערכת ההפעלה זימנה אותה. נסביר כעת כיצד לכתוב פונקציות ולקרוא להן.

קריאה לפונקציות

נתבונן תחילה באופן השימוש בפונקציות. על מנת לקרוא לפונקציות שקיימות כבר בספריות C++‎ רשמנו את שם הפונקציה ואחריו את הפרמטרים בתוך סוגריים. לדוגמה:

double alpha = atan2(y, x);

כדאי לדעת: הפונקציה atan2 מקבלת שיעורי ווקטור ומחזירה את הזווית שבין הווקטור לבין ציר ה-x. תפקידה דומה ל-atan(y/x)‎ מלבד ש-atan2 עובדת באופן תקין גם כאשר שיעור ה-x שווה ל-0. פונקציות מתמטיות אלה נמצאות בספרייה <cmath>.

בדוגמה זו קראנו לפונקציה בשם atan2. שני הפרמטרים שנתנו לפונקציה הם y ו-x. כיוון שהפונקציה מחזירה ערך, אנחנו שמרנו אותו במשתנה alpha. לאו דווקא יש לשמור את הערך שמחזירה פונקציה. קיימות פונקציות רבות שהערך המוחזר הוא לא המטרה שעבורה נקראה הפונקציה, בעיקר כשערך זה מסמל שגיאה. לדוגמה הפונקציה הנפוצה שמשמשת את מתכנתי C לקלט, שמה scanf, מחזירה את מספר הערכים שנקלטו בהצלחה. למרות זאת, הרבה מניחים את תקינות הקלט ולא בודקים ערך זה.

קריאה לפונקציה היא מעבר ביצוע התוכנית ממקום אחד בקוד למקום שני. בניגוד ללולאות או תנאים, התוכנית תחזור למקום ממנו נקראה הפונקציה כאשר הפונקציה תסתיים. ברגע הקריאה לפונקציה התוכנית דוחפת את הפרמטרים של הפונקציה אל המחסנית (אזור מיוחד בזיכרון), שומרת את כתובת החזרה (גם על המחסנית) ורק אז מבצעת קפיצה אל קוד הפונקציה עצמה. כאשר התוכנית מסיימת לבצע את קוד הפונקציה היא שולפת מהמחסנית את כתובת החזרה ומבצעת קפיצה על פיה. שיטה זו מאפשרת, גם לקרוא לכל פונקציה שהיא מכל מקום בתוכנית, וגם קריאות רקורסיביות (קריאות לפונציה אחת מתוך עצמה).

חשוב להבין שלעומת שפות אחרות, כמו Pascal למשל, הקריאה לפונקציה לא נעשת כאשר אנו כותבים את שמה. שם הפונקציה מייצג את הכתובת שלה בזיכרון המחשב. הפונקציה נקראת על ידי אופרטור קריאה לפונקציה: () (סוגריים), הוא זה שמבצע את הקפיצה לפי כתובת זו. אופרטור זה מיוחד בכך שיכול לקבל מספר שרירותי של אופרנדים. האופרנד הראשון הוא שם הפונקציה שאותה אנו רוצים לקרוא לה, במקום שם הפונקציה ניתן לתת גם מצביע לפונקציה (למד בהמשך על מצביעים). שאר האופרנדים הם הפרמטרים שיש להעביר אל הפונקציה. הטיפוסים של הפרמטרים המועברים לפונקציה צריכים להתאים לטיפוסים של הפרמטרים בהכרזה על הפונקציה או ניתנים להמרת implicit אליהם (ראה למטה). כיוון שהקריאה מבוצעת על ידי אופרטור אז יש צורך לכתוב אותו גם כאשר לפונקציה אין פרמטרים.

נכתוב בפרק זה פונקציה שמטרתה תהיה לעגל מספר שיבוא בפרמטר הראשון אל הכפולה הקרובה ביותר של חזקה של 10. החזקה של 10 אליה יש לעגל תבוא בפרמטר השני. הפונקציה תחזיר את התוצאה לאחר העיגול. נקרא לפונקציה זו בשם roundTo. לדוגמה נביא מספר קריאות לפונקציה זו:

cout << roundTo(16, 0) << ", ":
cout << roundTo(16, 1) << ", ":
cout << roundTo(16, 2) << ", ":
cout << roundTo(54, 2) << endl:

הפלט התקין צריך להיות:

16, 20, 0, 100

הגדרת פונקציות

שימו לב: הכרזה או הגדרה של הפונקציה תעשה לפני השימוש הראשון בה. טרם למדנו על הכרזות, יש לכתוב את הגדרת הפונקציות לפני פונקציית main.

כותרת הפונקציה

כל הגדרה של פונקציה תתחיל מכותרתה. כותרת הפונקציה מגדירה בסדר הבא את:

• הטיפוס של הערך המוחזר מהפונקציה – זהו טיפוס כלשהו, מובנה או מוגדר על ידי המתכנת. ניתן במקום זאת לרשום את המילה השמורה void שפירושה שהפונקציה לא מחזירה ערך (ראה בהמשך). לא נכון לקרוא לטיפוס המוחזר מהפונקציה בשם "טיפוס הפונקציה". זו טעות מכיוון שטיפוס הפונקציה הוא טיפוס המצביע אליה (למדו בפרק על מצביעים).
• שם הפונקציה – הכללים לבחירת שם הפונקציה זהים לכללים לבחירת כל שם אחר ב-C++‎. נשתמש בשם זה על מנת לקרוא לפונקציה משאר התוכנית.
• טיפוסים ושמות הפרמטרים – רשימה זו תבוא בסוגריים אחרי שם הפונקציה. כל פרמטר יהיה מופרד בפסיקים משאר הרשימה. הגדרת פרמטרים אלה דומה להגדרה של משתנים מקומיים, הם אף מתפקדים וממומשים כמשתנים מקומיים לכל דבר. ההבדל היחידי הוא בהגדרה: נצטרך לרשום טיפוס לכל פרמטר בנפרד, גם אם כולם מאותו הטיפוס. שם הפרמטר ישמש אותנו אך ורק בגוף הפונקציה בפניות אליו, לכן אם מסיבות כלשהן הפרמטר לא נמצא בשימוש, ניתן לא לתת לו שם.

להלן כדוגמה כותרת הפונקציה שנכתוב בפרק זה:

int roundTo(int number, int exponent)

משמעות הכותרת היא: הפונקציה נקראת roundTo, היא מקבלת שני פרמטרים מטיפוס שלם ששמם number ו-exponent והיא מחזירה ערך מטיפוס שלם.

גוף הפונקציה

הגדרה של פונקציה מכילה את קוד הפונקציה, כלומר היא מגדירה בפירוש מה הפונקציה עושה. לעיתים קוראים להגדרה גם מימוש הפונקציה. כאשר אנו מגדירים פונקציה אנו נכתוב אחרי הכותרת את גופה בתוך בלוק התחום בסוגריים מסולסלים. בלוק זה יכיל הוראות הניתנות לביצוע, בין השאר, כמו בכל בלוק אחר, גם בבלוק הפונקציה נוכל להגדיר משתנים מקומיים (לוקאליים). משתנים אלה יושמדו בעת יציאה מהפונקציה. בתוך גוף הפונקציה נוכל להשתמש בפרמטרים שהפונקציה מקבלת. פרמטרים אלה גם מתפקדים כמשתנים מקומיים. נכתוב את גוף הפונקציה roundTo (כרגע לפני ה-main):

int roundTo(int number, int exponent)
{
    int powerOfTen = 1;
    for(int i = 0; i < exponent; i++)
        powerOfTen *= 10;

    int result = (number + powerOfTen/2)/powerOfTen*powerOfTen;
    return result;
}

// main goes here:
int main()
{
    cout << "A call to roundTo(34567, 2) returns " << roundTo(34567, 2) << endl;
    return 0;
}

הפלט התקין צריך להיות:

A call to roundTO(34567, 2) returns 34600

בפונקציה זו הגדרנו משתנה לוקאלי powerOfTen ושמרנו לתוכו את החזקה של 10 שאליה ברצוננו לעגל את המספר. בשורה לפני האחרונה של גוף הפונקציה אנו מעגלים את המספר ושומרים את התוצאה במשתנה עזר result. לאחר מכן בשורה האחרונה אנו מחזירים (return) את הערך שנמצא במשתנה result.

המשתנים הלוקאליים (מקומיים) נקראים גם משתנים אוטומטיים (auto). הקצאת זיכרון עבור משתנים אלה מתבצעת באופן אוטומטי כמו גם שיחרורו. זיכרון זה הוא זיכרון המחסנית. כיוון שבעת יציאה מהפונקציה המחסנית מוחזרת למצבה הקודם לפני קריאתה, כל המשתנים הלוקאליים נשלפים ממנה.

הוראת return

על מנת להחזיר ערך מהפונקציה נשתמש בהוראת return. הוראה זו מחזירה את ערך הביטוי שנכתב אחריה. בדוגמה שלמעלה אנחנו מחזירים את ערכו של המשתנה result, כמו כן, ניתן היה להסתדר גם בלעדיו: לכתוב את הביטוי אחרי המילה השמורה return ובכך להחזיר ישירות את תוצאתו. הטיפוס של הביטוי חייב להיות זהה לטיפוס של הערך המוחזר על ידי הפונקציה (מצויין בתחילת כותרת הפונקציה) או ניתן להמרת implicit אליו. בדוגמה שלנו הטיפוסים מתאימים זה לזה ולא תיווצר שום בעייה (מחזירים int).

את הוראת ה-return ניתן לכתוב לאו דווקא בסוף הפונקציה. כאשר מבוצעת הוראת ה-return מכל מקום אחר בתוך גוף הפונקציה היא מפסיקה את ביצוע העתידי שלה, במילים אחרות התוכנית יוצאת מהפונקציה. תכונה זו של הוראה זו מאפשרת את קיצור הקוד ומניעת קינון תנאים, בדומה להוראת break.

כל פונקציה שבכותרתה מצויין טיפוס הערך המוחזר חייבת להחזיר ערך, כלומר בכל פונקצייה שטיפוס הערך המוחזר הוא לא void חייבת לכלול הוראת return שבה תסתיים ריצתה. לדוגמה הפונקציה הבאה תקינה:

int f()
{
    int n;
    for(;;)
    {
        cout << "Enter a positive integer:\n";
        cin >> n;
        if(n > 0)
            return n;

        cout << "It's not positive! ";
    }
}

בסוף גוף הפונקציה אין הוראת return, אבל התוכנית אף פעם לא תגיע לסוף בלוק הפונקציה מהסיבה שהיא מכילה לולאה אינסופית. הלולאה תיפסק רק כאשר תתבצעה הוראת ה-return שתצא מתוך הפונקציה ולכן ההוראה האחרונה שתתבצעה תהיה תמיד הוראת ה-return. לעומת זאת הפונקציה הבאה לא תקינה:

int f()
{
    int n;
    cout << "Enter a positive integer:\n";
    cin >> n;
    if(n > 0)
        return n;

    cout << "It's not positive! ";
}

הסיבה היא שכאשר התוכנית תקלוט מספר שלילי, היא תגיע לסוף הפונקציה, לא תמצא את הוראת ה-return ולא תדע איזה ערך להחזיר. מהדר טוב צריך להתריע על העדר הוראות ה-return.

טיפוס void

בשפות אחרות מפרידים את המושג "פונקצייה" מ-"פרוצדורה" (למשל ב-Pascal יש מילה שמורה function ומילה procedure, ב-Visual Basic יש Function ויש Sub). ב-C++‎ אין הפרדה זו: פרוצדורה היא פונקציה שלא מחזירה ערך. כדי להגדיר פונקציה שלא תחזיר ערך יש לכתוב את הטיפוס void (ריק) בטיפוס המוחזר שלה. טיפוס זה מיוחד בכך שלא ניתן ליצור משתנה מטיפוס זה. טיפוס זה משמש ליצירת טיפוסים מורכבים.

כאשר הפונקציה לא מחזירה ערך (פונקציית void), לא הכרחי להשתמש בהוראה return. אם בכל זאת נרצה לצאת מהפונקציה נוכל לרשום return ללא ביטוי אחריו:

void g()
{
    int n;
    cin >> n;
    if(n < 0)
        return;

    cout << "I'm a void function!\n";
}

פונקציה זו תקינה. כמו כן, אם נכתוב אחרי ה-return ביטוי שהטיפוס שלו הוא לא void, המהדר יתן שגיאה.

אחרי ה-return כן ניתן לכתוב ביטויים שהטיפוס שלהם הוא void, לדוגמה ניתן להחזיר את ערך ה-void המוחזר מפונקציית void אחרת, או ליצור ערך "void" זמני (כמובן פעולות אלה הן אך ורק דרכי כתיבה שונות, הרי לא קיימים ערכי void). אפשרות זו נוספה ל-C++‎ כדי להקל על יצירת תבניות עם פרמטרי void.

return void();
return f();

בהנחה ש-f היא פונקציית void, שתי הוראות אלו תהינה נכונות כאשר נכתובן בפונקציה g.

פונקציית main

כפי שנאמר כבר פעמים רבות, main גם היא פונקציה. פונקציה זו מיוחדת ממספר בחינות, נדון בהן כאן.

הערך המוחזר מפונקציה main, מטרתו לסמל סיום מוצלח או שגיאה כלשהי. אפס מסמל סיום מוצלח, ואילו כל מספר אחר מסמל שגיאה. הערך הזה מוחזר למערכת ההפעלה שכביכול קראה לפונקציה main. במערכות הפעלה שונות ניתן לברר בדרכים שונות מה הערך המוחזר מתוכנית זו או אחרת. לרוב המשתמש לא יודע על ערך מוחזר זה, ומערכת ההפעלה אף תתעלם ממנו.

פונקציה main יוצאת דופן: על אף שהיא מחזירה ערך, היא לא חייבת לכלול את הוראת return. במקרה והיא תסתיים ללא הוראה זו, מערכת ההפעלה תקבל ערך המסמל סיום מוצלח, כלומר אפס. ניתן לראות זאת כאילו המהדר מוסיף אוטומטית הוראה return 0; בסוף הפונקציה.

לפי התקן main צריכה להחזיר ערך int. חלק מהמהדרים מאפשרים להגדיר main שתחזיר void, הדבר לא לפי התקן.

שקלו לדלג על נושא זה נושא זה קשור למערכים ולמצביעים. ניתן להבין את הנכתב פה גם ללא ידע בנושאים אלה, אך עדיף לחזור לפה כשתלמדו אותם.

עד כה main לא קיבלה פרמטרים. אבל, ניתן להגדיר פונקציה זו גם עם הכותרת הבאה:

int main(int argc, char *argv[])

במקרה זה הפונקציה תקבל שני פרמטרים שמשמשים לקבלת שורת הפקודה שאיתה הורצה התוכנית. בסביבות חלונאיות המשתמש לא מתעסק, בדרך כלל, עם שורה זו, אך עדיין שורה זו קיימת. כאשר מורצת התוכנית ניתן להעביר אליה ארגומנטים שונים שיקבעו את פעולתה. למשל ניתן להריץ את התוכנית program.exe כך (משורת הפקודה):

program.exe --read myfile.txt

(אופן הרצת התוכנית משורת הפקודה יכול להיות שונה במערכות הפעלה שונות). בדוגמה זו, שתפעל תחת Microsoft Windows או Linux, הפונקציה main תקבל את הפרמטרים הבאים:

• הפרמטר הראשון הוא מספר הארגומנטים שהועברו לתוכנית (פלוס אחד). בדוגמה זו הועברו 2 ארגומנטים, לכן argc == 3.
• הפרמטר השני הוא מערך של מחרוזות (על מערכים למד בהמשך). פשטנית: פרמטר זה מכיל את הארגומנטים שהועברו לתוכנית, בסדר שהם נכתבו. הפרמטר הראשון (מספרו אפס) הוא שם של קובץ ההרצה של התוכנית:

argv[0]: "program.exe"
argv[1]: "--read"
argv[2]: "myfile.txt"

כאשר argv[n]‎ הוא האיבר במערך שמספרו n.

הכרזת פונקציות

לפני שנוכל להשתמש בשם כלשהו ב-C++‎, לרוב, תחילה נצטרך להכריז עליו או להגדיר אותו. במילים אחרות: המהדר שקורא את קבצי התוכנית מהתחלה עד הסוף, צריך להתקל כבר בהכרזת שם זה על מנת להכירו. ההכרזה אומרת למהדר שקיים שם מסויים (למשל i) ושיש להתייחס אליו כלדבר מסויים (למשל כלמשתנה מטיפוס int). דבר זה תקף גם עבור שמות הפונקציות. הפונקציות שנמצאות בספריות כלשהן (למשל atan2 שהשתמשנו בה למעלה), מוכרזות בקבצי ההכללה של הספריות אלה (דוגמה <cmath>).

במקרה של תוכנית פשוטה בעלת קובץ אחד, נוכל לסדר את הפונקציות בסדר כזה שכל אחת תהיה מוגדרת לפני השימוש הראשון בה. לדוגמה כאשר קראנו לפונקציה roundTo מפונקציית main, הגדרנו אותה לפני ה-main והסתדר ללא הכרזות. ארגון קוד כזה גורם להופעת פונקציה main בסוף הקוד בתור פונקציה אחרונה:

void f()
{
    cout << "in f();\n";
}

void g()
{
    cout << "in g();\n";
    f();
}

int main()
{
    g();
    f();
    return 0;
}

כמו כן קיימים מתכנתים המעדיפים להגדיר את הפונקציות אחרי ה-main על מנת ש-main תהיה בהתחלה. במקרה כזה עליהם להוסיף שורות נוספות לפני פונקציית main שהן שורות ההכרזה.

כאשר נכתוב פונקציה משלנו, לפעמים חובה להכריז עליה לפני שנשתמש בה. אנחנו חייבים להשתמש בהכרזה כאשר אנחנו מפרקים את התוכנית למודולים (למספר קבצי קוד, לרוב עם סיומת cpp), או כאשר אנחנו משתמשים בשתי פונקציות רקורסיביות הדדיות הקוראות זו לזו (למד בהמשך).

ההכרזה תכיל את כותרת הפונקציה שתסתיים בנקודה פסיק. גוף הפונקציה לא יבוא בהכרזה מהסיבה הפשוטה שהוא זה שמבדיל בין הגדרה והכרזה. לדוגמה הכרזת הפונקציה roundTo תראה כך:

int roundTo(int number, int exponent);

הכרזת הפונקציה צריכה להכיל את אותו השם, אותו טיפוס מוחזר ואותם טיפוסי הפרמטרים כמו גם הגדרתה. כנאמר למעלה שמות הפרמטרים ניתנים אך ורק על מנת לפנות אליהם מתוך גוף הפונקציה עצמה, לכן כאשר אין בהם צורך נוכל למחוק אותם:

int roundTo(int, int);

כאשר כותבים את הקריאה לפונקציה, סביבות פיתוח שונות נותנות רמזים שמכילים את כותרת הפונקציה. על מנת שרמזים אלה יעזרו להזכר (או להבין) במשמעות הפרמטרים, כדאי בכל זאת לכתוב את שמותם המלאים כדי שנדע מה תפקיד הפרמטר הראשון ומה תפקיד הפרמטר השני, גם כששניהם מטיפוס זהה. כמו כן אם ניתנים שמות לפרמטרים הם לא חייבים להיות זהים בין ההכרזה וההגדרה.

קוד הכתוב בסגנון "הגדרת פונקציה אחרי השימוש בה" יראה כך:

int roundTo(int number, int exponent);
// ... כאן תבואנה כל ההכרזות ...

// main
int main()
{
    cout << "A call to roundTo(34567, 2) returns " << roundTo(34567, 2) << endl;
    return 0;
}

int roundTo(int number, int exponent)
{
    // מימוש הפונקציה‎
}

// כאן יבואו המימושים (ההגדרות) של שאר הפונקציות

בסגנון זה יש יתרון: ניתן לכתוב את הפונקציות בכל סדר שנרצה, אך קיים גם חיסרון: יש צורך להוסיף כל פונקציה לרשימה של ההכרזות בתחילת הקובץ ולזכור לשנות את ההכרזות כאשר משנים את הפרמטרים.

כאשר השתמשנו בקריאה לפונקציה שלא הכרזנו עליה, במקרה ולא הגדרנו את הפונקציה המהדר לא הכיר אותה ונתן שגיאה. כאשר הגדרנו אותו אבל קראנו עם פרמטרים שגויים המהדר יכל לתת לנו את השורה המתאימה בה הייתה השגיאה. כאשר אנחנו מכריזים על פונקציה אנחנו "משתיקים" את המהדר כדי שהוא לא יתלונן על השימוש בפונקציה שלא הוגדרה. הבדיקה של הטיפוסים והקישור של הקריאה אל הכתובת בה נמצאת הפונקציה, מתבצעים על ידי המקשר. במקרה והכרזנו על הפונקציה הקובץ יהודר ללא שגיאות. אבל במקרה ולא הגדרנו אותה השגיאה תתגלה בזמן קישור. בדרך כלל המקשר, מטבעו, לא יודע את המקום בו קרתה השגיאה בקוד המקור, ולכן יש להכיר יותר את השגיאות שהוא יתן:

• במקרה ולא קיימת הגדרה של פונקציה שהכרזנו או רשימת הפרמטרים שלה לא מתאימה להכרזה, המקשר יתן שגיאה בסגנון:

main.obj : error LNK2001: unresolved external symbol "int __cdecl f(void)" (?f@@YAHXZ)

(נלקח מהמקשר של Microsoft Visual Studio 2005. הדבר המשותף למקשרים הוא שלא ניתנת שורה מסויימת בה קרתה השגיאה)

• במקרה והטיפוס המוחזר לא תואם בין ההגדרה וההכרזה המהדר יתן שגיאה.
• במקרה וההכרזה תואמת להגדרה אך הקריאה לא תואמת להכרזה, המהדר יתן שגיאה רגילה של אי התאמה במקום הקריאה.

רקורסיה

פונקציה רקורסיבית היא פונקציה שקוראת לעצמה, באופן ישיר או בעקיפין. למשל, לפי ההגדרה של סדרת פיבונאצ'י ניתן לכתוב את הפונקציה הבאה:

int Fibonacci(int n)
{
    if(n == 0)
        return 0;
    else if(n == 1)
        return 1;
    else
        return Fibonacci(n-1) + Fibonacci(n-2);
}

פונקציה זו מקבלת כפרמטר את אינדקס האיבר בסדרה, מחשבת ומחזירה את ערך האיבר עצמו. כמו בכל פונקציות רקורסיביות במחשב צריך להיות תנאי עצירה לרקורסיה, על מנת שהיא לא תהיה אינסופית. תנאי עצירה זה (המקרה הפשוט) הוא כאשר מספר האיבר בסדרה הוא 0 או 1. במקרה זה אנו יודעים את התשובה ומחזירים את הערך של האיבר בלי לחשבו. במקרה ואינדקס גדול מ-1 אנחנו מחשבים אותו על בסיס האיברים הקודמים לו: אנחנו מחברים את האיבר הקודם Fibonacci(n-1)‎ ואת האיבר לפני הקודם Fibonacci(n-2)‎. הנחנו את תקינות הפרמטר n ולא בדקנו את המקרה בו הוא שלילי.

פונקציה זו היא רקורסיבית מפני שהיא קוראת לעצמה: בכל קריאה שעבורה n גדול מ-1 היא קוראת לעצמה פעמיים. עבור כל קריאה לפונקציה כזאת נוצרים עותקים של כל המשתנים המקומיים (כולל הפרמטרים), והם מושמדים כאשר הפונקציה אליה הם שייכים תסתיים. מכיוון ש-Fibonacci קורא לעצמו לפני שהוא מסתיים, נוצר עוד עותק של הפרמטר n ושל כתובת החזרה מהפונקציה. כנאמר, המשתנים המקומיים, הפרמטרים וכתובת החזרה נמצאים על המחסנית. כיוון שהמחסנית היא אזור מוגבל בזיכרון, היא עלולה להתמלא. במקרה זה התוכנית תקרוס בזמן ריצה עקב גלישה מהמחסנית (Stack Overflow). במחשבים של היום, גודל המחסנית מספיק עבור רוב צרכי התוכנות, גם עבור פונקציות רקורסיביות. גלישה מהמחסנית תקרה כאשר יש שגיאה בתנאי העצירה של הרקורסיה והיא תהיה לאינסופית, או כאשר האלגוריתם שכתבנו באמת משתמש בעומק רקורסיה גדול מדיי.

נמחיש את אופן הקריאות הרקורסיביות באמצעות עץ:

כל צומת בעץ זה מייצג זימון אחד של הפונקציה Fibonacci;. החצים מייצגים את הזימונים עצמם, לדוגמה: Fibonacci(5)‎ קורא ל-Fibonacci(4)‎ ואחרי ש-Fibonacci(4)‎ מסתיים Fibonacci(5)‎ יקרא ל-Fibonacci(3)‎. אף זימון של פונקציה לא יסתיים כל עוד מתבצע אחד הזימונים המקוננים (הרקורסיביים). הם המיוצגים על ידי הצאצאים של אותו הצומת. לדוגמה, כאשר התוכנית יורדת לעומק הרקורסיה המקסימלי (לתחתית העץ משמאל) קיימים על המחסנית 5 עותקים של כל המשתנים המקומיים. Fibonacci(5)‎ לא יסתיים כל עוד כל תת-העצים מימין ומשמאל לא יסיימו להתבצע.

מניתוח מתמטי של הפונקציה הזו ניתן לקבל שזמן ריצתה שווה ל-$\Theta \left(\phi ^{n}\right)$ (זהו מספר הצמתים בעץ שלמעלה). עומק הרקורסיה המרבי, הוא גובה העץ, ומשיקול פשוט ברור שערך זה הוא $\Theta \left(n\right)$. שני המאפיינים הללו מראים על אי-יעילות האלגוריתם הרקורסיבי לחישוב מספרי פיבונאצ'י. אלגוריתם איטרטיבי (עם לולאה) יתבצע תוך $\Theta \left(n\right)$ ויקח $O\left(1\right)$ מנפח הזיכרון. שימוש בנוסחה למספרי פיבונאצ'י תחושב תוך $\Theta \left(\log n\right)$. מצד שני, נניח שבידינו מחשב 32 סיביות ועבור המחסנית מוקצה קטע זיכרון בגודל של מגה-בית אחד. במקרה זה הפרמטר n וכתובת החזרה יתפסו ביחד 8 ביתים, ולכן עומק הרקורסיה המקסימלי האפשרי יהיה בקירוב 131000. אבל, גודל מספר הפיבונאצי הזה הוא כ-$2^{91000}$ מה שהרבה מעבר לגודל המשתנה של 32 סיביות, כתוצאה כל שאר הסיביות חוץ מ-32 הראשונות יעלמו. מספר פיבונאצי הגדול ביותר שיחושב בהצלחה, גם עבור אלגוריתם איטרטיבי, יהיה Fibonacci(47)‎.

מלבד הקלות בפתרון בעיות שונות באמצעות רקורסיה, ניתן לעיתים גם ליעל את התוכנית באמצעותה. אלגוריתמים רבים המסתמכים על עקרון הפרד ומשול נכתבים לרוב באמצעות פונקציה רקורסיבית, לדוגמה: מיון מהיר, עצי BSP ועוד'. אלגוריתמים אחרים - אף על פי שהם קלים לכתיבה והבנה בצורה רקורסיבית, הפתרון האיטרטיבי שלהם גם הוא פשוט. לדוגמה: חיפוש בינארי, חיפוש בעץ, מיון מיזוג ועוד', כל אלה מתוארים באופן רקורסיבי, אבל ניתן לכתוב את אותו האלגוריתם ללא שימוש ברקורסיה.

במקרים פשוטים ניתן מלכתחילה להמנע מרקורסיה. מדובר במקרים בהם הפונקציה הרקורסיבית מזמנת את עצמה לכל היותר פעם אחת:

void f(/* params */)
{
    if(/* termination condition */)
        /* termination code */
    else
    {
        /* pre-call code */
        f(/* params */);
        /* post-call code */
    }
}

במקום פונקציות רקורסיביות מהסוג הזה ניתן להסתפק בשתי לולאות:

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 */
}

כאשר אחרי הקריאה לפונקציה הרקורסיבית לא מתבצעות פעולות נוספות, כלומר אין קטע קוד "post-call code", הלולאה השנייה בפתרון האיטרטיבי מתבררת כמיותרת ולכן גם אין צורך במונה "עומק הרקורסיה" n. שימו לב שהפונקציה Fibonacci קוראת לעצמה לכל היותר פעמיים, לכן הפתרון האיטרטיבי שלה הוא לא מהתבנית הזו (ראה תרגילים).

פרמטרים שרירותיים

שימו לב: פונקציות אלה היו נפוצות בשפת C ולכן הן נתמכות גם ב-C++‎. ב-C++‎ קיימים תחליפים לפונקציות אלה ולכן נסביר נושא זה על ידי השוואה לשפת C.

בשפת C ניתן היה להגדיר פונקציה שתקבל מספר שונה של פרטרים בכל קריאה אליה, כמו כן פרמטרים אלה יכלו להיות מכל טיפוס שהוא. בשפת C השתמשו בפונקציות כאלה בעיקר לצורך פלט, קלט ועיצוב המחרוזות. לדוגמה, נתבונן בהכרזת הפונקציה הידועה printf:

int printf(const char *format, ...);

הכרזת פונקציה זו נמצאה בספרייה <stdio.h> ב-C וניתן לגשת אליה גם מתוך <cstdio> ב-C++‎. פונקציה זו משמשת לפלט בקרב מתכנתי C. הפונקציה מאפשרת להדפיס כל מספר ערכים שנרצה בקריאה אחת. שלוש הנקודות בסוף רשימת הפרמטרים אומרות שיכולים לבוא פרמטרים נוספים בנוסף לפרמטרים המוגדרים לפני כן. ב-printf, הפרמטר הראשון הוא מחרוזת רגילה. מחרוזת זו מכילה סימנים מיוחדים במקומות בהם נרצה להכניס ערך של משתנה מסויים. הערכים עצמם יבואו בפרמטרים הבאים, מספרם וטיפוסם יכול להיות כל שנרצה. נראה שימוש לדוגמה:

double pi = 3.14;
int n = 20;

printf("The value of π is %g\n", pi);
printf("Square of %d is %d\n", n, n*n);

פלט קטע זה יהיה:

The value of π is 3.14
Square of 20 is 400

בדוגמה זו קראנו לפונקציה printf פעם אחת עם שני פרמטרים ופעם שנייה עם שלושה פרמטרים. הפונקציה צריכה באיזשהי דרך לדעת את מספר הפרמטרים המדוייק ואת טיפוסם על מנת להשתמש בהם, אם לא, התנהגות התוכנית לא מוגדרת והיא עלולה לקרוס. כדי לדעת אותם, הפונקציה חייבת לקבל לפחות פרמטר אחד שטיפוסו מוגדר במדוייק, לפיו הפונקציה תקבע את נתוני שאר הפרמטרים. בדוגמה עם printf, היא בודקת את מחרוזת ה-format ולפי מספר סימני האחוזים קובעת את מספר הפרמטרים. את טיפוס הפרמטרים הפונקציה קובעת לפי התווים שבאים אחרי כל אחוז, לתווים אלה יש משמעות מוגדרת מראש. בדוגמה שלנו, בקריאה הראשונה העברנו לפונקציה מספר ממשי (שבר) שיודפס במקום הצירוף "‎%g", בקריאה השנייה העברנו שני מספרים שלמים שהראשון יודפס במקום צירוף "‎%d" הראשון והשני במקום השני.

כיוון שאם הפונקציה לא תקבל אף פרמטר היא לא תדע זאת, הפונקציה חייבת לקבל לפחות פרמטר אחד מטיפוס מוגדר. משמע הדבר שלא ניתן להגדיר פונקציה מהסוג:

void impossibleFunction(...);

החסרון העיקרי של printf הוא שהשימוש בה מסוכן, על אחריות המתכנת להעביר מחרוזת format תקינה לפונקציה, כך שתתאים לשאר הפרמטרים המועברים אליה. כמו כן, שגיאה נפוצה, היא שמעבירים מחרוזת משתנה כפרמטר format, על מנת להדפיסה, דבר זה עלול לגרום לקריסת התוכנית או לחור אבטחה במקרה ובמחרוזת זו יופיע אחד הסימנים המיוחדים בעלי משמעות ל-printf.

ב-C++‎ השתמשו בפתרון אחר להדפסת ערכים רבים: העמיסו את אופרטור ה->> (למד בהמשך על העמסת אופרטורים). בשיטה זו ניתן להשתמש גם במקרים אחרים בהם משתמשים ברשימת פרמטרים שרירותית. במקום שתי קריאות printf שלמעלה, נרשום:

cout << "The value of π is " << pi << "\n";
cout << "Square of " << n << " is " << n*n << "\n";

במקרה זה המתכנת לא יכול לטעות ולהביא לקריסת התוכנית. המהדר הופך כל שימוש ב->> לקריאה לפונקציה נפרדת שמקבלת אך ורק שני פרמטרים: הראשון הוא cout והשני הוא הערך שיש להדפיס. עבור כל טיפוס של הערך המודפס קיימת פונקציה בפני עצמה, כך למשל עבור פלט pi ו-n נקראות פונקציות שונות, אחת לפלט ערכי double ואחת לפלט ערכי int. לשיטה זו קיימים יתרונות נוספים: כפי שנראה בהמשך הספר, ניתן להוסיף אפשרות לפלט של טיפוסים נוספים שלא קיימים בשפה, לעומת זאת printf לא ניתנת להרחבה.

פתרון אחר הוא ארגון הפרמטרים בתוך מערך בעל גודל ומבנה ידוע והעברתו כפרמטר אחד.

פרמטרים אופציונליים

לפעמים הפונקציה שנכתוב תקבל פרמטר אחד או יותר שיקנה לה גמישות אך ברוב הקריאות לפונקציה זו נעביר דרכו את אותו הערך. למשל בתוכנית גראפית כלשהי נרצה לכתוב פונקציה שתצייר קו על המסך. הקו ימשך מנקודה (x1, y1) לנקודה (x2, y2) ועוביו יקבע בפרמטר width. הכרזת הפונקציה תראה כך:

void DrawLine(int x1, int y1, int x2, int y2, int width);

הפרמטר width נותן שליטה על מראה הקו. אבל, בדרך כלל רוב הקווים שהתוכניות מציירות הם בעובי מסויים. גם בתוכנית שלנו, יתכן ורוב הקווים יהיו בעובי של יחידה אחת. במקרה כזה, ברוב הקריאות לפונקציה זו, הפרמטר האחרון יהיה 1. במקום זאת נוכל להגדיר את הפרמטר width כאופציונלי, כלומר, בזימון נוכל לא לכתובו והמהדר יציב לתוכו ערך ברירת מחדל. כדי להגדיר פרמטר מסוים כאופציונלי, נרשום אחריו את סימן ההשמה ואת ערך ברירת המחדל, בדומה לאיתחול משתנה מקומי:

void DrawLine(int x1, int y1, int x2, int y2, int width = 1);

מבחינת קוד הפונקציה, פרמטרים אופציונליים הם פרמטרים רגילים. כמו כן, אין דרך לדעת האם בקריאה לפונקציה DrawLine הופיע בפרמטר width הערך 1 או שלא הופיע פרמטר זה כלל.

בשימוש בפרמטרים אופציונליים קיימים מספר כללים נוספים:

נוכל להגדיר כמה שנרצה פרמטרים אופציונליים אך כולם יבואו בסוף רשימת הפרמטרים. כמו כן, אם יש לנו פונקציה עם שני פרמטרים אופציונליים או יותר, נוכל להעביר לה פרמטר אופציונלי מסויים אך ורק אם העברנו לה את הפרמטרים הקודמים לו ברשימה. למשל, בהנתן הבפונקציה:

void f(int a = 123, double b = pi);

נוכל לזמן אותה ללא ציון אף פרמטר, עם ציון פרמטר ראשון (a) ועם ציון שני הפרמטרים ביחד, a ו-b. לעומת זאת לא נוכל להעביר לה רק את b מבלי לציין את a:

f();        // a = 123, b = pi
f(1);       // a = 1, b = pi
f(1, 2.2);  // a = 1, b = 2.2

f(2.2);     // a = 2, b = pi
f( , 2.2);  // Error, not C++
f(b: 2.2);  // Error, not C++

העמסת פונקציות

העמסת פונקציות (function overloading) היא יצירה של מספר פונקציות שלכולן אותו השם. הפונקציות נבדלות זו מזו על ידי רשימת הפרמטרים שלהן. באמצעות העמסת פונקציות נוכל לכתוב עבור טיפוסי פרמטרים שונים מספר מימושים של אותה הפונקציה. למשל נוכל להגדיר פונקציה שתדפיס מספר שלם, פונקציה שתדפיס מספר ממשי ופונקציה שתדפיס מחרוזת, כאשר שלושתן תקראנה print. ההבדל בין שלושת פונקציות אלה יהיה בטיפוסים של הפרמטרים שהן תקבלנה:

void print(int x)
{
    // Print an integer number
}

void print(float x)
{
    // Print a real number
}

void print(const char *str)
{
    // Print a string
}

העמסת פונקציות עוזרת לנו להמנע מ-"סגנון C" בו הצטרכו המתכנתים להוסיף בסוף שם כל אחת מהפונקציות תוספת שתרמוז על הטיפוס של הפרמטרים: print_int, print_float, print_string וכד'... דוגמה נוספת מהחיים היא OpenGL. בספרייה זו רוב הפונקציות קיימות במספר גרסות עבור מספר טיפוסים של פרמטרים, למשל הפונקציה glColor קיימת ב-32 גרסות שונות כאשר לכל גרסה שם שונה. באמצעות העמסת פונקציות יכלו מפתחי הסיפרייה לקרוא לכולן באותו השם אך כיוון שהסיפרייה פותחה במקורה עבור שפת C, הדבר לא כך הוא.

מבחינת מימוש הפונקציות המועמסות לא חל שינוי. נתרכז כרגע באופן קריאתן. כיוון שיש מספר פונקציות עם אותו השם יש צורך לדעת איזו גרסה תקרא. המהדר יחליט לאיזו פונקציה לקרוא לפי בדיקת הטיפוסים של הפרמטרים המועברים במקום הקריאה והשוואתם לטיפוסים של הפרמטרים בפונקציות הקיימות באותו שם. הכללים הם הבאים:

1. אם חלה התאמה מלאה של טיפוסי הפרמטרים ומספרם לאחת גרסות הפונקציה, זו הגרסה שתקרא.
2. אחרת, המהדר יחפש גרסה שמתאימה לאחר ביצוע המרות מרחיבות של הפרמטרים.
3. אחרת, המהדר יחפש גרסה שמתאימה לאחר ביצוע המרות מצרות של הפרמטרים.
4. אחרת, המהדר יחפש גרסה שמתאימה לאחר ביצוע המרות המוגדרות על ידי המתכנת.
5. אחרת, המהדר יחפש גרסה שמתאימה כי היא מקבלת פרמטרים שרירותיים.
6. אחרת לא קיימת פונקציה מתאימה ותהיה שגיאת הידור.

אם יש מספר גרסות שמתאימות לכלל הראשון המתקיים מבין אלה, הקריאה אינה חד-משמעית וגם היא תגרום לשגיאת הידור. כמו כן, הטיפוס של הערך המוחזר לא משפיע על החלטתו של המהדר.

נציג כעת מספר דוגמות בעיתיות:

print(1.5); // Error

בהנתן ההגדרות שלמעלה, המהדר לא יודע לאיזו משתי הגרסות הראשונות לקרוא (הגרסה השלישית לא מתאימה בכל אופן). כיוון שטיפוס המספר 1.5 הוא double, גם המרה ל-int בגרסה הראשונה וגם המרה ל-float בגרסה השנייה הן המרות מצרות, לכן הכלל הראשון שמתאים (מס. 3) הוא דו-משמעי.

פרק זה לוקה בחסר. אתם מוזמנים לתרום לוויקיספר ולהשלים אותו. ראו פירוט בדף השיחה.

הפרק הקודם: מערכים

פונקציות תרגילים

הפרק הבא: מצביעים והמשתנה המיוחס