ما هو العودية ومتى يجب أن أستخدمه؟

Question

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

لذا فإن السؤال هو:

1. ما هو العودية؟
2. متى يمكنني استخدام العودية؟
3. لماذا لا يستخدم الناس العودية؟

Answer 1

هناك عدد من التفسيرات الجيدة ل العودية في هذا الموضوع، تدور هذه الإجابة حول سبب عدم استخدامه في معظم اللغات.* في غالبية تطبيقات اللغة الحتمية الرئيسية (أي.كل التطبيقات الرئيسية لـ C وC++ وBasic وPython وRuby وJava وC#) تكرار هو أفضل إلى حد كبير من العودية.

لمعرفة السبب، اتبع الخطوات التي تستخدمها اللغات المذكورة أعلاه لاستدعاء دالة:

1. تم نحت الفضاء على المدخنة لوسائط الدالة والمتغيرات المحلية
2. يتم نسخ وسائط الوظيفة إلى هذه المساحة الجديدة
3. يقفز التحكم إلى الوظيفة
4. يتم تشغيل رمز الوظيفة
5. يتم نسخ نتيجة الدالة إلى قيمة الإرجاع
6. يتم إرجاع المكدس إلى موضعه السابق
7. يعود عنصر التحكم إلى المكان الذي تم استدعاء الوظيفة فيه

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

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

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

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

** بالمناسبة يا ماريو، الاسم النموذجي لوظيفة ArrangeString هو "الانضمام"، وسأفاجأ إذا لم يكن للغة التي تختارها تطبيق لها بالفعل.

Answer 2

مثال إنجليزي بسيط للتكرار

A child couldn't sleep, so her mother told her a story about a little frog,
    who couldn't sleep, so the frog's mother told her a story about a little bear,
         who couldn't sleep, so the bear's mother told her a story about a little weasel... 
            who fell asleep.
         ...and the little bear fell asleep;
    ...and the little frog fell asleep;
...and the child fell asleep.

Answer 3

بالمعنى الأساسي لعلوم الكمبيوتر، العودية هي وظيفة تطلق على نفسها.لنفترض أن لديك بنية قائمة مرتبطة:

struct Node {
    Node* next;
};

وتريد معرفة مدة القائمة المرتبطة التي يمكنك القيام بذلك من خلال التكرار:

int length(const Node* list) {
    if (!list->next) {
        return 1;
    } else {
        return 1 + length(list->next);
    }
}

(يمكن القيام بذلك بالطبع باستخدام حلقة for أيضًا، ولكنه مفيد كتوضيح للمفهوم)

Answer 4

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

أبسط مثال هو التكرار الخلفي حيث يكون السطر الأخير من الوظيفة عبارة عن استدعاء لنفسها:

int FloorByTen(int num)
{
    if (num % 10 == 0)
        return num;
    else
        return FloorByTen(num-1);
}

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

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

يمكنك رسم واحدة منها بكل بساطة باستخدام التكرار، حيث تتفرع مكدس الاستدعاءات في ثلاثة اتجاهات:

private void BuildVertices(double x, double y, double len)
{
    if (len > 0.002)
    {
        mesh.Positions.Add(new Point3D(x, y + len, -len));
        mesh.Positions.Add(new Point3D(x - len, y - len, -len));
        mesh.Positions.Add(new Point3D(x + len, y - len, -len));
        len *= 0.5;
        BuildVertices(x, y + len, len);
        BuildVertices(x - len, y - len, len);
        BuildVertices(x + len, y - len, len);
    }
}

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

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

خاتمة

من الناحية العملية، يكون التكرار أكثر منطقية عندما تحتاج إلى التفرع التكراري.

Answer 5

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

المثال المتعارف عليه هو إجراء روتيني لإنشاء مضروب n.يتم حساب مضروب n بضرب كافة الأرقام بين 1 و n.يبدو الحل التكراري في C# كما يلي:

public int Fact(int n)
{
  int fact = 1;

  for( int i = 2; i <= n; i++)
  {
    fact = fact * i;
  }

  return fact;
}

ليس هناك ما يثير الدهشة بشأن الحل التكراري ويجب أن يكون منطقيًا لأي شخص مطلع على لغة C#.

تم العثور على الحل العودي من خلال إدراك أن العامل n هو n * Fact(n-1).أو بعبارة أخرى، إذا كنت تعرف ما هو الرقم العاملي المعين، فيمكنك حساب الرقم التالي.إليك الحل العودي في C#:

public int FactRec(int n)
{
  if( n < 2 )
  {
    return 1;
  }

  return n * FactRec( n - 1 );
}

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

عند مواجهته لأول مرة، يمكن أن يكون هذا أمرًا مربكًا نوعًا ما، لذا من المفيد فحص كيفية عمله عند التشغيل.تخيل أننا نسمي FactRec(5).نحن ندخل في الروتين، ولا يتم التقاطنا بواسطة الحالة الأساسية وبالتالي ينتهي بنا الأمر على النحو التالي:

// In FactRec(5)
return 5 * FactRec( 5 - 1 );

// which is
return 5 * FactRec(4);

إذا أعدنا إدخال الطريقة باستخدام المعلمة 4، فلن يتم إيقافنا مرة أخرى بواسطة شرط الحماية وبالتالي سينتهي بنا الأمر إلى:

// In FactRec(4)
return 4 * FactRec(3);

إذا قمنا باستبدال قيمة الإرجاع هذه في قيمة الإرجاع أعلاه نحصل عليها

// In FactRec(5)
return 5 * (4 * FactRec(3));

من المفترض أن يمنحك هذا فكرة عن كيفية التوصل إلى الحل النهائي، لذلك سنقوم بتتبع كل خطوة سريعًا وإظهارها في الطريق إلى الأسفل:

return 5 * (4 * FactRec(3));
return 5 * (4 * (3 * FactRec(2)));
return 5 * (4 * (3 * (2 * FactRec(1))));
return 5 * (4 * (3 * (2 * (1))));

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

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

Answer 6

العودية هي حل مشكلة مع وظيفة تستدعي نفسها.وخير مثال على ذلك هو وظيفة مضروب.المضروب هو مسألة رياضية حيث مضروب 5، على سبيل المثال، هو 5 * 4 * 3 * 2 * 1.تحل هذه الوظيفة هذه المشكلة في C# للأعداد الصحيحة الموجبة (لم يتم اختبارها - قد يكون هناك خطأ).

public int Factorial(int n)
{
    if (n <= 1)
        return 1;

    return n * Factorial(n - 1);
}

Answer 7

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

على سبيل المثال، لحساب مضروب للرقم X, ، يمكن للمرء أن يمثلها على أنها X times the factorial of X-1.وبالتالي، فإن الطريقة "تتكرر" للعثور على مضروب X-1, ، ثم يضاعف كل ما حصل عليه X لإعطاء إجابة نهائية.وبطبيعة الحال، للعثور على مضروب X-1, ، سيتم أولاً حساب مضروب X-2, ، وما إلى ذلك وهلم جرا.الحالة الأساسية ستكون متى X هو 0 أو 1، وفي هذه الحالة يعرف العودة 1 منذ 0! = 1! = 1.

Answer 8

النظر في مشكلة قديمة ومعروفة:

في الرياضيات، القاسم المشترك الأكبر (gcd) … لعددين أو أكثر من الأعداد الصحيحة غير الصفرية، هو أكبر عدد صحيح موجب يقسم الأعداد بدون باقي.

تعريف gcd بسيط بشكل مدهش:

حيث وزارة الدفاع هو مشغل الوحدة النمطية (أي الباقي بعد قسمة الأعداد الصحيحة).

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

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

لنحسب gcd(10, 8) كمثال.كل خطوة تساوي التي قبلها:

1. جي سي دي (10، 8)
2. جي سي دي (10، 10 مود 8)
3. جي سي دي (8، 2)
4. جي سي دي (8، 8 مود 2)
5. جي سي دي (2، 0)
6. 2

في الخطوة الأولى، 8 لا يساوي الصفر، لذلك ينطبق الجزء الثاني من التعريف.10 mod 8 = 2 لأن 8 تدخل في 10 مرة واحدة مع وجود 2 متبقية.في الخطوة 3، ينطبق الجزء الثاني مرة أخرى، ولكن هذه المرة 8 mod 2 = 0 لأن 2 يقسم 8 بدون باقي.في الخطوة 5، الوسيطة الثانية هي 0، وبالتالي فإن الإجابة هي 2.

هل لاحظت أن gcd يظهر على الجانبين الأيمن والأيسر من علامة التساوي؟قد يقول عالم الرياضيات أن هذا التعريف متكرر لأن التعبير الذي تحدده يتكرر داخل تعريفه.

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

sum l =
    if empty(l)
        return 0
    else
        return head(l) + sum(tail(l))

أين head هو العنصر الأول في القائمة و tail هي بقية القائمة.لاحظ أن sum يتكرر داخل تعريفه في النهاية.

ربما تفضل القيمة القصوى في القائمة بدلاً من ذلك:

max l =
    if empty(l)
        error
    elsif length(l) = 1
        return head(l)
    else
        tailmax = max(tail(l))
        if head(l) > tailmax
            return head(l)
        else
            return tailmax

يمكنك تعريف ضرب الأعداد الصحيحة غير السالبة بشكل متكرر لتحويلها إلى سلسلة من الإضافات:

a * b =
    if b = 0
        return 0
    else
        return a + (a * (b - 1))

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

دمج الفرز لديه تعريف متكرر جميل:

sort(l) =
    if empty(l) or length(l) = 1
        return l
    else
        (left,right) = split l
        return merge(sort(left), sort(right))

التعريفات العودية موجودة في كل مكان إذا كنت تعرف ما الذي تبحث عنه.لاحظ كيف أن كل هذه التعريفات تحتوي على حالات أساسية بسيطة جدًا، على سبيل المثال, جي سي دي(م, 0) = م.الحالات العودية تقلل من المشكلة للوصول إلى الإجابات السهلة.

مع هذا الفهم، يمكنك الآن تقدير الخوارزميات الأخرى الموجودة فيها مقالة ويكيبيديا عن العودية!

Answer 9

1. دالة تطلق على نفسها
2. عندما يمكن (بسهولة) تقسيم الوظيفة إلى عملية بسيطة بالإضافة إلى نفس الوظيفة في جزء أصغر من المشكلة.يجب أن أقول، بدلاً من ذلك، أن هذا يجعله مرشحًا جيدًا للتكرار.
3. إنهم يفعلون!

المثال القانوني هو العامل الذي يبدو كما يلي:

int fact(int a) 
{
  if(a==1)
    return 1;

  return a*fact(a-1);
}

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

Answer 10

الدالة العودية هي التي تستدعي نفسها.السبب الأكثر شيوعًا الذي وجدته لاستخدامه هو اجتياز هيكل الشجرة.على سبيل المثال، إذا كان لدي TreeView يحتوي على مربعات اختيار (فكر في تثبيت برنامج جديد، أو صفحة "اختيار الميزات لتثبيتها")، فقد أرغب في الحصول على زر "تحديد الكل" والذي سيكون شيئًا مثل هذا (الكود الكاذب):

function cmdCheckAllClick {
    checkRecursively(TreeView1.RootNode);
}

function checkRecursively(Node n) {
    n.Checked = True;
    foreach ( n.Children as child ) {
        checkRecursively(child);
    }
}

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

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

لا أستطيع التفكير في سبب يمنع الناس من استخدامه، عندما يكون ذلك مناسبًا.إنه مفيد في بعض الظروف، وليس في حالات أخرى.

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

Answer 11

العودية هو تعبير يشير إلى نفسه بشكل مباشر أو غير مباشر.

النظر في الاختصارات العودية كمثال بسيط:

• جنو تمثل جنو ليس يونكس
• بي أتش بي تمثل بي أتش بي:المعالج المسبق للنص التشعبي
• يامل تمثل YAML ليست لغة ترميزية
• خمر تمثل النبيذ ليس محاكياً
• تأشيرة تمثل جمعية خدمة التأشيرة الدولية

مزيد من الأمثلة على ويكيبيديا

Answer 12

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

يتجنب الناس التكرار لعدة أسباب:

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

2. أولئك منا الذين اكتسبوا مهارات البرمجة في البرمجة الإجرائية أو الموجهة للكائنات غالبًا ما يُطلب منهم تجنب التكرار لأنه عرضة للخطأ.

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

4. بالنسبة لاثنين على الأقل من لغات البرمجة التي استخدمتها، أتذكر أنني سمعت توصيات بعدم استخدام العودية إذا تجاوزت عمقًا معينًا لأن مجموعتها ليست بهذا العمق.

Answer 13

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

على سبيل المثال، خذ مضروبا:

factorial(6) = 6*5*4*3*2*1

لكن من السهل رؤية المضروب (6) أيضًا:

6 * factorial(5) = 6*(5*4*3*2*1).

بشكل عام:

factorial(n) = n*factorial(n-1)

بالطبع، الشيء الصعب في التكرار هو أنه إذا كنت تريد تعريف الأشياء من حيث ما قمت به بالفعل، فيجب أن يكون هناك مكان ما للبدء.

في هذا المثال، قمنا فقط بعمل حالة خاصة من خلال تعريف العامل (1) = 1.

والآن نراها من الأسفل إلى الأعلى:

factorial(6) = 6*factorial(5)
                   = 6*5*factorial(4)
                   = 6*5*4*factorial(3) = 6*5*4*3*factorial(2) = 6*5*4*3*2*factorial(1) = 6*5*4*3*2*1

وبما أننا حددنا المضروب (1) = 1، فقد وصلنا إلى "القاع".

بشكل عام، تتكون الإجراءات العودية من جزأين:

1) الجزء العودي، الذي يحدد بعض الإجراءات من حيث المدخلات الجديدة المدمجة مع ما "قمت به بالفعل" عبر نفس الإجراء.(أي. factorial(n) = n*factorial(n-1))

2) الجزء الأساسي، الذي يضمن عدم تكرار العملية إلى الأبد من خلال إعطائها مكانًا للبدء (أي. factorial(1) = 1)

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

أتمنى أن يساعدك هذا...

Answer 14

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

تعجبني أيضًا مناقشة Steve McConnells حول العودية في Code Complete حيث ينتقد الأمثلة المستخدمة في كتب علوم الكمبيوتر حول العودية.

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

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

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

يحرر:لم يكن هذا بحثًا في إجابة داف - لم أر هذا الرد عندما نشرت هذا

Answer 15

1.) طريقة متكررة إذا استطاعت أن تسمي نفسها ؛إما مباشرة:

void f() {
   ... f() ... 
}

أو بشكل غير مباشر:

void f() {
    ... g() ...
}

void g() {
   ... f() ...
}

2.) متى تستخدم العودية

Q: Does using recursion usually make your code faster? 
A: No.
Q: Does using recursion usually use less memory? 
A: No.
Q: Then why use recursion? 
A: It sometimes makes your code much simpler!

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

Answer 16

إليك مثال بسيط:كم عدد العناصر في المجموعة.(هناك طرق أفضل لحساب الأشياء، ولكن هذا مثال عودي بسيط ولطيف.)

أولا، نحتاج إلى قاعدتين:

1. إذا كانت المجموعة فارغة، فإن عدد العناصر في المجموعة هو صفر (دوه!).
2. إذا لم تكن المجموعة فارغة، يكون العدد واحدًا بالإضافة إلى عدد العناصر في المجموعة بعد إزالة عنصر واحد.

لنفترض أن لديك مجموعة مثل هذا:[س س س].دعونا نحسب عدد العناصر الموجودة.

1. المجموعة هي [x x x] وهي ليست فارغة، لذلك نطبق القاعدة 2.عدد العناصر هو واحد بالإضافة إلى عدد العناصر في [x x] (أي.لقد قمنا بإزالة عنصر).
2. المجموعة هي [x x]، لذلك نطبق القاعدة 2 مرة أخرى:واحد + عدد العناصر في [x].
3. المجموعة هي [x]، والتي لا تزال تطابق القاعدة 2:واحد + عدد العناصر في [].
4. الآن المجموعة هي []، والتي تطابق القاعدة 1:العدد صفر!
5. الآن بعد أن عرفنا الإجابة في الخطوة 4 (0)، يمكننا حل الخطوة 3 (1 + 0)
6. وبالمثل، الآن بعد أن عرفنا الإجابة في الخطوة 3 (1)، يمكننا حل الخطوة 2 (1 + 1)
7. وأخيرًا الآن بعد أن عرفنا الإجابة في الخطوة 2 (2)، يمكننا حل الخطوة 1 (1 + 2) والحصول على عدد العناصر في [x x x]، وهو 3.مرحا!

يمكننا تمثيل ذلك على النحو التالي:

count of [x x x] = 1 + count of [x x]
                 = 1 + (1 + count of [x])
                 = 1 + (1 + (1 + count of []))
                 = 1 + (1 + (1 + 0)))
                 = 1 + (1 + (1))
                 = 1 + (2)
                 = 3

عند تطبيق حل عودي، عادةً ما يكون لديك قاعدتان على الأقل:

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

إذا قمنا بترجمة ما سبق إلى كود زائف، نحصل على:

numberOfItems(set)
    if set is empty
        return 0
    else
        remove 1 item from set
        return 1 + numberOfItems(set)

هناك الكثير من الأمثلة المفيدة (عبور شجرة، على سبيل المثال) والتي أنا متأكد من أن الآخرين سيغطيونها.

Answer 17

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

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

Answer 18

مثال:التعريف العودي للدرج هو:يتكون الدرج من :- خطوة واحدة وسلالم (عودة) - أو خطوة واحدة فقط (إنهاء)

Answer 19

للتكرار على مشكلة تم حلها:لا تفعل شيئًا، لقد انتهيت.
للعودة إلى مشكلة مفتوحة:قم بالخطوة التالية، ثم كرر الباقي.

Answer 20

في سهل الانجليزية:افترض أنه يمكنك القيام بثلاثة أشياء:

1. خذ تفاحة واحدة
2. اكتب علامات العد
3. عد علامات العد

لديك الكثير من التفاح أمامك على الطاولة، وتريد أن تعرف عدد التفاحات الموجودة.

start
  Is the table empty?
  yes: Count the tally marks and cheer like it's your birthday!
  no:  Take 1 apple and put it aside
       Write down a tally mark
       goto start

عملية تكرار نفس الشيء حتى تنتهي تسمى العودية.

آمل أن تكون هذه هي الإجابة "باللغة الإنجليزية البسيطة" التي تبحث عنها!

Answer 21

الدالة العودية هي دالة تحتوي على استدعاء لنفسها.البنية العودية هي بنية تحتوي على مثيل لنفسها.يمكنك الجمع بين الاثنين كفئة متكررة.الجزء الأساسي من العنصر العودي هو أنه يحتوي على مثيل/استدعاء لنفسه.

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

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

Answer 22

هذا سؤال قديم، ولكني أريد إضافة إجابة من وجهة نظر لوجستية (أي ليس من وجهة نظر صحة الخوارزمية أو وجهة نظر الأداء).

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

وبالتالي، غالبًا ما أتجنب العودية، وأستخدم عملية المكدس بدلاً من ذلك، لأن العودية نفسها هي في الأساس عملية مكدس.

Answer 23

تريد استخدامه في أي وقت يكون لديك فيه هيكل شجرة.إنه مفيد جدًا في قراءة XML.

Answer 24

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

Answer 25

"إذا كان لدي مطرقة، اجعل كل شيء يبدو وكأنه مسمار."

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

مثال

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

1. يقسم: انشر كل الأوراق، بحيث يكون لديك ورقة واحدة فقط في كل "كومة".
2. يغزو:
   2. قم بالتجول، وضع كل ورقة فوق ورقة أخرى.لديك الآن أكوام من 2.
   3. قم بالتجول، وضع كل مجموعتين فوق مجموعتين أخريين.لديك الآن أكوام من 4.
   4. قم بالتجول، وضع كل 4 كومة فوق 4 كومة أخرى.لديك الآن أكوام من 8.
   5. ...مرارا وتكرارا ...
   6. لديك الآن مجموعة ضخمة من 1024 ورقة!

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

Answer 26

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

Answer 27

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

لنفترض أن لديك ثلاثة مديرين - جاك وجون ومورجان.يدير جاك مبرمجين اثنين، جون - 3، ومورجان - 5.ستمنح كل مدير 300 دولار وتريد أن تعرف تكلفة ذلك.الجواب واضح - ولكن ماذا لو كان اثنان من موظفي Morgan مديرين أيضًا؟

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

لن تعرف أبدًا عدد الدورات التي ستستغرقها قبل الحصول على إجابة، على الرغم من أنك تعرف عدد المديرين لديك وعدد الميزانية التي يمكنك إنفاقها.

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

Answer 28

في اللغة الإنجليزية البسيطة، العودية تعني تكرار شيء ما مرارًا وتكرارًا.

أحد الأمثلة في البرمجة هو استدعاء الدالة داخل نفسها.

انظر إلى المثال التالي لحساب مضروب الرقم:

public int fact(int n)
{
    if (n==0) return 1;
    else return n*fact(n-1)
}

Answer 29

يعرض أي خوارزمية الهيكلي العودية على نوع البيانات إذا كانت تتكون أساسًا من عبارة تبديل مع حالة لكل حالة من حالات نوع البيانات.

على سبيل المثال، عندما تعمل على نوع ما

  tree = null 
       | leaf(value:integer) 
       | node(left: tree, right:tree)

سيكون للخوارزمية العودية الهيكلية الشكل

 function computeSomething(x : tree) =
   if x is null: base case
   if x is leaf: do something with x.value
   if x is node: do something with x.left,
                 do something with x.right,
                 combine the results

هذه هي الطريقة الأكثر وضوحًا لكتابة أي خوارزمية تعمل على بنية البيانات.

الآن، عندما تنظر إلى الأعداد الصحيحة (حسنًا، الأعداد الطبيعية) كما تم تعريفها باستخدام بديهيات بيانو

 integer = 0 | succ(integer)

ترى أن الخوارزمية العودية الهيكلية على الأعداد الصحيحة تبدو هكذا

 function computeSomething(x : integer) =
   if x is 0 : base case
   if x is succ(prev) : do something with prev

تدور الوظيفة العليا المعروفة للغاية حول مثال تافهة لهذا النموذج.

Answer 30

استدعاء الدالة نفسها أو استخدام التعريف الخاص بها.