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.
أخطاء شائعة
- التكرار يحتاج حالة أساسية، وإلا ستمتلئ مكدس الاستدعاءات.
- يجب أن يتحرك كل استدعاء نحو الحالة الأساسية.
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— لأن الفاحص يوفر واحداً تلقائياً.
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). لا تكتب a 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). لا تكتب a 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. لا تكتب a main.
Click Run to see the output here. · اضغط تشغيل لرؤية المخرجات هنا.