الاستدعاء الذاتي (علوم الحاسوب)

تحدد حالة الأساس قيم الإدخال التي يمكن للدالة عندها تقديم نتيجة مباشرة، دون الحاجة إلى أي تكرار إضافي. ^{[ 11 ]} عادةً ما تكون هذه أبسط أو أصغر المدخلات الممكنة (والتي يمكن حلها بسهولة)، مما يسمح بإنهاء الحساب. حالات الأساس ضرورية لأنها تمنع التكرار اللانهائي. بعبارة أخرى، تحدد حالة توقف تُنهي التكرار.

مثال على ذلك حساب مضروب العدد الصحيح n، وهو حاصل ضرب جميع الأعداد الصحيحة من 0 إلى n. في هذه المسألة، يُعدّ التعريف 0! = 1 حالة أساسية. بدونه، قد يستمر الاستدعاء الذاتي إلى ما لا نهاية، مما يؤدي إلى عدم توقف البرنامج أو حتى أخطاء تجاوز سعة المكدس في التطبيقات العملية.

يُعدّ تصميم حالة أساسية صحيحة أمرًا بالغ الأهمية لأسباب نظرية وعملية على حد سواء. فبعض المسائل لها حالة أساسية طبيعية (مثلًا، القائمة الفارغة هي حالة أساسية في بعض دوال معالجة القوائم المتكررة)، بينما تتطلب مسائل أخرى مُعاملًا إضافيًا لتوفير معيار للتوقف (مثلًا، استخدام عداد العمق في اجتياز الشجرة المتكرر ).

في البرمجة الحاسوبية التكرارية ، قد يؤدي إغفال حالة التوقف أو تعريفها بشكل خاطئ إلى تكرار لا نهائي غير مقصود. وقد أظهرت دراسة أن العديد من الطلاب يجدون صعوبة في تحديد حالات التوقف المناسبة. ^{[ 11 ]}

تصف الحالة التكرارية كيفية تقسيم المشكلة إلى مشاكل فرعية أصغر من نفس الشكل. ^{[ 11 ]} تُحوّل كل خطوة تكرارية المدخلات بحيث تقترب من حالة أساسية، مما يضمن التقدم نحو الإنهاء. إذا فشلت خطوة الاختزال في التقدم نحو حالة أساسية، فقد يعلق البرنامج في حلقة لا نهائية .

في مثال المضروب ، تُعرَّف الحالة التكرارية على النحو التالي: ${\displaystyle n!=n\cdot (n-1)!\,,\forall n>0.}$ هنا، كل استدعاء للدالة يقلل من المدخلات${\displaystyle n}$بـ 1. وبالتالي، يضمن ذلك أن يصل التكرار في النهاية إلى الحالة الأساسية لـ${\displaystyle n=0}$.

تُشابه الحالة التكرارية خطوة الاستقراء في البرهان بالاستقراء : فهي تفترض أن الدالة تعمل مع حالة أصغر، ثم تُعمم هذا الافتراض على المُدخل الحالي. وبالتالي، فإن التعريفات والخوارزميات التكرارية تُوازي الحجج الاستقرائية في الرياضيات ، وغالبًا ما تعتمد صحتها على تقنيات استدلال مماثلة.

توجد العديد من التطبيقات العملية للتكرار التي تتبع بنية الحالة الأساسية والحالة التكرارية. وتُستخدم هذه التطبيقات على نطاق واسع لحل المشكلات المعقدة في علوم الحاسوب.

• تستخدم عمليات اجتياز الأشجار ، مثل البحث العميق أولاً ، حالة تكرارية لمعالجة كل شجرة فرعية (الحالة التكرارية)، وتتوقف في النهاية عند العقد الورقية (الحالة الأساسية). ^{[ 12 ]}
• فرز الدمج هو خوارزمية فرز تقوم بفرز ودمج المصفوفات الفرعية المقسمة بشكل متكرر (الحالة المتكررة) حتى تتكون كل مصفوفة فرعية من عنصر واحد (الحالة الأساسية). ^{[ 13 ]}
• يتم تعريف متتالية فيبوناتشي عن طريق جمع الرقمين السابقين في المتتالية (الحالة التكرارية)، والتوقف عندما n = 0 أو n = 1 (الحالات الأساسية).
• يقوم البحث الثنائي بتقسيم فترة البحث إلى نصفين بشكل متكرر (الحالة المتكررة) حتى يتم العثور على الهدف أو تصبح الفترة فارغة (الحالات الأساسية).

تعريف البيانات الاستقرائي المتكرر هو تعريف يحدد كيفية إنشاء نسخ من البيانات. على سبيل المثال، يمكن تعريف القوائم المرتبطة استقرائيًا (هنا، باستخدام صيغة هاسكل ):

data ListOfStrings = EmptyList | Cons String ListOfStrings

يُحدد الكود أعلاه قائمة من السلاسل النصية إما فارغة، أو بنية تحتوي على سلسلة نصية وقائمة من السلاسل النصية. يسمح المرجع الذاتي في التعريف بإنشاء قوائم تحتوي على أي عدد (محدود) من السلاسل النصية.

مثال آخر على التعريف الاستقرائي هو الأعداد الطبيعية (أو الأعداد الصحيحة الموجبة ):

العدد الطبيعي إما 1 أو n+1، حيث n هو عدد طبيعي.

وبالمثل ، تُستخدم التعريفات التكرارية غالبًا لنمذجة بنية التعبيرات والعبارات في لغات البرمجة. غالبًا ما يُعبّر مصممو اللغات عن القواعد النحوية بصيغة مثل صيغة باكوس-ناور ؛ إليك مثال على هذه القواعد النحوية، للغة بسيطة من التعبيرات الحسابية التي تتضمن الضرب والجمع:

<expr> :: = <number> | ( <expr> * <expr> )​​​​​​ | ( < تعبير > + < تعبير > ) 

ينص هذا على أن التعبير إما أن يكون عددًا، أو حاصل ضرب تعبيرين، أو مجموع تعبيرين. وباستخدام الإشارة المتكررة إلى التعبيرات في السطرين الثاني والثالث، تسمح القواعد النحوية بتعبيرات حسابية معقدة كيفما كانت (5 * ((3 * 6) + 8))، مثل التعبير الذي يحتوي على أكثر من عملية ضرب أو جمع في التعبير الواحد.

تعريف البيانات الاستقرائي هو تعريف يحدد العمليات التي يمكن إجراؤها على جزء من البيانات؛ وعادةً ما تُستخدم التعريفات الاستقرائية المرجعية الذاتية لهياكل البيانات ذات الحجم اللانهائي.

قد يبدو التعريف الاستقرائي للتيارات اللانهائية من السلاسل، المقدم بشكل غير رسمي، على النحو التالي:

سلسلة السلاسل النصية هي كائن s بحيث: الرأس (الرؤوس) عبارة عن سلسلة، و tail(s) عبارة عن سلسلة من السلاسل النصية.

هذا يشبه إلى حد كبير التعريف الاستقرائي لقوائم السلاسل النصية؛ والفرق هو أن هذا التعريف يحدد كيفية الوصول إلى محتويات بنية البيانات - أي عبر وظائف الوصولhead - وما tailقد تكون عليه تلك المحتويات، بينما يحدد التعريف الاستقرائي كيفية إنشاء البنية وما يمكن إنشاؤها منه.

التكرار المشترك مرتبط بالاستقراء المشترك، ويمكن استخدامه لحساب حالات محددة من كائنات (قد تكون) لانهائية. كتقنية برمجة، يُستخدم غالبًا في سياق لغات البرمجة الكسولة ، وقد يكون مفضلًا على التكرار عندما يكون حجم أو دقة مخرجات البرنامج غير معروفة. في مثل هذه الحالات، يتطلب البرنامج تعريفًا لنتيجة لانهائية الحجم (أو لانهائية الدقة)، وآلية لأخذ جزء محدود من تلك النتيجة. تُعد مشكلة حساب أول n عدد أولي مثالًا على مشكلة يمكن حلها باستخدام برنامج تكرار مشترك (على سبيل المثال هنا ).

يُعرف الاستدعاء الذاتي الذي يحتوي على مرجع ذاتي واحد فقط باسمالاستدعاء الذاتي الأحادي ، بينما يُعرف الاستدعاء الذاتي الذي يحتوي على مراجع ذاتية متعددة باسمالاستدعاء الذاتي المتعدد . تشمل الأمثلة القياسية للاستدعاء الذاتي الفردي اجتياز القائمة، كما هو الحال في البحث الخطي، أو حساب دالة المضروب، بينما تشمل الأمثلة القياسية للاستدعاء الذاتي المتعدداجتياز الشجرة، كما هو الحال في البحث العميق أولاً.

غالبًا ما يكون الاستدعاء الذاتي الأحادي أكثر كفاءة من الاستدعاء الذاتي المتعدد، ويمكن استبداله عمومًا بعملية حسابية تكرارية، تعمل في وقت خطي وتتطلب مساحة ثابتة. في المقابل، قد يتطلب الاستدعاء الذاتي المتعدد وقتًا ومساحة أسيين، وهو في جوهره استدعاء ذاتي، ولا يمكن استبداله بالتكرار دون استخدام مكدس صريح.

يمكن أحيانًا تحويل الاستدعاء المتعدد إلى استدعاء أحادي (وإذا رغبنا، إلى تكرار). على سبيل المثال، بينما يتطلب حساب متتالية فيبوناتشي في ظاهره تكرارًا متعددًا، حيث تتطلب كل قيمة قيمتين سابقتين، يمكن حسابها باستخدام استدعاء أحادي بتمرير قيمتين متتاليتين كمعاملات.

تُظهر معظم الأمثلة الأساسية للاستدعاء الذاتي، ومعظم الأمثلة المعروضة هنا،الاستدعاء المباشر هو استدعاء دالة لنفسها. أما الاستدعاء غير المباشر فيحدث عندما تُستدعى دالةٌ ما ليس من قِبلها، بل من قِبل دالة أخرى استدعتها (سواءً بشكل مباشر أو غير مباشر). على سبيل المثال، إذااستدعت الدالة f الدالة f، فهذا استدعاء مباشر، أما إذااستدعت f الدالة g التي تستدعي f، فهذا استدعاء غير مباشر للدالة f. ويمكن أن تتكون سلاسل الاستدعاء من ثلاث دوال أو أكثر؛ على سبيل المثال، تستدعي الدالة 1 الدالة 2، ثم تستدعي الدالة 2 الدالة 3، وهكذا تستدعي الدالة 3 الدالة 1 مرة أخرى.

يُطلق على الاستدعاء غير المباشر أيضًا اسم الاستدعاء المتبادل ، وهو مصطلح أكثر تناسقًا، مع أن هذا مجرد اختلاف في التركيز، وليس اختلافًا في المفهوم. بمعنى آخر، إذا استدعت الدالة f الدالة g ، ثم استدعت g الدالة f، التي بدورها استدعت g مرة أخرى، فمن وجهة نظر f وحدها، تكون f مستدعاة بشكل غير مباشر، بينما من وجهة نظر g وحدها، تكون g مستدعاة بشكل غير مباشر، أما من وجهة نظر كلتيهما، فإن f و g تستدعيان بعضهما البعض بشكل متبادل. وبالمثل، يمكن تسمية مجموعة من ثلاث دوال أو أكثر تستدعي بعضها البعض بمجموعة من الدوال المستدعاة بشكل متبادل.

عادةً ما يتم تنفيذ الاستدعاء الذاتي عن طريق استدعاء دالة بالاسم صراحةً. ومع ذلك، يمكن أيضًا تنفيذ الاستدعاء الذاتي عن طريق استدعاء دالة ضمنيًا بناءً على السياق الحالي، وهو أمر مفيد بشكل خاص للدوال المجهولة ، ويُعرف باسم الاستدعاء الذاتي المجهول .

يصنف بعض المؤلفين الاستدعاء الذاتي إلى نوعين: "بنيوي" و"توليدي". ويرتبط هذا التمييز بمصدر البيانات التي يحصل عليها الإجراء الاستدعائي، وكيفية معالجته لتلك البيانات.

تقوم الدوال التي تستخدم البيانات المهيكلة عادةً بتحليل وسائطها إلى مكوناتها الهيكلية المباشرة، ثم تعالج هذه المكونات. إذا كان أحد المكونات المباشرة ينتمي إلى نفس فئة البيانات التي ينتمي إليها المُدخل، فإن الدالة تكون تكرارية. ولهذا السبب، نشير إلى هذه الدوال باسم الدوال التكرارية (هيكليًا).

وبالتالي، فإن السمة المميزة للدالة التكرارية البنيوية هي أن وسيط كل استدعاء تكراري هو محتوى حقل من المدخلات الأصلية. يشمل التكرار البنيوي جميع عمليات اجتياز الأشجار تقريبًا، بما في ذلك معالجة XML، وإنشاء الأشجار الثنائية والبحث فيها، وما إلى ذلك. وبالنظر إلى البنية الجبرية للأعداد الطبيعية (أي أن العدد الطبيعي إما أن يكون صفرًا أو العدد التالي لعدد طبيعي آخر)، يمكن اعتبار دوال مثل دالة المضروب تكرارًا بنيويًا أيضًا.

الاستدعاء التوليدي هو البديل:

تُنشئ العديد من الخوارزميات التكرارية المعروفة بيانات جديدة تمامًا من البيانات المُعطاة، ثم تُكرر العملية عليها. ويُشير كتاب " كيفية تصميم البرامج " ( HtDP ) إلى هذا النوع من الخوارزميات باسم التكرار التوليدي. ومن أمثلة التكرار التوليدي: إيجاد القاسم المشترك الأكبر ، والفرز السريع ، والبحث الثنائي ، وفرز الدمج ، وطريقة نيوتن ، والكسور الهندسية ، والتكامل التكيفي .

هذا التمييز مهم في إثبات انتهاء الدالة.

• يمكن بسهولة إثبات أن جميع الدوال المتكررة هيكليًا على هياكل البيانات المحدودة ( المحددة استقرائيًا ) تنتهي، من خلال الاستقراء الهيكلي : بشكل بديهي، تتلقى كل استدعاء متكرر جزءًا أصغر من بيانات الإدخال، حتى يتم الوصول إلى حالة أساسية.
• على النقيض من ذلك، لا تُدخل الدوال التوليدية التكرارية بالضرورة مدخلات أصغر إلى استدعاءاتها التكرارية، لذا فإن إثبات توقفها ليس بالضرورة بهذه البساطة، ويتطلب تجنب الحلقات اللانهائية عناية أكبر. غالبًا ما يمكن تفسير هذه الدوال التوليدية التكرارية على أنها دوال تكرارية مشتركة - حيث تُولّد كل خطوة بيانات جديدة، مثل التقريب المتتالي في طريقة نيوتن - ويتطلب إنهاء هذا التكرار المشترك أن تُحقق البيانات في النهاية شرطًا ما، وهو أمر غير مضمون بالضرورة.
• فيما يتعلق بمتغيرات الحلقة ، فإن التكرار الهيكلي هو عندما يكون هناك متغير حلقة واضح، وهو الحجم أو التعقيد، والذي يبدأ محدودًا ويتناقص في كل خطوة تكرارية.
• وعلى النقيض من ذلك، فإن التكرار التوليدي هو عندما لا يكون هناك متغير حلقة واضح، ويعتمد الإنهاء على دالة، مثل "خطأ التقريب" الذي لا ينخفض ​​بالضرورة إلى الصفر، وبالتالي فإن الإنهاء غير مضمون بدون مزيد من التحليل.

الدالة المغلفة هي دالة يتم استدعاؤها مباشرة ولكنها لا تستدعي نفسها بشكل متكرر، بل تستدعي دالة مساعدة منفصلة تقوم فعليًا بالتكرار.

يمكن استخدام الدوال المُغلِّفة للتحقق من صحة المعاملات (بحيث يمكن للدالة التكرارية تجاوزها)، وإجراء عمليات التهيئة (تخصيص الذاكرة، وتهيئة المتغيرات)، لا سيما للمتغيرات المساعدة مثل "مستوى التكرار" أو العمليات الحسابية الجزئية للتخزين المؤقت ، ومعالجة الاستثناءات والأخطاء. في اللغات التي تدعم الدوال المتداخلة ، يمكن تضمين الدالة المساعدة داخل الدالة المُغلِّفة واستخدام نطاق مشترك. في حال عدم وجود دوال متداخلة، تكون الدوال المساعدة دالة منفصلة، ​​ويفضل أن تكون خاصة (لأنها لا تُستدعى مباشرةً)، وتُشارك المعلومات مع الدالة المُغلِّفة باستخدام تمرير المرجع .

دالة ` fac1` تأخذ عددًا صحيحًا ` n` كمدخل ، وتعيد ` 1` إذا كان ` n` أقل من أو يساوي صفرًا . وإلا ، فإنها تعيد `fac1 ( n - 1 ) * n` .

intfac2(intn){// assert(n >= 2);if(n==2){return2;}else{returnfac2(n-1)*n;}}intfac2wrapper(intn){if(n<=1){return1;}else{returnfac2(n);}}

Short-circuiting the base case, also known as arm's-length recursion, consists of checking the base case before making a recursive call – i.e., checking if the next call will be the base case, instead of calling and then checking for the base case. Short-circuiting is particularly done for efficiency reasons, to avoid the overhead of a function call that immediately returns. Note that since the base case has already been checked for (immediately before the recursive step), it does not need to be checked for separately, but one does need to use a wrapper function for the case when the overall recursion starts with the base case itself. For example, in the factorial function, properly the base case is 0! = 1, while immediately returning 1 for 1! is a short circuit, and may miss 0; this can be mitigated by a wrapper function. The box shows C code to shortcut factorial cases 0 and 1.

Short-circuiting is primarily a concern when many base cases are encountered, such as Null pointers in a tree, which can be linear in the number of function calls, hence significant savings for O(n) algorithms; this is illustrated below for a depth-first search. Short-circuiting on a tree corresponds to considering a leaf (non-empty node with no children) as the base case, rather than considering an empty node as the base case. If there is only a single base case, such as in computing the factorial, short-circuiting provides only O(1) savings.

من الناحية النظرية، يمكن اعتبار الاختصار إما ذا حالة أساسية وخطوة تكرارية متماثلتين، حيث يتم التحقق من الحالة الأساسية فقط قبل التكرار، أو ذا حالة أساسية مختلفة (خطوة واحدة أبعد عن الحالة الأساسية القياسية) وخطوة تكرارية أكثر تعقيدًا، وهي "التحقق من الصحة ثم التكرار"، كما في اعتبار العقد الورقية بدلاً من العقد الفارغة حالات أساسية في الشجرة. ولأن الاختصار يتميز بتدفق أكثر تعقيدًا، مقارنةً بالفصل الواضح بين الحالة الأساسية والخطوة التكرارية في التكرار القياسي، فإنه يُعتبر غالبًا أسلوبًا برمجيًا رديئًا، لا سيما في الأوساط الأكاديمية. ^{[ 16 ]}

bool tree_contains ( struct BinaryTree * node , int i ) { if ( ! node ) { return false ; // الحالة الأساسية } else if ( node- > data == i ) { return true ; } else { return tree_contains ( node- > left , i ) || tree_contains ( node- > right , i ); } }

#include <assert.h>// دالة تغليف للتعامل مع الشجرة الفارغة bool tree_contains ( struct BinaryTree * node , int i ) { if ( ! node ) { return false ; // شجرة فارغة } else { return tree_contains_aux ( node , i ); // استدعاء الدالة المساعدة } }// يفترض أن node != NULL bool tree_contains_aux ( struct BinaryTree * node , int i ) { assert ( node ); if ( node -> data == i ) { return true ; // تم العثور على العنصر } else { // استدعاء الدالة بشكل متكرر return ( node -> left && tree_contains_aux ( node -> left , i )) || ( node -> right && tree_contains_aux ( node -> right , i )); } }

غالبًا ما تكون الخوارزميات التكرارية غير فعّالة مع البيانات الصغيرة، نظرًا لتكلفة استدعاءات الدوال المتكررة وعمليات الإرجاع. لهذا السبب، تبدأ التطبيقات الفعّالة للخوارزميات التكرارية عادةً بالخوارزمية التكرارية نفسها، ثم تنتقل إلى خوارزمية أخرى عندما تصبح البيانات صغيرة. ومن الأمثلة المهمة على ذلك فرز الدمج ، الذي يُنفّذ غالبًا بالتحول إلى فرز الإدراج غير التكراري عندما تكون البيانات صغيرة بما يكفي، كما في فرز الدمج المُجزّأ . ويمكن تحسين الخوارزميات التكرارية الهجينة بشكل أكبر، كما في Timsort ، المشتقة من فرز دمج/إدراج هجين.

تتيح معظم لغات البرمجة المستخدمة اليوم تحديد الدوال والإجراءات التكرارية بشكل مباشر. عند استدعاء دالة من هذا النوع، يتتبع بيئة تشغيل البرنامج مختلف حالات الدالة (غالبًا باستخدام مكدس الاستدعاءات ، مع إمكانية استخدام طرق أخرى). يمكن تحويل أي دالة تكرارية إلى دالة تكرارية عن طريق استبدال الاستدعاءات التكرارية ببنى تحكم تكرارية ومحاكاة مكدس الاستدعاءات باستخدام مكدس يديره البرنامج بشكل صريح. ^{[ 17 ] [ 18 ]}

على النقيض، يمكن التعبير عن جميع الدوال والإجراءات التكرارية التي يمكن تقييمها بواسطة الحاسوب (انظر اكتمال تورينج ) باستخدام الدوال التكرارية؛ حيث تُعاد كتابة بنيات التحكم التكرارية، مثل حلقات while و for، بشكل روتيني في شكل تكراري في اللغات الوظيفية . ^{[ 19 ] [ 20 ]} مع ذلك، يعتمد هذا التعديل عمليًا على حذف استدعاءات الذيل ، وهي ميزة غير متوفرة في جميع اللغات. تُعد لغات C و Java و Python من أبرز اللغات الشائعة التي قد تتسبب فيها جميع استدعاءات الدوال، بما في ذلك استدعاءات الذيل ، في تخصيص مساحة في مكدس الاستدعاءات، وهو ما لا يحدث عند استخدام بنيات الحلقات؛ في هذه اللغات، قد يتجاوز برنامج تكراري يعمل، تمت إعادة كتابته بشكل تكراري، سعة مكدس الاستدعاءات، على الرغم من أن حذف استدعاءات الذيل قد لا يكون ميزة مشمولة في مواصفات اللغة، وقد تختلف تطبيقات اللغة نفسها في قدرات حذف استدعاءات الذيل.

في اللغات (مثل C و Java ) التي تفضل بنيات التكرار الحلقي، عادة ما تكون هناك تكلفة كبيرة من حيث الوقت والمساحة مرتبطة بالبرامج المتكررة، وذلك بسبب الحمل الزائد المطلوب لإدارة المكدس والبطء النسبي لاستدعاءات الدوال؛ في اللغات الوظيفية ، عادة ما يكون استدعاء الدالة (وخاصة استدعاء الذيل ) عملية سريعة جدًا، وعادة ما يكون الفرق أقل وضوحًا.

كمثال عملي، يعتمد الفرق في الأداء بين التنفيذ التكراري والتنفيذ الاستدعائي لمثال "المضروب" المذكور أعلاه بشكل كبير على المُصرّف المُستخدم. في اللغات التي تُفضّل استخدام حلقات التكرار، قد يكون الإصدار الاستدعائي أسرع بعدة مراتب من الإصدار الاستدعائي. أما في اللغات الوظيفية، فقد يكون الفرق الزمني الإجمالي بين التنفيذين ضئيلاً؛ بل إن تكلفة ضرب الأعداد الأكبر أولاً بدلاً من الأعداد الأصغر (وهو ما يفعله الإصدار الاستدعائي المذكور هنا) قد تفوق أي وقت يتم توفيره باختيار الاستدعاء الاستدعائي.

في بعض لغات البرمجة، يكون الحد الأقصى لحجم مكدس الاستدعاءات أقل بكثير من المساحة المتاحة في الذاكرة الديناميكية ، وتميل الخوارزميات التكرارية إلى استهلاك مساحة أكبر في المكدس مقارنةً بالخوارزميات التكرارية. ونتيجةً لذلك، تفرض هذه اللغات أحيانًا حدًا أقصى لعمق الاستدعاء لتجنب تجاوز سعة المكدس ؛ وبايثون إحدى هذه اللغات. ^{[ 21 ]} لاحظ التحذير الوارد أدناه بشأن الحالة الخاصة للاستدعاء الذيل .

نظرًا لأن الخوارزميات التكرارية قد تتعرض لتجاوز سعة المكدس، فقد تكون عرضة للمدخلات غير الطبيعية أو الخبيثة . ^{[ 22 ]} تستهدف بعض البرامج الضارة مكدس استدعاءات البرنامج تحديدًا، وتستغل طبيعته التكرارية. ^{[ 23 ]} حتى في غياب البرامج الضارة، قد يكون تجاوز سعة المكدس الناتج عن التكرار غير المحدود قاتلًا للبرنامج، وقد لا تمنع آلية معالجة الاستثناءات إنهاء العملية المعنية . ^{[ 24 ]}

تُعدّ المسائل التكرارية المتعددة تكرارية بطبيعتها، نظرًا لحاجتها إلى تتبع الحالة السابقة. ومن الأمثلة على ذلك اجتياز الشجرة كما في البحث العميق أولًا ؛ فعلى الرغم من استخدام كلٍّ من الطرق التكرارية والتكرارية ^{[ 25 ]} ، إلا أنها تختلف عن اجتياز القائمة والبحث الخطي فيها، وهو طريقة تكرارية أحادية، وبالتالي فهي بطبيعتها تكرارية. ومن الأمثلة الأخرى خوارزميات فرق تسد مثل الفرز السريع ، ودوال مثل دالة أكرمان . يمكن تنفيذ جميع هذه الخوارزميات تكراريًا باستخدام مكدس صريح ، ولكن الجهد الذي يبذله المبرمج في إدارة المكدس، وتعقيد البرنامج الناتج، قد يفوقان أي مزايا للحل التكراري.

يمكن استبدال الخوارزميات التكرارية بنظيراتها غير التكرارية. ^{[ 26 ]} إحدى طرق استبدال الخوارزميات التكرارية هي محاكاتها باستخدام ذاكرة الكومة بدلاً من ذاكرة المكدس . ^{[ 27 ]} وثمة بديل آخر يتمثل في تطوير خوارزمية بديلة تعتمد كلياً على أساليب غير تكرارية، وهو ما قد يكون صعباً. ^{[ 28 ]} على سبيل المثال، كانت الخوارزميات التكرارية لمطابقة الأحرف البديلة ، مثل خوارزمية wildmat لريتش سالز ، [ ^{29 ] شائعة} في السابق. وقد طُوّرت خوارزميات غير تكرارية لنفس الغرض، مثل خوارزمية كراوس لمطابقة الأحرف البديلة ، لتجنب عيوب التكرار ^{[ 30 ]} ، ولم تتحسن إلا تدريجياً بالاعتماد على تقنيات مثل جمع الاختبارات وتحليل الأداء . ^{[ 31 ]}

#include <stdio.h>void recursiveFunction ( int num ) { if ( num < 4 ) { recursiveFunction ( num + 1 ); } printf ( "%d \n " , num ); }

إن ناتج الدالة 2 هو ناتج الدالة 1 مع تبديل الأسطر.

في حالة استدعاء دالة لنفسها مرة واحدة فقط، تُنفَّذ التعليمات الموضوعة قبل الاستدعاء التكراري مرة واحدة لكل تكرار قبل أي من التعليمات الموضوعة بعد الاستدعاء التكراري. وتُنفَّذ هذه التعليمات الأخيرة بشكل متكرر بعد الوصول إلى الحد الأقصى للتكرار.

لاحظ أيضًا أن ترتيب عبارات الطباعة معكوس، وهذا يرجع إلى طريقة تخزين الدوال والعبارات في مكدس الاستدعاءات .

من الأمثلة الكلاسيكية على الإجراءات المتكررة الدالة المستخدمة لحساب مضروب عدد طبيعي :

${\displaystyle \operatorname {fact} (n)={\begin{cases}1&{\mbox{if }}n=0\\n\cdot \operatorname {fact} (n-1)&{\mbox{if }}n>0\\\end{cases}}}$

دالة المضروب هي: المدخلات : عدد صحيح n بحيث يكون n ≥ 0، المخرجات : [ n × ( n - 1) × ( n - 2) × ... × 1] . 1. إذا كان n يساوي 0، تُرجع الدالة 1. 2. وإلا، فأرجع [ ن × مضروب( ن - 1)] نهاية المضروب

يمكن أيضًا كتابة الدالة كعلاقة تكرارية :

${\displaystyle b_{n}=nb_{n-1}}$

${\displaystyle b_{0}=1}$

يوضح هذا التقييم لعلاقة التكرار الحساب الذي سيتم إجراؤه عند تقييم الشفرة الزائفة أعلاه:

ب ٤ = ٤ × ب ٣ = ٤ × (٣ × ب ٢ ) = 4 × (3 × (2 × b 1 )) = 4 × (3 × (2 × (1 × b 0 ))) = 4 × (3 × (2 × (1 × 1))) = 4 × (3 × (2 × 1)) = 4 × (3 × 2) = 4 × 6 = 24

يمكن أيضًا وصف دالة المضروب هذه دون استخدام الاستدعاء الذاتي من خلال الاستفادة من بنيات التكرار النموذجية الموجودة في لغات البرمجة الإجرائية:

دالة المضروب هي: المدخلات : عدد صحيح n بحيث يكون n ≥ 0، المخرجات : [ n × ( n - 1) × ( n - 2) × ... × 1] . 1. أنشئ متغيرًا جديدًا باسم running_total بقيمة 1. 2. ابدأ الحلقة. 1. إذا كانت قيمة n تساوي 0، فاخرج من الحلقة 2. اضبط قيمة running_total على ( running_total × n ) 3. إنقاص قيمة n 4. تكرار الحلقة 3. إرجاع المجموع الكلي نهاية المضروب

الكود الإجرائي أعلاه يعادل هذا التعريف الرياضي باستخدام متغير تراكمي t :

${\displaystyle {\begin{aligned}\operatorname {fact} (n)&=\operatorname {fact_{acc}} (n,1)\\\operatorname {fact_{acc}} (n,t)&={\begin{cases}t&{\mbox{if }}n=0\\\operatorname {fact_{acc}} (n-1,nt)&{\mbox{if }}n>0\\\end{cases}}\end{aligned}}}$

يمكن ترجمة التعريف أعلاه بشكل مباشر إلى لغات البرمجة الوظيفية مثل Scheme ؛ وهذا مثال على التكرار الذي يتم تنفيذه بشكل متكرر.

يمكن كتابة خوارزمية إقليدس ، التي تحسب القاسم المشترك الأكبر لعددين صحيحين، بشكل متكرر.

تعريف الدالة :

${\displaystyle \gcd(x,y)={\begin{cases}x&{\mbox{if }}y=0\\\gcd(y,\operatorname {remainder} (x,y))&{\mbox{if }}y>0\\\end{cases}}}$

دالة gcd هي: المدخلات : عدد صحيح x ، عدد صحيح y بحيث x > 0 و y >= 0. 1. إذا كان y يساوي 0، فأرجع x. 2. وإلا، فأرجع [gcd( y , (باقي قسمة x على y ))]. نهاية gcd

العلاقة التكرارية للقاسم المشترك الأكبر، حيث${\displaystyle x\%y}$يعبّر عن الباقي من${\displaystyle x/y}$:

${\displaystyle \gcd(x,y)=\gcd(y,x\%y)}$لو${\displaystyle y\neq 0}$

${\displaystyle \gcd(x,0)=x}$

القاسم المشترك الأكبر (27، 9) = القاسم المشترك الأكبر (9، 27% 9) = القاسم المشترك الأكبر (9، 0) = 9

جي سي دي (111، 259) = جي سي دي (259، 111% 259) = القاسم المشترك الأكبر (259، 111) = القاسم المشترك الأكبر (111، 259% 111) = القاسم المشترك الأكبر (111، 37) = القاسم المشترك الأكبر (37، 111% 37) = القاسم المشترك الأكبر (37، 0) = 37

البرنامج التكراري أعلاه هو برنامج تكراري ذيلي ؛ وهو مكافئ لخوارزمية تكرارية، وتُظهر العملية الحسابية أعلاه خطوات التقييم التي ستُنفذها لغة برمجة تُزيل الاستدعاءات الذيلية. فيما يلي نسخة من الخوارزمية نفسها باستخدام التكرار الصريح، وهي مناسبة للغة برمجة لا تُزيل الاستدعاءات الذيلية. من خلال الاحتفاظ بحالته بالكامل في المتغيرين x و y واستخدام بنية تكرارية، يتجنب البرنامج إجراء استدعاءات تكرارية وتوسيع مكدس الاستدعاءات.

دالة القاسم المشترك الأكبر (gcd) هي: المدخلات : عدد صحيح x ، عدد صحيح y بحيث يكون x ≥ y و y ≥ 0. 1. أنشئ متغيرًا جديدًا باسم " الباقي". 2. ابدأ الحلقة. 1. إذا كانت قيمة y تساوي صفرًا، فاخرج من الحلقة. 2. اجعل الباقي هو باقي قسمة x على y 3. اجعل قيمة x تساوي قيمة y ٤. اجعل قيمة y هي الباقي. ٥. كرر الحلقة. ٣. أرجع قيمة x. نهاية القاسم المشترك الأكبر.

تتطلب الخوارزمية التكرارية متغيرًا مؤقتًا، وحتى مع معرفة خوارزمية إقليدس، يصعب فهم العملية بمجرد الفحص البسيط، على الرغم من أن الخوارزميتين متشابهتان جدًا في خطواتهما.

أبراج هانوي لغز رياضي يوضح حله مفهوم الاستدعاء الذاتي. ^{[ 32 ] [ 33 ]} توجد ثلاثة أوتاد يمكنها حمل أكوام من الأقراص ذات الأقطار المختلفة. لا يمكن وضع قرص أكبر فوق قرص أصغر. بدءًا من n قرصًا على وتد واحد، يجب نقلها إلى وتد آخر واحدًا تلو الآخر. ما هو أقل عدد من الخطوات اللازمة لنقل الكومة؟

تعريف الدالة :

${\displaystyle \operatorname {hanoi} (n)={\begin{cases}1&{\mbox{if }}n=1\\2\cdot \operatorname {hanoi} (n-1)+1&{\mbox{if }}n>1\\\end{cases}}}$

العلاقة التكرارية لهانوي :

${\displaystyle h_{n}=2h_{n-1}+1}$

${\displaystyle h_{1}=1}$

هانوي(4) = 2×هانوي(3) + 1 = 2×(2×هانوي(2) + 1) + 1 = 2×(2×(2×هانوي(1) + 1) + 1) + 1 = 2×(2×(2×1 + 1) + 1) + 1 = 2×(2×(3) + 1) + 1 = 2×(7) + 1 = 15

أمثلة على التطبيقات:

دالة hanoi هي: المدخلات : عدد صحيح n ، بحيث يكون n >= 1. 1. إذا كان n يساوي 1 ، فأرجع 1. 2. أرجع [2 * [ استدعاء hanoi(n-1)] + 1] نهاية hanoi

على الرغم من أن ليس لكل الدوال التكرارية حل صريح، إلا أنه يمكن اختزال متتالية برج هانوي إلى صيغة صريحة. ^{[ 34 ]}

h 1 = 1 = 2 1 - 1 h 2 = 3 = 2 2 - 1 h 3 = 7 = 2 3 - 1 h 4 = 15 = 2 4 - 1 h 5 = 31 = 2 5 - 1 ح 6 = 63 = 2 6 - 1 h 7 = 127 = 2 7 - 1

على العموم: h n = 2 n - 1، لجميع قيم n ≥ 1

خوارزمية البحث الثنائي هي طريقة للبحث في مصفوفة مرتبة عن عنصر واحد، وذلك بتقسيم المصفوفة إلى نصفين في كل دورة تكرارية. يكمن سرّها في اختيار نقطة منتصف قريبة من مركز المصفوفة، ومقارنة البيانات عند تلك النقطة بالبيانات المراد البحث عنها، ثم الاستجابة لأحد الشروط الثلاثة التالية: وجود البيانات عند نقطة المنتصف، أو كون البيانات عند نقطة المنتصف أكبر من البيانات المراد البحث عنها، أو كون البيانات عند نقطة المنتصف أصغر من البيانات المراد البحث عنها.

يُستخدم التكرار في هذه الخوارزمية لأنه مع كل دورة، يتم إنشاء مصفوفة جديدة بتقسيم المصفوفة القديمة إلى نصفين. ثم تُستدعى عملية البحث الثنائي بشكل تكراري، هذه المرة على المصفوفة الجديدة (الأصغر حجمًا). عادةً ما يتم تعديل حجم المصفوفة بتغيير فهرس البداية والنهاية. تُظهر الخوارزمية نموًا لوغاريتميًا لأنها تقسم مجال المشكلة إلى نصفين مع كل دورة.

مثال على تطبيق البحث الثنائي في لغة C:

/** * @brief استدعاء دالة binary_search مع الشروط الابتدائية المناسبة. * @param data مصفوفة من الأعداد الصحيحة مرتبة تصاعديًا * @param target العدد الصحيح المراد البحث عنه * @param count العدد الإجمالي للعناصر في المصفوفة * @returns نتيجة دالة binary_search */ int search ( int data [], int target , int count ) { // Start = 0 (مؤشر البداية) // End = count - 1 (مؤشر النهاية) return binary_search ( data , target , 0 , count - 1 ); }/** * @brief خوارزمية البحث الثنائي. * @param data مصفوفة من الأعداد الصحيحة مرتبة تصاعديًا * @param target العدد الصحيح المراد البحث عنه * @param start أصغر فهرس في المصفوفة * @param end أكبر فهرس في المصفوفة * @returns موضع العدد الصحيح المراد البحث عنه ضمن مصفوفة البيانات، -1 إذا لم يتم العثور عليه */ int binary_search ( int data [], int target , int start , int end ) { // الحصول على نقطة المنتصف. int mid = start + ( end - start ) / 2 ; // قسمة عدديةإذا كانت قيمة `start` أكبر من ` end` ، فسيتم إرجاع القيمة -1. وإلا ، إذا كانت قيمة ` data [ mid ] ` تساوي قيمة `target` ، فسيتم إرجاع قيمة ` mid` . وإلا ، إذا كانت قيمة ` data [ mid ] ` أكبر من قيمة ` target` ، فسيتم البحث في النصف السفلي من البيانات باستخدام الدالة ` binary_search` . وإلا ، إذا كانت قيمة ` data [ mid ] ` أصغر من قيمة ` target` ، فسيتم البحث في النصف العلوي من البيانات باستخدام الدالة ` binary_search` .

فيما يلي تعريف بلغة C لبنية عقدة قائمة مرتبطة. لاحظ تحديدًا كيف تُعرَّف العقدة بدلالة نفسها. العنصر "next" LinkedListهو مؤشر إلى قائمة مرتبطة أخرى، مما يُنشئ فعليًا نوع قائمة.

struct LinkedList { int data ; // بعض البيانات العددية struct LinkedList * next ; // مؤشر إلى عقدة أخرى في القائمة المرتبطة };

نظرًا لأن بنية بيانات العقدة struct تُعرَّف بشكل تكراري، يمكن تنفيذ الإجراءات التي تعمل عليها بشكل طبيعي كإجراءات تكرارية. يقوم الإجراء list_print المُعرَّف أدناه بالمرور على عناصر القائمة حتى تصبح فارغة (أي أن مؤشر القائمة يُساوي NULL). لكل عقدة، يطبع عنصر البيانات (عددًا صحيحًا). في تطبيق لغة C، تبقى القائمة دون تغيير بعد تنفيذ الإجراء list_print .

void list_print ( struct LinkedList * list ) { // الحالة الأساسية if ( list ) { printf ( "%d " , list -> data ); // طباعة البيانات العددية متبوعة بمسافة list_print ( list -> next ); // استدعاء متكرر على العقدة التالية } }

فيما يلي تعريف بسيط لعقدة الشجرة الثنائية. وكما هو الحال مع عقدة القوائم المتصلة، تُعرَّف هذه العقدة بدلالة نفسها، بشكل تكراري. يوجد مؤشران مرجعيان ذاتيان: الأيسر (يشير إلى الشجرة الفرعية اليسرى) والأيمن (يشير إلى الشجرة الفرعية اليمنى).

struct BinaryTree { int data ; // بعض البيانات العددية struct BinaryTree * left ; // مؤشر إلى الشجرة الفرعية اليسرى struct BinaryTree * right ; // مؤشر إلى الشجرة الفرعية اليمنى };

يمكن تنفيذ العمليات على الشجرة باستخدام الاستدعاء الذاتي. لاحظ أنه نظرًا لوجود مؤشرين يشيران إلى نفس العنصر (يسار ويمين)، فقد تتطلب عمليات الشجرة استدعاءين ذاتيين.

// اختبار ما إذا كانت العقدة tree_node تحتوي على i؛ إرجاع 1 إذا كانت كذلك، و0 إذا لم تكن كذلك. int tree_contains ( struct BinaryTree * node , int i ) { if ( ! node ) { return 0 ; // الحالة الأساسية } else if ( node -> data == i ) { return 1 ; } else { return tree_contains ( node -> left , i ) || tree_contains ( node -> right , i ); } }

سيتم إجراء استدعاءين متكررين على الأكثر لأي استدعاء معين للدالة tree_contains كما هو محدد أعلاه.

// اجتياز الترتيب الداخلي: void tree_print ( struct BinaryTree * node ) { // الحالة الأساسية if ( node ) { tree_print ( node -> left ); // الانتقال إلى اليسار printf ( "%d " , node -> data ); // طباعة العدد الصحيح متبوعًا بمسافة tree_print ( node -> right ); // الانتقال إلى اليمين } }

يوضح المثال أعلاه عملية اجتياز الشجرة الثنائية بترتيبها الصحيح . شجرة البحث الثنائية هي حالة خاصة من الشجرة الثنائية حيث تكون عناصر البيانات في كل عقدة مرتبة.

بما أن عدد الملفات في نظام الملفات قد يختلف، فإن الاستدعاء الذاتي هو الطريقة العملية الوحيدة لاجتيازه وبالتالي تعداد محتوياته. يُشبه اجتياز نظام الملفات إلى حد كبير اجتياز الشجرة ، لذا فإن المفاهيم الكامنة وراء اجتياز الشجرة قابلة للتطبيق على اجتياز نظام الملفات. وبشكل أكثر تحديدًا، يُعد الكود أدناه مثالًا على اجتياز نظام الملفات بترتيب ما قبل الترتيب .

package org.wikipedia.examples ;استيراد java.io.File ؛public class Example { /**  * الحصول على جذور نظام الملفات  * المتابعة في اجتياز نظام الملفات بشكل متكرر  */ private static void traverse () { File [] fs = File . listRoots (); for ( int i = 0 ; i < fs . length ; i ++ ) { System . out . println ( fs [ i ] ); if ( fs [ i ] . isDirectory () && fs [ i ] . canRead ()) { rtraverse ( fs [ i ] ); } } }/**  * اجتياز دليل معين بشكل متكرر  *  * @param fd يشير إلى نقطة بداية الاجتياز  */ private static void rtraverse ( File fd ) { File [] fss = fd . listFiles ();for ( int i = 0 ; i < fss.length ; i ++ ) { System.out.println ( fss [ i ] ) ; if ( fss [ i ] .isDirectory ( ) && fss [ i ] .canRead ( ) ) { rtraverse ( fss [ i ] ) ; } } }​​​public static void main ( String [] args ) { traverse (); } }

هذا الكود هو عبارة عن تكرار وتكرار - يتم تكرار الملفات والمجلدات، ويتم فتح كل مجلد بشكل متكرر.

تُعد طريقة "rtraverse" مثالاً على الاستدعاء الذاتي المباشر، بينما تُعد طريقة "traverse" دالة تغليف.

السيناريو "الأساسي" هو أنه سيكون هناك دائمًا عدد ثابت من الملفات و/أو الدلائل في نظام ملفات معين.

إذا كان التعقيد الزمني للدالة على الصورة $${\displaystyle T(n)=a\cdot T(n/b)+f(n)}$$

إذن، فإنّ قيمة Big O للتعقيد الزمني هي كالتالي:

• لو${\displaystyle f(n)=O(n^{\log _{b}a-\varepsilon })}$لبعض الثوابت${\displaystyle \varepsilon >0}$، ثم${\displaystyle T(n)=\Theta (n^{\log _{b}a})}$
• لو${\displaystyle f(n)=\Theta (n^{\log _{b}a})}$، ثم${\displaystyle T(n)=\Theta (n^{\log _{b}a}\log n)}$
• لو${\displaystyle f(n)=\Omega (n^{\log _{b}a+\varepsilon })}$لبعض الثوابت${\displaystyle \varepsilon >0}$وإذا${\displaystyle a\cdot f(n/b)\leq c\cdot f(n)}$بالنسبة لثابت ما c < 1 ولجميع قيم n الكبيرة بما فيه الكفاية ، فإن${\displaystyle T(n)=\Theta (f(n))}$

حيث يمثل a عدد الاستدعاءات المتكررة في كل مستوى من مستويات التكرار، ويمثل b العامل الأصغر الذي يكون به المدخل للمستوى التالي من التكرار (أي عدد الأجزاء التي تقسم إليها المشكلة)، ويمثل f ( n ) العمل الذي تقوم به الدالة بشكل مستقل عن أي تكرار (مثل التقسيم، إعادة التجميع) في كل مستوى من مستويات التكرار.