العودية
مُقدَّم| English | المعنى |
|---|---|
| recursive/rɪˈkɜːsɪv/ | تكراري |
| base case/beɪs keɪs/ | الحالة الأساسية |
| recursive case/rɪˈkɜːsɪv keɪs/ | الحالة التكرارية |
| call stack/kɔːl stæk/ | مكدس الاستدعاء |
| stack frame/stæk freɪm/ | إطار المكدس |
| stack overflow/stæk ˌəʊvəˈfləʊ/ | تجاوز سعة المكدس |
| memoisation/ˌmeməʊaɪˈzeɪʃn/ | الترميز التذكاري |
تعريف يتضمن نفسه
- كيف تنص على سلف؟ والدك هو سلف. وكذلك سلف والدك. هاتان الجملتان تعرفان سلسلة غير محدودة، والجملة الثانية تستخدم الكلمة التي تُعرّفها.
- هذا ليس حجة دائرية، لأن الجملة الأولى تحدد مكاناً تتوقف فيه السلسلة. بدونها، سيستمر التعريف إلى ما لا نهاية.
- يمكن كتابة البرامج بنفس الطريقة، وللمشاكل ذات شكل تلك السلسلة، يكون الحل التراجعي أقصر بكثير من الحلقة.
- هذه الدرس هو الحالة الأساسية والحالة التراجعية، كيفية تتبع الاستدعاء التراجعي، وما يفعله مكدس الاستدعاء في الأسفل.
الحالتان
FUNCTION Factorial(n : INTEGER) RETURNS INTEGER
IF n = 0 OR n = 1 THEN
RETURN 1 // base case
ELSE
RETURN n * Factorial(n - 1) // recursive case
ENDIF
ENDFUNCTION
- الحالة الأساسية هي نسخة من المشكلة صغيرة بما يكفي للإجابة عليها مباشرة، دون استدعاء إضافي. وهي ما يوقف التراجع.
- الحالة التراجعية تستدعي الدالة مرة أخرى بـ مدخل أصغر، متجهة نحو الحالة الأساسية.
- كلاهما مطلوب. التراجع بدون حالة أساسية لن يتوقف أبداً؛ وأحد مدخلاته لا ينكمش لن يصل أبداً للحالة الأساسية.
Every recursive algorithm must have a base case because:
الصعوبة 1/5 · 100 عملة + مكافأة صغيرة عند الإنجاز الأول اليوم
The base case is the condition that ends the chain of calls; without it the recursion runs forever.
Recursion is a natural fit for self-similar problems (trees, divide-and-conquer), but each call adds a stack frame — so without a base case it overflows the stack.
الصعوبة 1/5 · 100 عملة + مكافأة صغيرة عند الإنجاز الأول اليوم
A simple counting loop is cleaner for plain iteration; recursion shines when the problem contains smaller copies of itself.
What must a recursive routine have to terminate? Select جميعها that apply.
الصعوبة 2/5 · 140 عملة + مكافأة صغيرة عند الإنجاز الأول اليوم
A base case alone is not enough: if the input never shrinks, the base case is never reached and frames pile up until the stack overflows.
مثال محلول: تتبع التراجع
- تتبع
Factorial(4). - التراكم:
Factorial(4)يحتاج4 * Factorial(3)، الذي يحتاج3 * Factorial(2)، الذي يحتاج2 * Factorial(1). لم يتم الضرب بعد؛ كل استدعاء ينتظر. - الحالة الأساسية:
Factorial(1)يعيد 1 دون استدعاء أي شيء. - التفكيك:
2 * 1 = 2يُعاد، ثم3 * 2 = 6، ثم4 * 6 = 24. - أشر إلى الاتجاهين. التتبع الذي يتجه للأسفل فقط أو يعود فقط يفقد نصف الدرجات.
Recursion unwinds from the leaves up
Step through fib(4) in the order the calls actually finish: the leaves (base cases) resolve first, then each parent combines its children. Notice fib(2) is computed twice — that repeated work is why naive recursion is slow.
What does Factorial(4) return?
الصعوبة 2/5 · 140 عملة + مكافأة صغيرة عند الإنجاز الأول اليوم
4 × 3 × 2 × 1 = 24.
ما تفعله الآلة
- كل استدعاء يحتاج إلى نسخة خاصة به من المعاملات والمتغيرات المحلية، لأن
Factorial(3)وFactorial(2)استدعاءات مختلفة بقيمnمختلفة. - تعيش تلك النسخ في إطار مكدس على مكدس الاستدعاء: إطار واحد لكل استدعاء جاري، يحتوي على المعاملات، والمتغيرات المحلية، وعنوان الإرجاع.
- يُدفع الإطار على المكدس في كل استدعاء ويُحذف عند العود. ولهذا تعود القيم بترتيب معكوس لترتيب الاستدعاءات: لأن مكدس الاستدعاءات هو مكدس، تماماً كـ ADT من الموضوع 10.
Put the events of evaluating Factorial(4) in order.
الصعوبة 3/5 · 200 عملة + مكافأة صغيرة عند الإنجاز الأول اليوم
Nothing is multiplied on the way down; every call waits. The multiplications all happen as the stack unwinds.
ما قد يخطئ
- لا حالة أساسية، أو حالة أساسية لا يتم الوصول إليها أبداً: لا يتوقف التراجع، تتراكم الإطارات، وينتهي مكدس الاستدعاء بالذاكرة. هذا هو تجاوز المكدس.
- التراجع العميق: حتى التراجع الصحيح بمليون مستوى يحتاج مليون إطار، لذا يمكن أن يستنفذ الذاكرة حيث لا تستخدم الحلقة شيئاً.
- العمل المكرر: فيبوناتشي التراجعي البسيط يعيد حساب نفس القيم عدداً أسياً من المرات. أصلحه بحلقة، أو بـ التخزين المؤقت، تخزين كل نتيجة أول مرة يتم حسابها.
Match each recursion term to what it means.
الصعوبة 2/5 · 140 عملة + مكافأة صغيرة عند الإنجاز الأول اليوم
A recursion needs a base case to stop and a recursive case to shrink the problem; each call adds a stack frame.
A stack frame for a function call holds:
الصعوبة 1/5 · 100 عملة + مكافأة صغيرة عند الإنجاز الأول اليوم
Each frame stores that call's parameters, locals and where to resume — so calls don't trample each other.
Each call in progress keeps its parameters and locals in its own ____ on the call stack.
الصعوبة 1/5 · 100 عملة + مكافأة صغيرة عند الإنجاز الأول اليوم
Pushed on call, popped on return. That is why values come back in the reverse of the order the calls were made.
التراجع أم التكرار
- التراجع مناسب للمشاكل متشابهة ذاتياً، حيث تحتوي المشكلة على نسخة أصغر منها: تجوال الشجرة، تقسيم وسيطر مثل البحث الثنائي ودمج الترتيب، وسلسلة السلف أعلاه.
- التكرار مناسب لكل شيء آخر، ولا يستخدم ذاكرة إضافية للتكرار.
- يمكن كتابة أي شيء متكرر بشكل تكراري والعكس صحيح أيضاً. يعتمد الاختيار على أيهما يعبر عن المشكلة بوضوح، مقارنة بتكلفة الذاكرة التي يسببها المكدس.
A recursive routine crashes with a stack overflow. Which explanation is correct?
الصعوبة 1/5 · 100 عملة + مكافأة صغيرة عند الإنجاز الأول اليوم
Stack overflow is about frames, not arithmetic. A number too large for its register is an arithmetic overflow, a different thing entirely.
مثال محلول: ذكر المخاطر
- طالب يكتب روتيناً تراجعيًا وينهار بتجاوز المكدس. اذكر سببين محتملين.
- لا توجد حالة أساسية، أو لا يمكن الوصول للحالة الأساسية لأن المدخل لا يصغر في كل استدعاء، فتستمر الاستدعاءات إلى ما لا نهاية وتتراكم الإطارات.
- التراجع صحيح لكن عميق جداً: كل واحد من الاستدعاءات الكثيرة يحتفظ بإطاره الخاص، وينتهي مكدس الاستدعاء بالذاكرة قبل الوصول للحالة الأساسية.
- كلا السببين يتعلقان بتراكم الإطارات. قل ما يتراكم ولماذا لا يتوقف.
علامات ضائعة
- التراجع يحتاج كلا الحالة الأساسية ومدخل يصغر. تسمية الحالة الأساسية فقط هي نصف الشرط.
- في التتبع، أظهر الاستدعاءات تتراكم للقيمة تتفكك. الاتجاهان يحملان درجات.
- لكل استدعاء معاملات ومتغيرات خاصة به، في إطار مكدس خاص به. وهذا هو سبب تكلفة التراجع للذاكرة التي لا يكلفها التكرار.
- تجاوز المكدس هو نفاد ذاكرة المكدس من كثرة الإطارات، وليس تجاوز حسابي.
لقد فهمت الأمر
- يتطلب الروتين المتكرر حالة أساسية تُحل مباشرة وحالة متكررة تستدعي نفسها بمدخل أصغر.
- تتبعه في الاتجاهين: استدعاءات تتراكم نحو الحالة الأساسية، ثم قيم تتفكك عائدة
- لكل استدعاء إطار مكدس خاص على مكدس الاستدعاء، يُدفع عند الاستدعاء ويُحذف عند الإرجاع، وهو السبب في أن التراجع يكلف الذاكرة
- مخاطر: عدم وجود حالة أساسية يمكن الوصول إليها يؤدي إلى استدعاء ذاتي لا نهائي وتفريغ المكدس، والاستدعاءات العميقة تستنفذ الذاكرة، والعمل المكرر يتطلب حلقة تكرار أو الترميز التذكاري