العودية
| 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əʊ/ | Overflow المكدس |
| 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
- الحالة الأساسية هي نسخة من المشكلة صغيرة بما يكفي للإجابة عليها مباشرة، دون استدعاء إضافي. وهي ما يوقف التراجع.
- الحالة التراجعية تستدعي الدالة مرة أخرى بـ مدخل أصغر، متجهة نحو الحالة الأساسية.
- كلاهما مطلوب. التراجع بدون حالة أساسية لن يتوقف أبداً؛ وأحد مدخلاته لا ينكمش لن يصل أبداً للحالة الأساسية.
يجب أن تحتوي كل خوارزمية عودية على حالة أساسية لأن:
الحالة الأساسية هي الشرط الذي ينهي سلسلة المكالمات؛ بدونها تستمر العودية إلى ما لا نهاية.
العودة هي خيار طبيعي للمشاكل شبيهة بالذات (الأشجار، تقسيم والحكم)، لكن كل مكالمة تضيف إطار مكدس — لذا بدون حالة أساسية تمتلئ المكدسة.
حلقة عد بسيطة أنظف للتكرار العادي؛ تلمع العودية عندما يحتوي المشكلة نسخ أصغر من نفسها.
ما الذي يجب أن تتمتع به روتين عودي لينتهي؟ حدد جميع ما ينطبق.
حالة أساسية وحدها ليست كافية: إذا لم يصغر المدخل أبداً، فلن تُ reachable الحالة الأساسية وتتراكم الإطارات حتى تمتلئ المكدسة.
مثال محلول: تتبع التراجع
- تتبع
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. - أشر إلى الاتجاهين. التتبع الذي يتجه للأسفل فقط أو يعود فقط يفقد نصف الدرجات.
تتراجع العودية من الأوراق صعوداً
مرر عبر fib(4) بالترتيب الذي تنتهي فيه المكالمات فعليًا: تتحلل الأوراق (الحالات الأساسية) أولاً، ثم يجمع كل أب أبنائه. لاحظ أن fib(2) يتم حسابه مرتين — هذا العمل المكرر هو السبب في بطء العودية البدائية.
ماذا يعيد Factorial(4)؟
4 × 3 × 2 × 1 = 24.
ما تفعله الآلة
- كل استدعاء يحتاج إلى نسخة خاصة به من المعاملات والمتغيرات المحلية، لأن
Factorial(3)وFactorial(2)استدعاءات مختلفة بقيمnمختلفة. - تعيش تلك النسخ في إطار مكدس على مكدس الاستدعاء: إطار واحد لكل استدعاء جاري، يحتوي على المعاملات، والمتغيرات المحلية، وعنوان الإرجاع.
- يُدفع الإطار عند كل استدعاء ويُحذف عند الإرجاع. ولهذا تعود القيم بالعكس相对于 order تم استدعاؤها: مكدس الاستدعاء هو مكدس، تماماً ADT من الموضوع 10.
ضع أحداث تقييم Factorial(4) بالترتيب.
لا يوجد ضرب أثناء النزول؛ كل مكالمة تنتظر. الضربات جميعها تحدث أثناء تراجع المكدسة.
ما قد يخطئ
- لا حالة أساسية، أو حالة أساسية لا يتم الوصول إليها أبداً: لا يتوقف التراجع، تتراكم الإطارات، وينتهي مكدس الاستدعاء بالذاكرة. هذا هو تجاوز المكدس.
- التراجع العميق: حتى التراجع الصحيح بمليون مستوى يحتاج مليون إطار، لذا يمكن أن يستنفذ الذاكرة حيث لا تستخدم الحلقة شيئاً.
- العمل المكرر: فيبوناتشي التراجعي البسيط يعيد حساب نفس القيم عدداً أسياً من المرات. أصلحه بحلقة، أو بـ التخزين المؤقت، تخزين كل نتيجة أول مرة يتم حسابها.
طابق كل مصطلح عودي بما يعني.
تحتاج العودية إلى حالة أساسية للتوقف وحالة عودية لتقليص المشكلة؛ كل مكالمة تضيف إطار مكدس.
إطار مكدسة لمكالمة دالة يحتفظ بـ:
يخزن كل إطار معلمات تلك المكالمة، والمتغيرات المحلية، ومكان الاستئناف — بحيث لا تتداخل المكالمات مع بعضها البعض.
تحتفظ كل مكالمة جارية بمعلماتها ومتغيراتها المحلية في ____ خاص بها على كومة المكالمات.
تُضاف عند المكالمة وتُزاح عند الإرجاع. ولهذا تعود القيم بالعكس عن ترتيب إجراء المكالمات.
التراجع أم التكرار
- التراجع مناسب للمشاكل متشابهة ذاتياً، حيث تحتوي المشكلة على نسخة أصغر منها: تجوال الشجرة، تقسيم وسيطر مثل البحث الثنائي ودمج الترتيب، وسلسلة السلف أعلاه.
- التكرار مناسب لكل شيء آخر، ولا يستخدم ذاكرة إضافية للتكرار.
- أيthing تراجعي يمكن كتابتها تكرارياً والعكس صحيح أيضاً. الاختيار يتعلق بأي منهما يعبر عن المشكلة بوضوح، مقارنة بالذاكرة التي تكلفها المكدس.
يتوقف البرنامج المتكرر (المتداخل) بسبب تجاوز سعة الكومة. أي explanation صحيح؟
تجاوز الكومة يتعلق بالأطر وليس بالحساب. العدد الكبير الذي يتسع له السجل هو تجاوز حسابي، وهو أمر مختلف تماماً.
مثال محلول: ذكر المخاطر
- طالب يكتب روتيناً تراجعيًا وينهار بتجاوز المكدس. اذكر سببين محتملين.
- لا توجد حالة أساسية، أو لا يمكن الوصول للحالة الأساسية لأن المدخل لا يصغر في كل استدعاء، فتستمر الاستدعاءات إلى ما لا نهاية وتتراكم الإطارات.
- التراجع صحيح لكن عميق جداً: كل واحد من الاستدعاءات الكثيرة يحتفظ بإطاره الخاص، وينتهي مكدس الاستدعاء بالذاكرة قبل الوصول للحالة الأساسية.
- كلا السببين يتعلقان بتراكم الإطارات. قل ما يتراكم ولماذا لا يتوقف.
علامات ضائعة
- التراجع يحتاج كلا الحالة الأساسية ومدخل يصغر. تسمية الحالة الأساسية فقط هي نصف الشرط.
- في التتبع، أظهر الاستدعاءات تتراكم للقيمة تتفكك. الاتجاهان يحملان درجات.
- لكل استدعاء معاملات ومتغيرات خاصة به، في إطار مكدس خاص به. وهذا هو سبب تكلفة التراجع للذاكرة التي لا يكلفها التكرار.
- تجاوز المكدس هو نفاد ذاكرة المكدس من كثرة الإطارات، وليس تجاوز حسابي.
لقد فهمت الأمر
- الرoutine التراجعي يحتاج حالة أساسية تُحل مباشرة وحالة تراجعية تستدعي نفسها بـ مدخل أصغر
- تتبعه في الاتجاهين: استدعاءات تتراكم نحو الحالة الأساسية، ثم قيم تتفكك عائدة
- لكل استدعاء إطار مكدس خاص على مكدس الاستدعاء، يُدفع عند الاستدعاء ويُحذف عند الإرجاع، وهو السبب في أن التراجع يكلف الذاكرة
- مخاطر: عدم وجود حالة أساسية يمكن الوصول إليها يؤدي إلى استدعاء ذاتي لا نهائي وتفريغ المكدس، والاستدعاءات العميقة تستنفذ الذاكرة، والعمل المكرر يتطلب حلقة تكرار أو الترميز التذكاري