הבדל מפתח – רקורסיה לעומת איטרציה
ניתן להשתמש ברקורסיה ואיטרציה כדי לפתור בעיות תכנות. הגישה לפתרון הבעיה באמצעות רקורסיה או איטרציה תלויה בדרך לפתור את הבעיה. ההבדל העיקרי בין רקורסיה לאיטרציה הוא שרקורסיה היא מנגנון לקרוא לפונקציה בתוך אותה פונקציה בעוד איטרציה היא לבצע קבוצה של הוראות שוב ושוב עד שהתנאי הנתון מתקיים. רקורסיה ואיטרציה הן טכניקות מרכזיות לפיתוח אלגוריתמים ובניית יישומי תוכנה.
מהי רקורסיה?
כאשר פונקציה קוראת לעצמה בתוך הפונקציה, היא ידועה בשם רקורסיה. ישנם שני סוגים של רקורסיה. הם רקורסיה סופית ורקורסיה אינסופית. לרקורסיה סופית יש מצב מסתיים. לרקורסיה אינסופית אין תנאי מסיים.
ניתן להסביר רקורסיה באמצעות התוכנית לחישוב גורמים גורמים.
n!=n(n-1)!, אם n>0
n!=1, אם n=0;
עיין בקוד למטה כדי לחשב פקטורי של 3(3!=321).
intmain () {
int value=fatorial (3);
printf(“Facttorial is %d\n”, value);
return 0;
}
intfatorial (intn) {
if(n==0) {
return 1;
}
else {
return n factorial(n-1);
}
}
בעת קריאה לפקטורי (3), הפונקציה הזו תקרא פקטוריאלית (2). בעת קריאה לפקטורי (2), פונקציה זו תקרא לפקטורי (1). ואז פקטוריאלי (1) יקרא פקטוריאלי (0). פקטוריאלי (0) יחזיר 1. בתוכנית לעיל, n==0 תנאי ב"אם בלוק" הוא תנאי הבסיס.לפי ה- Likewise, הפונקציה הפקטוריאלית נקראת שוב ושוב.
פונקציות רקורסיביות קשורות לערימה. ב-C, לתוכנית הראשית יכולות להיות פונקציות רבות. אז, main () היא הפונקציה הקוראת, והפונקציה שנקראת על ידי התוכנית הראשית היא הפונקציה שנקראת. כאשר הפונקציה נקראת, השליטה ניתנת לפונקציה הנקראת. לאחר השלמת ביצוע הפונקציה, הפקד מוחזר ל-main. ואז התוכנית הראשית ממשיכה. לכן, הוא יוצר רשומת הפעלה או מסגרת מחסנית כדי להמשיך בביצוע.
איור 01: רקורסיה
בתוכנית שלמעלה, כאשר מתקשרים לפקטורי (3) מהראשי, זה יוצר רשומת הפעלה בערימת השיחות. לאחר מכן, נוצרת מסגרת ערימה פקטוריאלית (2) על גבי הערימה וכן הלאה. רשומת ההפעלה שומרת מידע על משתנים מקומיים וכו'. בכל פעם שהפונקציה נקראת, נוצרת קבוצה חדשה של משתנים מקומיים בחלק העליון של הערימה. מסגרות ערימה אלה יכולות להאט את המהירות. באופן דומה ברקורסיה, פונקציה קוראת לעצמה. מורכבות הזמן של פונקציה רקורסיבית נמצאת לפי מספר הפעמים, הפונקציה נקראת. מורכבות הזמן עבור קריאת פונקציה אחת היא O(1). עבור n מספר של שיחות רקורסיביות, מורכבות הזמן היא O(n).
מה זה איטרציה?
איטרציה היא גוש הוראות שחוזר על עצמו שוב ושוב עד שהתנאי הנתון מתקיים. ניתן להשיג איטרציה באמצעות "ללולאה", "לעשות תוך כדי לולאה" או "בזמן לולאה". תחביר "ללולאה" הוא כדלקמן.
for (אתחול; תנאי; שנה) {
// הצהרות;
}
איור 02: "עבור דיאגרמת זרימת לולאה"
שלב האתחול מתבצע ראשון. שלב זה הוא להכריז ולאתחל משתני בקרת לולאה. אם התנאי נכון, ההצהרות בתוך הסוגרים המתולתלים יתבצעו. ההצהרות הללו פועלות עד שהתנאי מתקיים. אם התנאי הוא שקר, הפקד עובר להצהרה הבאה אחרי "לולאת for". לאחר ביצוע ההצהרות בתוך הלולאה, הפקד עובר לקטע שינוי. זה לעדכן את משתנה בקרת הלולאה. ואז המצב נבדק שוב.אם התנאי נכון, ההצהרות בתוך הסוגרים המתולתלים יבוצעו. בדרך זו חוזרת ה-"for loop".
ב"while loop", ההצהרות בתוך הלולאה מופעלות עד שהתנאי מתקיים.
while (מצב){
//statements
}
בלולאת "עשה תוך כדי", התנאי נבדק בסוף הלולאה. אז הלולאה מופעלת לפחות פעם אחת.
do{
//statements
} while(condition)
התוכנית למציאת הפקטורי של 3 (3!) באמצעות איטרציה ("ללולאה") היא כדלקמן.
int main(){
intn=3, פקטורי=1;
inti;
for(i=1; i<=n; i++){
factorial=פקטוריi;
}
printf(“הגורם הוא %d\n”, פקטורי);
return 0;
}
מהם הדמיון בין רקורסיה ואיטרציה?
- שתיהן טכניקות לפתרון בעיה.
- ניתן לפתור את המשימה ברקורסיה או איטרציה.
מה ההבדל בין רקורסיה ואיטרציה?
רקורסיה לעומת איטרציה |
|
| רקורסיה היא שיטה לקריאה לפונקציה בתוך אותה פונקציה. | איטרציה היא גוש הוראות שחוזר על עצמו עד שהתנאי הנתון מתקיים. |
| מורכבות החלל | |
| מורכבות החלל של תוכניות רקורסיביות גבוהה מאיטרציות. | מורכבות החלל נמוכה יותר באיטרציות. |
| Speed | |
| ביצוע הרקורסיה איטי. | בדרך כלל, איטרציה מהירה יותר מהרקורסיה. |
| מצב | |
| אם אין תנאי סיום, יכולה להיות רקורסיה אינסופית. | אם התנאי לעולם לא יהפוך לשקר, זה יהיה איטרציה אינסופית. |
| Stack | |
| ברקורסיה, המחסנית משמשת לאחסון משתנים מקומיים כאשר קוראים לפונקציה. | באיטרציה, הערימה אינה בשימוש. |
| קריאת קוד | |
| תוכנית רקורסיבית קריאה יותר. | התוכנית האיטרטיבית קשה יותר לקריאה מתוכנית רקורסיבית. |
סיכום – רקורסיה לעומת איטרציה
מאמר זה דן בהבדל בין רקורסיה ואיטרציה.ניתן להשתמש בשניהם כדי לפתור בעיות תכנות. ההבדל בין רקורסיה ואיטרציה הוא שרקורסיה היא מנגנון לקרוא לפונקציה בתוך אותה פונקציה ואיטרציה שלה כדי לבצע קבוצה של הוראות שוב ושוב עד שהתנאי הנתון מתקיים. אם ניתן לפתור בעיה בצורה רקורסיבית, ניתן לפתור אותה גם באמצעות איטרציות.
הורד את גרסת ה-PDF של רקורסיה לעומת איטרציה
ניתן להוריד את גרסת ה-PDF של מאמר זה ולהשתמש בה למטרות לא מקוונות לפי הערת ציטוט. אנא הורד כאן גרסת PDF ההבדל בין רקורסיה ואיטרציה
