Recursion: base case and recursive case · רקורסיה: מקרה בסיס ומקרה רקורסיבי
A function that calls itself
- Recursion is when a function calls itself to solve a smaller version of the same problem.
- It needs two parts: a base case that stops, and a recursive case that shrinks the problem.
- Without a base case, it would call itself forever and crash.
פונקציה הקוראת לעצמה
- רקורסיה היא כאשר פונקציה קוראת לעצמה כדי לפתור גרסה קטנה יותר מאותו בעיה.
- היא דורשת שני חלקים: מקרה בסיס שמפסיק, ומקרה רקורסיבי שמצמצם את הבעיה.
- ללא מקרה בסיס, היא הייתה קוראת לעצמה לנצח ומתמוטטת.
The base case
- The base case is the smallest problem you can answer directly, with no more calls.
- For factorial,
0!and1!are both1— that is the base case. - Always handle the base case first, so the recursion has somewhere to stop.
המקרה הבסיס
- המקרה הבסיס הוא הבעיה הקטנה ביותר שתוכל לפתור ישירות, ללא עוד קריאות.
- עבור פקטוריאל,
0!ו1!הם שניהם1— זהו המקרה הבסיס. - תמיד טפל במקרה הבסיס תחילה, כדי שהרקורסיה תישאר למקום להפסיק.
The recursive case
- The recursive case solves the problem using the answer to a smaller one.
n! = n × (n - 1)!, sofactorial(n)returnsn * factorial(n - 1).- Each call must move closer to the base case, or it will never stop.
המקרה הרקורסיבי
- המקרה הרקורסיבי פותר את הבעיה באמצעות התשובה לקטנה ממנה.
n! = n × (n - 1)!, ולכןfactorial(n)מחזירn * factorial(n - 1).- כל קריאה חייבת להתקרב יותר למקרה הבסיס, אחרת היא לעולם לא תפסיק.
#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;
}
Recursion over an array
- You can recurse along an array by passing an index that moves forward each call.
- The base case is "the index has reached the end" (return
0for a sum). - The recursive case is
a[i] + sum(a, i + 1, n)— this item plus the sum of the rest.
ריקורסיה על מערך
- ניתן לבצע רקורסיה לאורך מערך על ידי העברת אינדקס הנע קדימה בכל קריאה.
- המקרה הבסיסי הוא "האינדקס הגיע לסוף" (חזרה
0עבור סכום). - המקרה הרקורסיבי הוא
a[i] + sum(a, i + 1, n)— הפריט הזה עלול להוסיף את הסכום של שאר האלמנטים.
Common mistakes
- Recursion needs a base case, or the call stack overflows.
- Each call must move closer to the base case.
טעויות נפוצות
- רקורסיה דורשת מקרה בסיסי, אחרת תרחש גלישה בעומק המערכת (Call Stack Overflow).
- כל שיחה חייבת לקרב למקרה הבסיסי.
Now you try
- Write the base case first, then the recursive case that calls itself on a smaller input.
- Keep test values small so the numbers stay inside an
int. - Do not write a
main— the checker provides one.
כעת תנסו בעצמכם
- כתוב תחילה את המקרה הבסיסי, ולאחר מכן את המקרה הרקורסיבי הקורא לעצמו עם קלט קטן יותר.
- שמור על ערכי הבדיקה קטנים כדי שהמספרים יישארו בתוך טווח ה-
int. - אל תכתוב
main— הבוקר מספק אותו already.
Recursion returns up · רקורסיבי חוזר למעלה
Calls split to a base case, then values return up. · הקראים מתפצלים למקרה בסיס, ולאחר מכן הערכים חוזרים למעלה.
Complete int factorial(int n) using recursion: return 1 for n <= 1 (the base case), otherwise n * factorial(n - 1). Do not write a main. · השלם int factorial(int n) באמצעות רקורסיביות: החזר 1 עבור n <= 1 (המקרה הבסיסי), אחרת n * factorial(n - 1). אל תכתב פונקציה main.
Click Run to see the output here. · לחץ על הרץ כדי לראות את התוצא כאן.
Complete int power(int base, int exp) using recursion (assume exp >= 0): base to the power 0 is 1, otherwise base * power(base, exp - 1). Do not write a main. · השלם int power(int base, int exp) באמצעות רקורסיביות (הנחה: exp >= 0): base מעוצה ל-0 היא 1, אחרת base * power(base, exp - 1). אל תכתב פונקציה main.
Click Run to see the output here. · לחץ על הרץ כדי לראות את התוצא כאן.
Complete int array_sum(const int a[], int i, int n) using recursion: it returns the sum of a[i] up to a[n-1]. Base case: i >= n returns 0. Do not write a main. · השלם int array_sum(const int a[], int i, int n) באמצעות רקורסיביות: היא מחזירה את הסכום של a[i] עד a[n-1]. מקרה בסיסי: i >= n מחזירה 0. אל תכתב פונקציה main.
Click Run to see the output here. · לחץ על הרץ כדי לראות את התוצא כאן.