العودية في بنية البيانات: كيف تعمل ، أنواعها وعندما تستخدم

نشرت: 2020-05-22

لنبدأ بتعريف العودية في بنية البيانات. سنناقش لاحقًا أنواعًا مختلفة من العودية وكيفية استخدام العودية لحل المشكلات المختلفة.

جدول المحتويات

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

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

يمكن أن تحدث العملية التي تستدعي فيها الوظيفة نفسها بشكل مباشر وغير مباشر. يؤدي هذا الاختلاف في الاستدعاء إلى ظهور أنواع مختلفة من العودية ، والتي سنتحدث عنها بعد قليل. تتضمن بعض المشكلات التي يمكن حلها باستخدام العودية DFS للرسم البياني وأبراج هانوي وأنواع مختلفة من عمليات اجتياز الأشجار وغيرها. للتعرف على العودية ومفاهيم علوم البيانات الأخرى ، تحقق من دورات IIIT-B لعلوم البيانات عبر الإنترنت.

قراءة: 13 فكرة مثيرة للاهتمام لمشروع هيكل البيانات

كيف تعمل العودية؟

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

لا يشترط وجود خبرة في الترميز. 360 درجة الدعم الوظيفي. دبلوم PG في التعلم الآلي والذكاء الاصطناعي من IIIT-B وما فوق.

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

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

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

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

اقرأ أيضًا: أفضل 6 لغات برمجة للتعلم

أنواع العودية

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

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

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

متى يتم استخدام العودية؟

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

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

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

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

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

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

راجع أيضًا: 23 من أفضل دورات برمجة الكمبيوتر للحصول على وظيفة

خاتمة

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

إذا كنت مهتمًا بالتعرف على بنية البيانات وعلوم البيانات ، فراجع برنامج IIIT-B & upGrad's Executive PG في علوم البيانات والذي تم إنشاؤه للمهنيين العاملين ويقدم أكثر من 10 دراسات حالة ومشاريع ، وورش عمل عملية عملية ، وإرشاد مع الصناعة خبراء ، وجهاً لوجه مع مرشدين في الصناعة ، وأكثر من 400 ساعة من التعلم والمساعدة في العمل مع الشركات الكبرى.

ما هو التطبيق الواقعي الأكثر شيوعًا للتكرار؟

العودية هي عملية تستدعي فيها الوظيفة نفسها بشكل غير مباشر أو مباشر من أجل حل المشكلة. تسمى الوظيفة التي تؤدي عملية العودية بالوظيفة العودية. هناك بعض المشكلات التي يمكن حلها بسهولة تامة بمساعدة خوارزمية تكرارية.

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

ما هي الخصائص التي يجب أن تمتلكها الدالة العودية؟

الوظيفة العودية لديها القدرة على الاستمرار في حلقة لا نهائية. هناك نوعان من الخصائص التي يجب تحديدها لأي دالة تكرارية لمنعها من الدخول في حلقة لا نهائية. هم انهم:

1. المعايير الأساسية - يجب أن يكون هناك شرط أساسي واحد محدد مسبقًا. عندما يتم استيفاء هذا المعيار الأساسي ، ستتوقف الوظيفة عن استدعاء نفسها.
2. النهج التدريجي - ينبغي أن تتكون النداءات المتكررة من نهج تدريجي. عندما يتم إجراء مكالمة متكررة للوظيفة ، يجب أن تكون قريبة من الحالة الأساسية.

ما هي مزايا وعيوب العودية؟

بعض مزايا العودية هي أنك تحتاج فقط إلى تعريف الشرط الأساسي والحالة العودية في دالة عودية. هذا يجعل الشفرة بسيطة جدًا وقصيرة مقارنةً بالشفرة التكرارية ، وبعض المشكلات مثل Tree Traversal و Graph هي عودية بطبيعتها.

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