עצרת רקורסיבית

חלק מהיחידה לוגיקה וזרימת תוכנית במסלול ה-C++ של Coddy. שיעור 46 מתוך 56.

העצרת של מספר היא דוגמה מושלמת להדגמת רקורסיה בפעולה. העצרת של n (נכתבת כך: n!) היא מכפלת כל המספרים השלמים החיוביים מ־1 ועד n. לדוגמה, 5! = 5 × 4 × 3 × 2 × 1 = 120.

מה שהופך את העצרת לאידיאלית עבור רקורסיה הוא שניתן להגדיר אותה במונחים של עצמה: n! = n × (n-1)!. כלומר, כדי לחשב 5!, מכפילים את 5 ב־4!, וכדי לחשב 4!, מכפילים את 4 ב־3!, וכן הלאה.

כך נראית פונקציית עצרת רקורסיבית:

int factorial(int n) {
    if (n <= 1) {           // מקרה בסיס: גם 0! וגם 1! שווים ל-1
        return 1;
    }
    
    return n * factorial(n - 1);  // שלב רקורסיבי: n! = n × (n-1)!
}

מקרה הבסיס עוצר את הרקורסיה כאשר n מגיע ל־1 או ל־0, ומחזיר 1. הצעד הרקורסיבי מכפיל את המספר הנוכחי בעצרת של המספר הבא הקטן ממנו. כשקוראים ל־factorial(4), החישוב הוא 4 × 3 × 2 × 1 באמצעות קריאות עוקבות עד שמגיעים למקרה הבסיס, ואז מכפילים את כל התוצאות יחד כשהקריאות חוזרות.

אתגר

קל

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

הקלט הבא יסופק:

מספר שלם n שמייצג את המספר שעבורו יש לחשב את העצרת

התוכנית שלכם צריכה:

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

השתמשו בפורמט הפלט המדויק הבא:

Factorial of [n] is [result]

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

נסו בעצמכם

#include <iostream>
using namespace std;

// TODO: כתבו כאן את הפונקציה שלכם לחישוב עצרת

int main() {
    // קראו את הקלט
    int n;
    cin >> n;
    
    // TODO: קראו לפונקציה לחישוב עצרת ושמרו את התוצאה
    
    // הדפיסו את התוצאה
    cout << "Factorial of " << n << " is " << result << endl;
    
    return 0;
}