רקורסיה: מקרה בסיס ומקרה רקורסיבי
עמוד זה דורש דפדפן עדכני (תומך ב-SharedArrayBuffer). אנא עדכן את Chrome, Edge, Firefox או Safari לגרסה העדכנית ביותר.
פונקציה הקוראת לעצמה
- רקורסיה היא כאשר פונקציה קוראת לעצמה כדי לפתור גרסה קטנה יותר מאותו בעיה.
- היא דורשת שני חלקים: מקרה בסיס שמפסיק, ומקרה רקורסיבי שמצמצם את הבעיה.
- ללא מקרה בסיס, היא הייתה קוראת לעצמה לנצח ומתמוטטת.
המקרה הבסיס
- המקרה הבסיס הוא הבעיה הקטנה ביותר שתוכל לפתור ישירות, ללא עוד קריאות.
- עבור פקטוריאל,
0!ו1!הם שניהם1— זהו המקרה הבסיס. - תמיד טפל במקרה הבסיס תחילה, כדי שהרקורסיה תישאר למקום להפסיק.
המקרה הרקורסיבי
- המקרה הרקורסיבי פותר את הבעיה באמצעות התשובה לקטנה ממנה.
n! = n × (n - 1)!, ולכןfactorial(n)מחזירn * factorial(n - 1).- כל קריאה חייבת להתקרב יותר למקרה הבסיס, אחרת היא לעולם לא תפסיק.
English
#include <stdio.h>
int factorial(int n) {
if (n <= 1) return 1; // base case
return n * factorial(n - 1); // recursive case
}
int main(void) {
printf("%d\n", factorial(5)); // 120
return 0;
}
ריקורסיה על מערך
- ניתן לבצע רקורסיה לאורך מערך על ידי העברת אינדקס הנע קדימה בכל קריאה.
- המקרה הבסיסי הוא "האינדקס הגיע לסוף" (חזרה
0עבור סכום). - המקרה הרקורסיבי הוא
a[i] + sum(a, i + 1, n)— הפריט הזה עלול להוסיף את הסכום של שאר האלמנטים.
טעויות נפוצות
- רקורסיה דורשת מקרה בסיסי, אחרת תרחש גלישה בעומק המערכת (Call Stack Overflow).
- כל שיחה חייבת לקרב למקרה הבסיסי.
כעת תנסו בעצמכם
- כתוב תחילה את המקרה הבסיסי, ולאחר מכן את המקרה הרקורסיבי הקורא לעצמו עם קלט קטן יותר.
- שמור על ערכי הבדיקה קטנים כדי שהמספרים יישארו בתוך טווח ה-
int. - אל תכתוב
main— הבוקר מספק אותו already.
חקור
רקורסיבי חוזר למעלה
הקראים מתפצלים למקרה בסיס, ולאחר מכן הערכים חוזרים למעלה.
רמת קושי 4/5 · 280 מטבעות + בונוס קטן בהשלמה הראשונה היום
השלם int factorial(int n) באמצעות רקורסיביות: החזר 1 עבור n <= 1 (המקרה הבסיסי), אחרת n * factorial(n - 1). אל תכתב פונקציה main.
לחץ על הרץ כדי לראות את התוצא כאן.
רמת קושי 4/5 · 280 מטבעות + בונוס קטן בהשלמה הראשונה היום
השלם int power(int base, int exp) באמצעות רקורסיביות (הנחה: exp >= 0): base מעוצה ל-0 היא 1, אחרת base * power(base, exp - 1). אל תכתב פונקציה main.
לחץ על הרץ כדי לראות את התוצא כאן.
רמת קושי 4/5 · 280 מטבעות + בונוס קטן בהשלמה הראשונה היום
השלם int array_sum(const int a[], int i, int n) באמצעות רקורסיביות: היא מחזירה את הסכום של a[i] עד a[n-1]. מקרה בסיסי: i >= n מחזירה 0. אל תכתב פונקציה main.
לחץ על הרץ כדי לראות את התוצא כאן.