الإجراءات الفرعية. العودية


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

إذا كنت تتذكر الرياضيات ، فهناك يمكنك التعرف على مبدأ الاستقراء الرياضي . وهي كالتالي:

عبارة معينة صحيحة لكل nbsp؛ طبيعي إذا
نبسب ؛ نبسب ؛ 1. صالح لـ & nbsp؛ n = 1 & nbsp؛ و
نبسب ؛ نبسب ؛ 2. من صحة العبارة لأي تعسفي طبيعي n = k & nbsp ؛ ويترتب على ذلك أنها صحيحة لـ & nbsp؛ n = k + 1.

في البرمجة ، تسمى هذه التقنية العودية

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

التكراري سيطلق عليه أيضًا إجراء (وظيفة) يستدعي نفسه مباشرة أو من خلال إجراءات ووظائف أخرى
مثال على إجراء تكراري: <قبل> الإجراء Rec (a: عدد صحيح) ؛ يبدأ نبسب ؛ نبسب ؛ إذا أ & GT. 0 بعد ذلك نبسب ؛ نبسب ؛ نبسب ؛ نبسب ؛ Rec (أ - 1) ؛ نبسب ؛ نبسب ؛ اكتب)؛ end؛ من الناحية التخطيطية ، يمكن تمثيل عمل العودية بواسطة مخطط انسيابي

نبسب ؛
يتم تنفيذ الإجراء Rec () & nbsp؛ مع المعلمة 3. ثم ، داخل الإجراء مع المعلمة 3 ، يتم استدعاء الإجراء مع المعلمة 2 ، وهكذا ، حتى يتم استدعاء الإجراء مع المعلمة 0. عندما يتم استدعاء الإجراء مع تم استدعاء المعلمة 0 ، ولن يحدث الاستدعاء المتكرر بالفعل ، وسوف يطبع الإجراء مع المعلمة 0 الرقم 0 وينتهي. ثم يتم نقل التحكم مرة أخرى إلى الإجراء بالمعامل 1 ، كما أنه ينهي عمله بطباعة الرقم 1 ، وهكذا. قبل الإجراء مع المعلمة 3. نبسب ؛

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

Training problem

العودية. ما هذا؟

لقد رأينا أن العودية هي التنفيذ المتكرر للتعليمات الواردة في روتين فرعي. وهذا بدوره يشبه عمل الدورة. هناك لغات برمجة يكون فيها بناء الحلقة غائبًا على الإطلاق ، على سبيل المثال ، Prolog. & nbsp؛
لنحاول محاكاة عملية حلقة for. & nbsp؛
تحتوي الحلقة for على متغير عداد الخطوة. في روتين فرعي متكرر ، يمكن تمرير مثل هذا المتغير كمعامل. <قبل> // LoopImitation () مع معلمتين // المعلمة الأولى & ndash؛ عداد الخطوة ، المعلمة الثانية & ndash ؛ العدد الإجمالي للخطوات LoopImitation (i، n: عدد صحيح) ؛ يبدأ نبسب ؛ نبسب ؛ writeln (& # 39 ؛ Hello N & # 39 ؛، i) ؛ // العامل المراد تكراره لأي قيمة لـ i نبسب ؛ نبسب ؛ إذا كنت & lt ؛ n ثم // حتى يصبح عداد الحلقة مساويًا للقيمة n ، نبسب ؛ نبسب ؛ نبسب ؛ نبسب ؛ LoopImitation (i + 1، n) ؛ // استدعاء مثيل جديد من الإجراء ، مع المعلمة i + 1 (الانتقال إلى القيمة التالية i) نهاية؛

Training problem

العودية. محاكاة الدورة

لفهم العودية ، تحتاج إلى فهم العودية ...
نبسب ؛
التكرار & nbsp؛ في البرمجة & mdash؛ بمعنى واسع و [مدش] ؛ تنظيم معالجة البيانات ، حيث يتم تكرار الإجراءات عدة مرات ، دون أن يؤدي ذلك إلى مكالمات إلى أنفسهم (على عكس & nbsp ؛٪ BA٪ D1٪ 83٪ D1٪ 80٪ D1٪ 81٪ D0٪ B8٪ D1٪ 8F "title =" Recursion " > العود ). بالمعنى الضيق و [مدش]. عملية معالجة البيانات الدورية بخطوة واحدة. & nbsp؛
غالبًا ما تستخدم الخوارزميات التكرارية في الخطوة الحالية (التكرار) نتيجة نفس العملية أو الإجراء المحسوب في الخطوات السابقة. & nbsp ؛ أحد الأمثلة على هذه الحسابات هو حساب علاقات التكرار. & nbsp ؛
مثال بسيط على القيمة العودية هو العامل: \ (N! = 1 \ cdot 2 \ cdot 3 \ cdot \ ... \ \ cdot N \) حساب القيمة في كل خطوة (التكرار) هو \ (N = N \ cdot i \) . & nbsp؛ عند حساب قيمة \ (N \) ، نأخذ القيمة المخزنة بالفعل & nbsp؛ \ (N \) . <ر ​​/>
يمكن أيضًا وصف مضروب الرقم باستخدام الصيغة المتكررة :



قد تلاحظ أن هذا الوصف ليس أكثر من وظيفة تكرارية.
هنا السطر الأول ( \ (n & lt؛ = 1 \) ) & mdash؛ هذه هي الحالة الأساسية (حالة نهاية العودية) والسطر الثاني هو الانتقال إلى الخطوة التالية. & nbsp ؛
نبسب ؛ <الجسم>
ستبدو وظيفة العوامل العودية على هذا النحو قارن الخوارزمية لإيجاد العامل بالطريقة المعتادة غير العودية
دالة عاملة (n: عدد صحيح): عدد صحيح ؛
تبدأ
نبسب ؛ نبسب ؛ إذا ن & GT. 1 ثم
نبسب ؛ نبسب ؛ نبسب ؛ نبسب ؛ عاملي: = n * عاملي (n - 1)
نبسب ؛ نبسب ؛ آخر
نبسب ؛ نبسب ؛ نبسب ؛ نبسب ؛ عاملي: = 1 ؛
النهاية ؛ 		س: = 1 ؛
بالنسبة إلى i: = 2 to n do
نبسب ؛ نبسب ؛ س: = س * ط ؛
writeln (x)؛

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

Training problem

العودية والتكرار