أمثلة على Recursion .. ” الاستدعاء الذاتي في هياكل البيانات “

كتابة: duaa mohe آخر تحديث: 16 سبتمبر 2021 , 04:38

ماهي تقنية الاستدعاء الذاتي Recursion

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

أمثلة على Recursion

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

أمثلة على الطريقة المباشرة بلغة++C

#include <bits/stdc++.h>
using namespace std;
// Assuming n-th disk is bottom disk (count down)
void tower(int n, char sourcePole,
char destinationPole, char auxiliaryPole)
{
// Base case (termination condition)
if(0 == n)
return;
// Move first n-1 disks from source pole
// to auxiliary pole using destination as
// temporary pole
tower(n - 1, sourcePole, auxiliaryPole,
destinationPole);
// Move the remaining disk from source
// pole to destination pole
cout << "Move the disk "<< n << " from " <<
sourcePole <<" to "<< destinationPole << endl;
// Move the n-1 disks from auxiliary (now source)
// pole to destination pole using source pole as
// temporary (auxiliary) pole
tower(n - 1, auxiliaryPole, destinationPole,
sourcePole);
}
// Driver code
int main()
{
tower(3, 'S', 'D', 'A');
return 0;
}
// This code is contributed by SHUBHAMSINGH10

أمثلة على الطريقة المباشرة بلغة الجافا

// Assuming n-th disk is
// bottom disk (count down)
class GFG {
    
static void tower(int n, char sourcePole,
                  char destinationPole, char auxiliaryPole)
{
    // Base case (termination condition)
    if (0 == n)
    return;
    // Move first n-1 disks from source pole
    // to auxiliary pole using destination as
    // temporary pole
    tower(n - 1, sourcePole, auxiliaryPole,
                          destinationPole);
    // Move the remaining disk from source
    // pole to destination pole
    System.out.printf("Move the disk %d from %c to %cn",
                         n, sourcePole, destinationPole);
    // Move the n-1 disks from auxiliary (now source)
    // pole to destination pole using source pole as
    // temporary (auxiliary) pole
    tower(n - 1, auxiliaryPole, destinationPole, sourcePole);
}
public static void main(String[] args)
{
    tower(3, 'S', 'D', 'A');
}
}
// This code is contributed by Smitha Dinesh Semwal.
أمثلة على الطريقة المباشرة بلغة البايثون 3
# Assuming n-th disk is
# bottom disk (count down)
def tower(n, sourcePole, destinationPole, auxiliaryPole):
    # Base case (termination condition)
    if(0 == n):
        return
    
    # Move first n-1 disks
    # from source pole
    # to auxiliary pole
    # using destination as
    # temporary pole
    tower(n-1, sourcePole, auxiliaryPole, destinationPole)
    
    # Move the remaining
    # disk from source
    # pole to destination pole
    print("Move the disk",sourcePole,"from",sourcePole,"to",destinationPole)
    
    # Move the n-1 disks from
    # auxiliary (now source)
    # pole to destination pole
    # using source pole as
    # temporary (auxiliary) pole
    tower(n-1, auxiliaryPole, destinationPole,sourcePole)
# Driver code
[2]tower(3, 'S', 'D', 'A')
ومن الأمثلة على الاستدعاء الذاتي طباعة الأعداد:
فهنا المستخدم يرسم رقم محدد وليكن س ثم يتم طباعة الأرقام من س إلى الرقم 1 بشكل تنازلي، ويكون البرنامج كالتالي:
public void printInt(int i){
if(i == 1){
;System.out.println(1)
}else{
;System.out.println(i)
;printInt(i1)
{{
أما في حالة طباعة الأرقام بشكل تصاعدي فقط يجب عكس آخر سطري الكود ليتم إنتاج الطباعة بشكلها التصاعدي ويكون كالتالي:
{public void printInt(int i)
}if(i == 1)
;System.out.println(1)
}else{
;printInt(i1)
; System.out.println(i)
 {{
ومن الأمثلة على الاستدعاء الذاتي المجموع للعدد س:
فنها يجب أن يتم استدعاء متكرر للـ method نفسه والتي ستقوم بجمع الأعداد من العدد صفر حتى س، وسيتم كتابة البرنامج كالتالي:
}public int SUM(int i)
}if(i == 0)
;return 0
 } else{
;return i + SUM(i 1)
{ {

الاستدعاء الذاتي بلغة c

إن العملية التي تستدعي فيها الوظيفة نفسها تعرف باسم الوظيفة العودية وتسمى بالوظيفة المقابلة، ففي لغة ++c نفهم العودية أكثر عن طريق دالة عاملي والتي تتجلى في:[1]

 f (n) = n * f (n-1) ، الشرط الأساسي: إذا كان n <= 1 ثم f (n) = 1.

فالغرض من العودية هو تقسيم المشكلة إلى مشاكل أصغر حتى تصل إلى الحالة الأساسية، ويتم عن طريق استدعاء دالة عاملية f(n).

أنواع تقنية الاستدعاء الذاتي

إن الاستدعاء الذاتي يتكون من نوعين ويعتمد إذا كانت الوظيفة تستدعي نفسها من داخل نفسها أو تعمل على استداعاء أكثر من وظيفة، وإن نوعي تقنية الاستدعاء الذاتي هما:

-الاستدعاء الذاتي المباشر

وتصنف إلى أربعة أنواع وتتجلى في:

  • استدعاء الذاتي الذيلي Tail Recursion وفيها يتم استداع الدالة لنفسها، ويكون هذا الاستدعاء هو العبارة الأخيرة في الدالة، وبعد أن يتم هذا الاستدعاء لا تؤدي الدالة إلى شيء، وإن هذه الدالة يجب أن تقوم بمعالجة أو تقوم بتنفيذ أي عملية في وقت الاستدعاء.
  •  الاستدعاء الذاتي الرأسي Head Recursion فعندما تستدعي الدالة نفسها حيث أن هذا الاستدعاء يكون العبارة الأولى في الدالة فإن هذا الاستدعاء يعرف باسم الاستدعاء الذاتي الرأسي، وفيه لا تتواجد أي عبارة أو عملية قبل أن يحصل الاستدعاء، ولا تحتاج الدالة إلى أن تقوم بمعالجة أو تنفيذ أي عملية عند الوقت الذي يتم فيه الاستدعاء، وإن جميع العمليات يتم تنفيذها وقت الارجاع.
  • الاستدعاء الذاتي الشجري Tree Recursion وفي هذا الاستدعاء يتم عن طريق استدعاء الدالة لنفسها لأكثر من مرة، فهي على عكس الاستدعاء الذاتي الخطي الذي يتم فيه استدعاء الدالة لنفسها مرة واحدة فقط.
  • الاستدعاء الذاتي الخطي Linear Recursion وهي الدالة التي تقوم من خلال إجراء استدعاء واحد فقط لنفسها، ويتم هذا الاستدعاء في كل مرة يتم فيها تشغيل الدالة.

-الاستدعاء الذاتي الغير مباشر

ويتم في الاستدعاء الذاتي الغير مباشر اتصال أكثر من دالة ببعضهم البعض بشكل دائري، فهو استدعاء إحدى الوظائف نفسها بالشكل الغير مباشر من وظيفة أخرى.[3]

مزايا وخصائص الاستدعاء الذاتي

إن خصائص الاستدعاء الذاتي تتجلى في:

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

بينما مزايا الاستدعاء الذاتي تتجلى في:

  • إنه يجعل البرنامج نظيفاً.
  • يعمل على تقصير التعليمات البرمجية المعقدة والمتداخلة.

بينما مساوئ الاستدعاء الذاتي تتجلى في :

  • من الصعب أن يتم تصحيح الأخطاء.
  • من الصعب أن يتم فهم المنطق.[4]

اترك تعليقاً

لن يتم نشر عنوان بريدك الإلكتروني. الحقول الإلزامية مشار إليها بـ *

زر الذهاب إلى الأعلى
إغلاق