إلى أي مدى تنفذ العودية في وظيفتك في C ++؟

Question

لقد كتبت وظائف متكررة مع إرشادات صديق يقوم بتدريسني C ++ (كلغة أولى). ومع ذلك، أنا لا أفهم حقا ما يجري. لقد ساعدني (وكذلك المجتمع، كذلك) اكتب وظيفة فرز الدمج.

std::vector<int> mergeSort(std::vector<int> original)

//code here to create two vectors, farray and sarray, out of the 
//original std::vector<int> original ; each is half the length,
//note: if the size % 2 != 0, sarray takes the odd int

farray = mergeSort(farray);
sarray = mergeSort(sarray);

//code here merges the two into a single, final sorted std::vector   

في هذه الوظيفة، قمت بتعيين:

farray = mergeSort(farray);
sarray = mergeSort(sarray);

ما يحدث بالضبط هنا؟ يستدعي Mergesort مع Farray و Sarray كمعلمات ويغير القيمة. إلى أي مدى تنفذ Mergesort في نفسه بشكل متكرر؟ فقط حتى دعوة الدالة العودية؟

Answer 1

في كل مرة تسمون فيها وظيفة متكررة، فإنها تجعل نسخة جديدة بفعالية من المعلومات التي يحتاجها، وتستمر.

يمكن أن يكون لديك برنامج يتكرر "بلا حدود"، أي حتى ينفد من الموارد، وعادة ما تكدس مساحة - المساحة التي تسير فيها تلك النسخ. من شأنها أن تبدو

void recur(){
    recur();
}

int main(){
    recur();
    exit(0); /* won't ever really get here.*/
}

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

#include <iostream>
using namespace std;
void recurSome(int count){
    cout << "RecurSome called with " << count << endl;
    if (count > 0){
        recurSome(count-1);
        cout << "Back at " << count << endl;
    }else{
        cout << "Bottom." << endl;
    }
    return;
}

int main(){
    recurSome(10);
    exit(0);  /* now it will get here. */
}

إذا قمت بتجميعها وتشغيل ذلك، فقل مع:

bash $ g++ -Wall -o rc recursome.cpp
bash $ ./rc

سوف تحصل على النتائج:

RecurSome called with 10
RecurSome called with 9
RecurSome called with 8
RecurSome called with 7
RecurSome called with 6
RecurSome called with 5
RecurSome called with 4
RecurSome called with 3
RecurSome called with 2
RecurSome called with 1
RecurSome called with 0
Bottom.
Back at 1
Back at 2
Back at 3
Back at 4
Back at 5
Back at 6
Back at 7
Back at 8
Back at 9
Back at 10
bash $ 

انظر كيف يتم استدعاؤه لمدة 10، ثم 9، وهلم جرا، ثم بعد أن يصل إلى الأسفل، يظهر أنه يعود إلى 1، ثم 2، وهلم جرا حتى 10؟

القاعدة الأساسية هي أن كل يجب أن يكون لدى الوظيفة العودية شيئا يجعل القضية الأساسية، والتي يفعل اتصل بنفسها مرة أخرى. في هذا واحد، القضية الأساسية هي count == 0 وفي الواقع يمكننا أن نكتتبه هذا كتعريف متكرر

Recursome:
إذا c = 0: أسفل الطباعة
إذا c> 0: عدد الطباعة، وتصلب (C-1)

سترى العديد من التعريفات العودية لهذا النوع كما تنتقل في الرياضيات.

إليك نسخة Niftier C Niftier مع إخراج أفضل:

#include <stdio.h>
#include <stdlib.h>

int max = 10;

void recurSome(int count){
    printf("RecurSome %*c Called with %d\n", max-count+1, ' ', count);
    if (count > 0){
        recurSome(count-1);
        printf("RecurSome %*c Back at %d\n", max-count+1, ' ', count);
    }else{
        printf("RecurSome %*c Bottom.\n", 2*max, ' ');
        printf("RecurSome %*c Back at %d\n", max-count+1, ' ', count);
    }
    return;
}

int main(){
    recurSome(max);
    exit(0);  /* now it will get here. */
}

انتاج:

RecurSome   Called with 10
RecurSome    Called with 9
RecurSome     Called with 8
RecurSome      Called with 7
RecurSome       Called with 6
RecurSome        Called with 5
RecurSome         Called with 4
RecurSome          Called with 3
RecurSome           Called with 2
RecurSome            Called with 1
RecurSome             Called with 0
RecurSome                      Bottom.
RecurSome             Back at 0
RecurSome            Back at 1
RecurSome           Back at 2
RecurSome          Back at 3
RecurSome         Back at 4
RecurSome        Back at 5
RecurSome       Back at 6
RecurSome      Back at 7
RecurSome     Back at 8
RecurSome    Back at 9
RecurSome   Back at 10

Answer 2

تحقق من ذلك في القاموس:

العودية: اسم. يرى العودية

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

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

كمثال بسيط، حساب قوة N N اتصالا لعدد صحيح معين، يمكن أن أكون وظيفة power( int number, int power ). وبعد كيف يمكنك تنفيذها؟ بطرق عدة. أبسط كونها مكالمة إلى مكتبة، تليها حلقة، أو يمكنك تحديد الوظيفة من حيث نفسه:

int power( int number, unsigned int pow )
{
   // Basic trivial case, cuts the recursion:
   if ( pow == 0 ) return 1;

   // Implement power in terms of itself:
   return number * power( number, pow-1 );
}
int main()
{
   int power = power( 2, 10 );
}

لقد حددنا الوظيفة من حيث نفسها. تبدأ مع أكثر الحالة الأساسية (n ^ 0 = 1). إذا لم نكن في أبسط القضية، فيمكنك التعبير عن خوارزمية الخاص بك من حيث نفسها.

سيبدأ البرنامج في الدعوة الرئيسية power( 2, 10 ) من شأنه أن ينص على الاستدعاء power( 2, 9 ) تقليل المشكلة إلى الأصغر المشكلة وسوف تؤكل بعد ذلك الإجابة النهائية من حيث المشكلة الأكثر بساطة.

ستكون تتبع استدعاء actuall:

power( 2, 5 )
  power( 2, 4 )
    power( 2, 3 )
      power( 2, 2 )
        power( 2, 1 )
          power( 2, 0 )    // simplest case: return 1
        return 2 * 1 -> 2  // obtain next solution in terms of previous
      return 2 * 2 -> 4
    return 2 * 4 -> 8
  return 2 * 8 -> 16
return 2 * 16 -> 32

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

Answer 3

يمكن فهم العودية كتطبيق عملي لمبدأ التعريفي. لإثبات بيان p (n) للجميع n where p (n) يعني "مجموع الأعداد الصحيحة من 1 إلى n هو n (n + 1) / 2" علينا أن نثبت شيئين:

1. حالة قاعدة: ص (ن) يحمل لعدد صحيح معين. ص (1) صحيح لأن 1 = 1 (1 + 1) / 2.
2. حالة حثية: إذا كان P (n) صحيحا، يجب أن يكون P (n + 1) صحيحا. 1 + ... + N + (N + 1) = n (n + 1) / 2 + (n + 1) = n (n + 1) / 2 + 2 (n + 1) / 2 = (n + 1) ((n + 1) +1) / 2، وهو الإخصام p (n + 1).

وبالمثل، في وظيفة متكررة مثل Mergesort، نحتاج إلى التعامل مع حالتين:

1. حالة قاعدة: إذا كان الصفيف عنصر واحد، يتم فرزه؛ غير ذلك
2. القضية العودية: قم بتقسيم الصفيف إلى صفيفين أصغرين، ويرتفع كل منها، ودمجها معا.

المفتاح هو أن صفيفين هي الأصغر من الأصل، وإلا فلن يصل أحدهم إلى القضية الأساسية. نظرا لأن المصفوفات تقسيم تقريبا إلى النصف تقريبا، فستكون عمق العودية حول log2 (n) في هذه الحالة.

بقدر ما يذهب القانون في السؤال، هناك ثلاثة مشاكل:

1. القضية الأساسية مفقودة.
2. إعادة استخدام المتغيرات Farray و Sarray ليست ضرورية بدقة وقد تكون مربكة.
3. سيكون الرمز بطيئا جدا بسبب عدد ناقلات STD :: ناقوها التي يتم إنشاؤها وتدميرها. أفضل واجهة ل mergesort تأخذ اثنين من ناقلات :: محاصرات كمدخل، على غرار وظيفة STD :: فرز ().

يجب على المبرمجين الجدد محاولة تشغيل مدمج مع الورق والقلم الرصاص.

Answer 4

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

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

يمكنك التعامل مع هذا عن طريق فحص حجم Farray و Sarray ويقرر ما إذا كنت تريد الاتصال بالدماء () في إما أو كليهما قبل الجمع بينها وإعادة التركيبة.

ماذا لو كان لدى المرء عنصرين واحدا 1؟ استدعاء Mergesort () على الحجم 2 ولكن ليس على الحجم 1.

عند إجراء مكالمة إلى Mergesort () لا تتصل بالدماء () إما على Farray أو Sarray قبل العودة، ستبدأ العودية بالتراجع.

Answer 5

إلقاء نظرة على صفحة ويكيبيديا ل دمج فرز للحصول على معلومات إضافية حول ما تحاول القيام به.

كإصدار Sidenote، كن على علم بأنك تقوم بنسخة من كل ناقل تعطى كمعلمة. استخدام ناقلات <> const & بدلا من ذلك.