يمكن أن يحتوي الإجراء أو الوظيفة على استدعاء لإجراء آخر داخله. بما في ذلك ، يمكن للروتين الفرعي استدعاء نفسه. في هذه الحالة ، لا يهتم الكمبيوتر. هو ، كما هو الحال دائمًا ، ينفذ باستمرار الأوامر التي التقى بها من أعلى إلى أسفل.
إذا كنت تتذكر الرياضيات ، فهناك يمكنك تلبية مبدأ الاستقراء الرياضي. على النحو التالي: & nbsp؛ بعض العبارات صحيحة لكل طبيعي & nbsp؛ n إذا
نبسب ؛ نبسب ؛ 1) صالح لـ & nbsp؛ n = 1 ؛
نبسب ؛ نبسب ؛ 2) من صحة العبارة لأي تعسفي طبيعي n = k & nbsp ؛ ويترتب على ذلك أنها صحيحة لـ & nbsp؛ n = k + 1 .
في البرمجة ، هذه التقنية تسمى العودية.
التكرار طريقة لتعريف مجموعة من الكائنات وفقًا للمجموعة نفسها ، بناءً على حالات أساسية بسيطة معينة.
التكرار هو إجراء (وظيفة) تستدعي نفسها مباشرة أو من خلال إجراءات ووظائف أخرى.
مثال على إجراء تكراري:
تسجيل باطل (int a)
{
نبسب ؛ إذا (a & gt؛ 0) {Rec (a-1) ؛ }
نبسب ؛ Console.WriteLine (أ) ؛
}
تخطيطيًا ، يمكن تمثيل عمل العودية كمخطط انسيابي.
نبسب ؛
Rec () & nbsp؛ يتم تنفيذ الإجراء باستخدام المعلمة 3 بعد ذلك ، داخل الإجراء مع المعلمة 3 ، يتم استدعاء الإجراء مع المعلمة 2 ، وهكذا ، حتى يتم استدعاء الإجراء مع المعلمة 0. work. ثم يتم نقل التحكم مرة أخرى إلى الإجراء بالمعامل 1 ، كما أنه ينهي عمله بطباعة الرقم 1 ، وهكذا. قبل الإجراء مع المعلمة 3. نبسب ؛
يتم تخزين جميع الإجراءات التي تسمى في الذاكرة حتى يكملوا عملهم. يُطلق على عدد الإجراءات المتزامنة اسم عمق العودية .
|
اكتشفنا أن العودية هي التنفيذ المتكرر للأوامر المضمنة في روتين فرعي. وهذا بدوره يشبه عمل الدورة. هناك لغات برمجة يكون فيها بناء الحلقة غائبًا على الإطلاق ، على سبيل المثال ، Prolog. & nbsp؛
دعونا نحاول محاكاة عمل الحلقة for . & nbsp؛
تحتوي حلقة for على متغير عداد الخطوة. في روتين فرعي متكرر ، يمكن تمرير مثل هذا المتغير كمعامل.
<قبل>
// الإجراء LoopImitation () مع معلمتين
// المعلمة الأولى & ndash؛ عداد الخطوة ، المعلمة الثانية & ndash ؛ العدد الإجمالي للخطوات
LoopImitation الفراغ الثابت (int i، int n)
{
Console.WriteLine (& quot؛ Hello N & quot؛ + i)؛ // عبارة تتكرر لأي قيمة i
إذا (i & lt؛ n) // حتى يساوي عداد الحلقة n ،
{
LoopImitation (i + 1، n) ؛ // استدعاء جديد إجراء المثال ، مع المعلمة i + 1 (انتقل إلى قيمة i التالية)
}
}
|
العودية والتكرار
لفهم العودية ، تحتاج إلى فهم العودية ...
نبسب ؛
التكرار & 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 \) ) هو الحالة الأساسية (شرط إنهاء العودية) والسطر الثاني هو الانتقال إلى الخطوة التالية. نبسب ؛
نبسب ؛
<الجسم>
| دالة التوزيع العودية |
الخوارزمية التكرارية |
<قبل>
static int Factorial (int n) {
إذا (n & gt؛ 1)
عودة ن * عاملي (ن - 1) ؛
آخر يعود 1 ؛
}
|
<قبل>
int x = 1؛
لـ (int i = 2 ؛ i & lt ؛ = n ؛ i ++)
س = س * ط ؛
Console.WriteLine ("٪ d"، x)؛
|
يجب أن يكون مفهوماً أن استدعاءات الوظائف تنطوي على بعض النفقات الإضافية ، لذا فإن حساب العوامل غير العودية سيكون أسرع قليلاً. & nbsp؛
الخلاصة: حيث يمكنك كتابة برنامج باستخدام خوارزمية تكرارية بسيطة ، بدون تكرار ، فأنت بحاجة إلى الكتابة بدون تكرار. ولكن لا يزال هناك فئة كبيرة من المشاكل حيث يتم تنفيذ العملية الحسابية فقط عن طريق العودية.
من ناحية أخرى ، غالبًا ما تكون الخوارزميات العودية أكثر قابلية للفهم.
|
الترجمة التكرارية لرقم من نظام رقمي إلى آخر
في & nbsp ؛ في بعض المواقف من الإجراءات ، يمكنك استخدام كلمة return & nbsp؛ بدون وسيطة - أي في الواقع ، لا يزال الإجراء لا يُرجع أي شيء. & nbsp ؛ قد يكون هذا مفيدًا عند التكرار ، عندما & nbsp ؛ return & nbsp؛ يُستخدم لإنهاء الهبوط عند الحالات الأساسية لقيم المعلمات التي يتم تكرارها. على سبيل المثال ، قد يبدو الإجراء الذي يحول رقمًا من عشري إلى ثنائي كما يلي:
ثابت & نبسب ؛ باطل printTwo (int n)
{& nbsp؛ & nbsp؛
نبسب ؛ إذا (ن == 0) عودة ؛
نبسب ؛ نبسب ؛ printTwo (ن / 2) ؛
نبسب ؛ إذا (ن٪ 2 == 0) Console.Write (0) ؛
نبسب ؛ آخر نبسب ؛ وحدة التحكم. الكتابة (1) ؛
}
|
مهمة
في أبجدية لغة القبيلة "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 # هكذا.
// w - معلمة قابلة للتغيير (سلسلة-نتيجة)
// يتم تمرير إجراء TumbaWords الأبجدية كسلسلة أحرف ،
// الكلمة word وعدد الأحرف المحددة بالفعل (في البداية & ndash ؛ 0)
TumbaWords باطل ثابت (سلسلة A ، سلسلة المرجع w ، int N)
{
إذا (N == w.Length) // w.Length - عدد الأحرف في السلسلة
{
نبسب ؛ // إذا تم بالفعل تعيين جميع الأحرف للكلمة ، & nbsp؛ نبسب ؛
نبسب ؛ // ثم من الضروري إخراج سلسلة وإنهاء الإجراء
Console.WriteLine (ث) ؛
يعود؛
}
لـ (int i = 0؛ i & lt؛ w.Length؛ i ++) // إذا كان الشرط أعلاه خاطئًا (أي أنه لا توجد مسافات بين جميع الأحرف ،
{
نبسب ؛ نبسب ؛ // إذا كان الشرط أعلاه خاطئًا (أي ، ليست كل الأحرف متباعدة ، & nbsp؛
نبسب ؛ // ثم في الحلقة نمر بجميع أحرف الأبجدية و
نبسب ؛ // ضع الحرف بالتناوب على أول مساحة خالية
w + = A [i] ؛
TumbaWords (A ، المرجع w ، N + 1) ؛
ث = ث إزالة (طول ث - 1) ؛ // ثم قم بإزالة آخر حرف مضاف ،
نبسب ؛ // لعمل كلمة جديدة بنفس البادئة
}
}
فراغ ثابت رئيسي ()
{
int n = Convert.ToInt32 (Console.ReadLine ()) ،
كلمة سلسلة = & quot؛ & quot ؛؛
TumbaWords (& quot؛ KLMN & quot ؛، المرجع word ، 0) ؛
}
لاحظ أن w معلمة قابلة للتغيير (سلسلة نتيجة)!
|