C++/פונקציות/תרגילים

רקורסיה

מספרי פיבונאצ'י

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

פתרון

אחת האפשרויות מוצגת כאן. פתרון זה מבוסס על שמירת האיבר הקודם ולפני הקודם במשתנים f0 ו-f1. כאשר מחושב האיבר הבא (f2) כבר אין צורך באיבר שלפני הקודם וניתן "לזוז" איבר אחד קדימה.

int Fibonacci(int n)
{
    if(n <= 1)
        return n;

    int f0 = 1, f1 = 1;
    for(int i = 2; i < n; i++)
    {
        int f2 = f1 + f2;
        f0 = f1;
        f1 = f2;
    }
    return f1;
}

פתרון נוסף הוא שימוש בנוסחה ישירה לחישוב איברי הסדרה: $\ F_{n}={\frac {1}{\sqrt {5}}}\left(\left({\frac {1+{\sqrt {5}}}{2}}\right)^{n}-\left({\frac {1-{\sqrt {5}}}{2}}\right)^{n}\right)$

עצרת

בפרק על לולאות כתבת תוכנית שמחשבת עצרת: $n!=1\cdot 2\cdot 3\cdots n$. כתוב פונקציה שתחשב עצרת באמצעות אלגוריתם רקורסיבי.

פתרון

long Factorial(long n)
{
    if(n <= 1)
        return 1;
    else
        return Factorial(n-1)*n;
}