ما هي الخورازميات العودية «Recursion Algorithms» ؟
سلسلة تعلم الخوارزميات: ما هي الخوارزميات العودية؟ نوصف الشيء بأنه ذو بنية عودية إذا كان مؤلفًا من مكونات بعضها معرف تعريف الشيء الأصلي أو الأساسي.
إن مفهوم العودية ذائع الصيت في المجال الرياضي إذ يستخدم في التعريفات الرياضية وحل كثير من المسائل فيها كمسائل المضاريب و”متسلسلة فيبوناتشي” ومسألة “برج هانوي” وغيرها من المشاكل ذات التعريف العودي.
دعنا نوضح الفكرة الرئيسية لاستخدام الخوارزميات العودية المسائل كالتالي: لحل مسألة ما، سنقوم بتحليل المسألة الرئيسية إلى مسائل فرعية لنفس المسألة الأصلية ومن ثم ّ استخدام حلول المسائل الفرعية للوصل إلى الحل النهائي للمسألة الرئيسية.
يستخدم مفهوم الخوارزميات العودية في حسابات المضاريب «factorials» في الرياضيات فلكي نتمكن من حساب مضروب عدد ما يجب معرفة مضروب العدد السابق وهكذا حتى نصل إلى العدد 1 .
فمثلًا إذا كان لدينا عدد نرمز له بالرمز n وأردنا حساب مضروبه- دعنا نرمز لمضروبه بالرمز!n -والذي يمثل في هذه الحالة المسألة الأصلية- سنحتاج إذن إلى حساب المسائل الفرعية المتفرعة من هذه المسألة الأصلية أي سنقوم بحساب «(n-1)!» و«(n-2)!» وهكذا. لنفترض أننا نريد حساب مضروب العدد 4 ففي هذه الحالة سيتعين علينا إجراء العملية الحسابية كالتالي:
4!= 4 x (4 -1)! =4 x 3! = 4 x 3 x (3-1)! = 4 x 3 x 2! =4 x 3 x 2 x (2-1)! = 4 x 3 x 2 x 1! = 4 x 3 x 2 x 1x (1-1)! =4 x 3 x 2 x 1 x 0!
كما نرى في مثالنا السابق قمنا بتقسيم المسألة الرئيسية إلى عدة مسائل فرعية فلحساب مضروب العدد 4 قمنا بحساب مضروب العدد 3 ثم مضروب العد 2 وهكذا حتى وصلنا للرقم 0 والذي مضروبه يساوي 1 (0! =1). إذن مضروب العدد 4 يساوي
4! = 4 x 3 x 2 x 1 x 1 =24
محتويات المقال :
ما هي شروط الخوارزميات العودية ؟
يجب أن تحتوي جميع الخوارزميات العودية على ما يلي:
- «الحالة الأساسية-Base Case»: متى ستتوقف فيه الخوارزمية ففي المثال السابق توقفنا عن حساب مضاريب الأعداد عندما وصلنا إلى الرقم 0.
- الإجراء التنفيذي للوصول إلى الحالة الحالة الأساسية: يقصد به الجزء الذي نجعل فيه المشكلة أبسط (على سبيل المثال ،نقسم المسألة الاصلية إلى عدة فروع أصغر كما في المثال السابق لحساب مضروب العدد 4 نقوم بحساب مضاريب الأعداد الطبيعية التي هي أقل من 4).
- الاستدعاء التكراري: هو االجزء الذي نستخدم فيه نفس الخوارزمية لحل نسخة أبسط من المشكلة.
ما هي أنواع الإجراءات في الخوارزميات العودية ؟
إنّ الأداة اللازمة والكافية للتعبير عن برنامج معيّن تعبيراً عودياًّ هي «الإجرائية-Procedure» أو «الدالة-Function» لأنها تسمح بإعطاء اسم معين لمجموعة تعليمات، وهذا ما يسمح باستدعاء هذه التعليمات استدعاءً عوديّاً. يمكن التمييز بين نوعين من الإجرائيات العوديّة:
– الإجرائيات ذات العوديّة المباشرة «direct recursion»: نقول عن إجرائية P إنها عوديّة مباشرة إذا كانت تحوي استدعاءً صريحاً لنفسها.
– الإجرائيات ذات العوديّة غير المباشرة «indirect recursion»: نقول عن إجرائية P إنها عوديّة غير مباشرة إذا كانت تستدعي إجرائية أخرى Q تستدع P بطريقة مباشرة أو غير مباشرة.
تطبيق مفهوم العودية في متسلسة فيبوناتشي
في عام 1202 توصل فيبوناتشي إلى اكتشاف أجمل السلاسل العددية على الإطلاق وذلك أثناء بحثه حول سرعة تكاثر الأرانب في الظروف المثالية وقد صاغ فرضياته على النحو التالي:
- نبدأ بزوج واحد من الأرانب -ذكر وأنثى- حديثي الولادة.
- تصبح الأرانب قادرة على الإنجاب عندما يصبح عمرها شهراً واحداً.
- بعد أن يبدأ زوج الأرانب بالإنجاب فإنه ينجب في كل شهرا زوجاً واحداً من الأرانب -ذكر وأنثى-
- الأرانب لا تموت خلال مدة الحساب
إذن كم زوجًا من الأرانب سيكون لدينا بعد عام؟ هذا السؤال الذي طرحه العالم فيبوناتشي وتمكن آنذاك من صياغة متسلسلته الشهيرة على النحو التالي
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144,……
إذا دققت النظر إلى هذه المتسلسلة ستجد أن كل رقم هو ناتج عن جمع الرقمين السابقين له، فالرقم 89 هو ناتج جمع الرقمين 55 و 34 والرقم 55 هو ناتج جمع الرقمين السابقين له 34 و 21 وهكذا. إذاً لدينا حالتان بدائيتان (0 و 1) بينما من أجل أي عدد آخر لا يمكن حساب القيمة إلا بالاعتماد على القيم المسبقة، هذا يعني أنه لدينا تكرار حساب دالة فيبوناتشي ولكن في كل مرة لأعداد أصغر حتى نصل إلى أبسط قيم ممكنة أي 0 و 1.
بذلك يمكننا القول بأن متسلسلة فيبوناتشي معرفة تعريفًا عوديًا. الجدير بالذكر أن هذه المتسلسة تظهر بشكلٍ متكرر في الطبيعة لتبدو وكأنها مؤشر على بعض جوانب النمو. على سبيل المثال، يُمكنك إيجادها في حلقات الحلزونات الطبيعية، وفي النباتات، وفي أزهار عباد الشمس وفي شجرة عائلة النحل، وترتبط هذه السلسلة برقمٍ شهير يُعرف بالنسبة الذهبية «golden ratio» إذ أن النسبة بين أي رقمين متتالين -أي رقمين بعد الرقم 2 في المتسلسلة- تقترب من النسبة الذهبية كلما تقدمنا أكثر في المتسلسلة فالنسبة بين 5 و 3 تساوي 1.666 والنسبة بين 8 و 5 يساوي 1.6 وهكذا حتى نصل إلى العدد 40 والأعداد التالية ستجد بأن النسبة تساوي تقريبا النسبة الذهبية والتي تقدر قيمتها ب 1.618033988749895 .
توزع حلزونات البذور على نمط متسلسة فيبوناتشي في زهور عباد الشمس
هل الخوارزميات العودية هي الحل الأمثل في جميع الحالات؟
نستفيد من الخوارزميات العودية عندما نتعامل مع مسائل معقدة حيث تقوم العودية بتقسيم هذه الحالة إلى حالات أبسط على التوالي حتى إن تصل إلى حالة بدائية. ومن ثم تعود خطوةً خطوةً وتعوض القيم الناتجة إلى أن تصل إلى الحالة الأصلية فنحصل على الناتج النهائي.
لكن الاستدعاءات العودية تسبب ضياعاً في الوقت وتستهلك ذاكرة إضافية لذا لا تستخدم في الواقع العملي في كل المسائل فذواكر الحواسيب التي تعمل على معالجة البيانات محددة الحجم وقد لا تكفي لكل وسائط الاستدعاء. يمكنك متابعة المقالات السابقة في سلسلة تعلم الخورزميات من هنا وهنا.
المصادر
سعدنا بزيارتك، جميع مقالات الموقع هي ملك موقع الأكاديمية بوست ولا يحق لأي شخص أو جهة استخدامها دون الإشارة إليها كمصدر. تعمل إدارة الموقع على إدارة عملية كتابة المحتوى العلمي دون تدخل مباشر في أسلوب الكاتب، مما يحمل الكاتب المسؤولية عن مدى دقة وسلامة ما يكتب.
التعليقات :