قد يحتوي الإجراء أو الوظيفة على استدعاء لإجراء آخر ضمنه. بما في ذلك ، يمكن للروتين الفرعي استدعاء نفسه. في هذه الحالة ، لا يهتم الكمبيوتر. كما أنه ، كما هو الحال دائمًا ، ينفذ باستمرار الأوامر التي التقى بها من أعلى إلى أسفل.
إذا كنت تتذكر الرياضيات ، فهناك يمكنك التعرف على مبدأ الاستقراء الرياضي . وهي كالتالي:
بعض العبارات صحيحة لكل n طبيعية إذا
نبسب ؛ نبسب ؛ 1. صالح لـ & nbsp؛ n = 1 & nbsp؛ و
نبسب ؛ نبسب ؛ 2. من صحة العبارة لأي تعسفي طبيعي n = k & nbsp ؛ ويترتب على ذلك أنها صحيحة لـ & nbsp؛ n = k + 1.
في البرمجة ، تسمى هذه التقنية العودية
التكرار هو طريقة لتحديد مجموعة من الكائنات من حيث المجموعة نفسها ، بناءً على حالات أساسية بسيطة معينة.
التكراري سيطلق عليه أيضًا إجراء (وظيفة) يستدعي نفسه مباشرة أو من خلال إجراءات ووظائف أخرى
مثال على إجراء تكراري:
<قبل>
تسجيل باطل (int a)
{
إذا (a & gt؛ 0) Rec (a-1) ؛
كوت & lt؛ & lt؛ أ؛
}
من الناحية التخطيطية ، يمكن تمثيل عمل العودية بواسطة مخطط انسيابي
نبسب ؛
يتم تنفيذ الإجراء Rec () & nbsp؛ مع المعلمة 3. ثم ، داخل الإجراء مع المعلمة 3 ، يتم استدعاء الإجراء مع المعلمة 2 ، وهكذا ، حتى يتم استدعاء الإجراء مع المعلمة 0. عندما يتم استدعاء الإجراء مع تم استدعاء المعلمة 0 ، ولن يحدث الاستدعاء المتكرر بالفعل ، وسوف يطبع الإجراء مع المعلمة 0 الرقم 0 وينتهي. ثم يتم نقل التحكم مرة أخرى إلى الإجراء بالمعامل 1 ، كما أنه ينهي عمله بطباعة الرقم 1 ، وهكذا. قبل الإجراء مع المعلمة 3. نبسب ؛
يتم تخزين جميع الإجراءات التي تسمى في الذاكرة حتى يكملوا عملهم. يسمى عدد الإجراءات المتزامنة عمق العودية .
|
العودية. محاكاة الحلقة
لقد رأينا أن العودية هي التنفيذ المتكرر للتعليمات الواردة في روتين فرعي. وهذا بدوره يشبه عمل الدورة. هناك لغات برمجة يكون فيها بناء الحلقة غائبًا على الإطلاق ، على سبيل المثال ، Prolog. & nbsp؛
دعنا نحاول محاكاة عمل الحلقة لـ . & nbsp؛
تحتوي الحلقة لـ على متغير عداد الخطوة. في روتين فرعي متكرر ، يمكن تمرير مثل هذا المتغير كمعامل.
// الإجراء LoopImitation () مع معلمتين.
// المعلمة الأولى & ndash؛ عداد الخطوة ، المعلمة الثانية & ndash ؛ العدد الإجمالي للخطوات.
LoopImitation باطلة (int i، int n)
{
كوت & lt؛ & lt؛ "مرحبًا N" & lt؛ & lt؛ أنا & lt ؛ & lt ؛ نهاية. // العامل المراد تكراره لأي قيمة لـ i
إذا (i & lt ؛ n) // حتى يساوي عداد الحلقة n ،
{// استدعاء مثيل جديد للإجراء ، مع المعلمة i + 1 (انتقل إلى القيمة التالية i).
LoopImitation (i + 1، n) ؛
}
}
|
العودية والتكرار
لفهم العودية ، تحتاج إلى فهم العودية ...
نبسب ؛
التكرار & nbsp؛ في البرمجة - خطوة واحدة لعملية معالجة البيانات الدورية. & nbsp؛
غالبًا ما تستخدم الخوارزميات التكرارية في الخطوة الحالية (التكرار) نتيجة نفس العملية أو الإجراء المحسوب في الخطوات السابقة. & nbsp ؛ أحد الأمثلة على هذه الحسابات هو حساب علاقات التكرار. & nbsp ؛
مثال بسيط على القيمة العودية هو العامل: \ (N! = 1 \ cdot 2 \ cdot 3 \ cdot \ ... \ \ cdot N \) .
حساب القيمة في كل خطوة (التكرار) هو \ (N = N \ cdot i \) . & nbsp؛ عند حساب قيمة \ (N \) ، نأخذ القيمة المخزنة بالفعل & nbsp؛ \ (N \) . <ر />
يمكن أيضًا وصف مضروب الرقم باستخدام الصيغة المتكررة :
\ (\ start {equation *} n! = \ begin {cases} 1 & amp؛ \ text {n & lt؛ = 1،} \\ (n-1)! \ cdot n & amp؛ \ text {n & gt؛ 1.} \ end {cases} \ end {equation *} \)
قد تلاحظ أن هذا الوصف ليس أكثر من وظيفة تكرارية.
هنا السطر الأول ( \ (n & lt؛ = 1 \) ) هو الحالة الأساسية (شرط إنهاء العودية) والسطر الثاني هو الانتقال إلى الخطوة التالية. نبسب ؛
نبسب ؛
<الجسم>
| دالة عاملة متكررة |
الخوارزمية التكرارية |
|
عامل int عاملي (int n)
{
إذا (n & gt؛ 1)
عودة ن * عاملي (ن - 1) ؛
آخر يعود 1 ؛
}
|
س = 1 ؛
لـ (i = 2 ؛ i & lt ؛ = n ؛ i ++)
س = س * ط ؛
كوت & lt؛ & lt؛ x ؛
|
يجب أن يكون مفهوماً أن استدعاءات الوظائف تنطوي على بعض النفقات الإضافية ، لذا فإن حساب العوامل غير العودية سيكون أسرع قليلاً. & nbsp؛
الخلاصة: حيث يمكنك كتابة برنامج باستخدام خوارزمية تكرارية بسيطة ، بدون تكرار ، فأنت بحاجة إلى الكتابة بدون تكرار. ولكن لا يزال هناك فئة كبيرة من المشاكل حيث يتم تنفيذ العملية الحسابية فقط عن طريق العودية.
من ناحية أخرى ، غالبًا ما تكون الخوارزميات العودية أكثر قابلية للفهم.
نبسب ؛
|
مهمة
في أبجدية لغة القبيلة "Tumba-Yumba" ؛ أربعة أحرف: "K" ، "L" ، "M" و & quot؛ N & quot ؛. تحتاج إلى عرض جميع الكلمات التي تتكون من أحرف n التي يمكن إنشاؤها من أحرف هذه الأبجدية.
المشكلة هي مشكلة القوة الغاشمة العادية التي يمكن اختزالها إلى مشكلة أصغر.
سنقوم باستبدال الأحرف بالتسلسل.
يمكن أن يكون الموضع الأول للكلمة واحدًا من الأحرف الأربعة للأبجدية (K. L ، M ، N).
لنضع الحرف K أولاً. بعد ذلك ، من أجل الحصول على جميع المتغيرات التي تحتوي على الحرف الأول K ، تحتاج إلى تعداد جميع مجموعات الأحرف الممكنة & nbsp؛ في المواضع المتبقية n - 1 & nbsp؛ وما إلى ذلك. (انظر الصورة).
وهكذا ، يتم تقليل المشكلة إلى حل أربع مسائل طولها n - 1 .
نبسب ؛
تكرار أكثر من n حرفًا بشكل متكرر
w [0] = & # 39؛ K & # 39 ؛؛ // كرر خلال آخر أحرف L-1
ث [0] = & # 39 ؛ L & # 39 ؛؛ // كرر خلال آخر أحرف L-1
ث [0] = & # 39 ؛ M & # 39 ؛؛ // كرر خلال آخر أحرف L-1
ث [0] = & # 39 ؛ N & # 39 ؛؛ // كرر خلال آخر أحرف L-1
w - سلسلة أحرف تخزن كلمة العمل.
وهكذا ، حصلنا على العودية. & nbsp ؛ يمكننا ترتيب حل المشكلة في شكل إجراء تكراري. & nbsp ؛
يبقى لتحديد متى سينتهي العودية؟ عندما يتم تعيين جميع الأحرف ، أي أن عدد الأحرف المحددة هو n . في هذه الحالة ، تحتاج إلى عرض الكلمة الناتجة على الشاشة والخروج من الإجراء.
سيبدو برنامج C ++ بهذا الشكل.
# include & lt؛ iostream & gt؛
استخدام اسم للمحطة؛
Void TumbaWords (سلسلة A ، string & amp؛ w ، int N)
// w - معلمة قابلة للتغيير (سلسلة-نتيجة)
// يتم تمرير إجراء TumbaWords الأبجدية كسلسلة أحرف ،
// الكلمة word وعدد الأحرف التي تم تعيينها بالفعل (السابقة & ndash ؛ 0).
{
إنت أنا
إذا (N == w.size ())
{
نبسب ؛ // إذا تم بالفعل تعيين جميع الأحرف للكلمة ، & nbsp؛
نبسب ؛ // ثم من الضروري إخراج سلسلة وإنهاء الإجراء
كوت & lt؛ & lt؛ & lt؛ & lt؛ نهاية.
يعود؛
}
لـ (i = 1 ؛ i & lt ؛ A.size () ؛ i ++)
{
نبسب ؛ // إذا كان الشرط أعلاه خاطئًا (أي أنه لا توجد مسافات بين جميع الأحرف ،
نبسب ؛ // ثم في الحلقة نمر بجميع أحرف الأبجدية و
// ضع الحرف بالتناوب على أول مساحة خالية
w [N] = A [i] ؛
TumbaWords (A، w، N + 1) ؛
}
}
رئيسي()
{
إنت.
سلسلة.
إنتن.
سينما & GT ؛ & GT. ن؛
word.resize (n) ؛ // زيادة السلسلة إلى الحجم n
TumbaWords ("KLMN" ، كلمة ، 0) ؛
}
لاحظ أن w معلمة قابلة للتغيير (سلسلة نتيجة)!
|