مفهوم التعاود (Recursion) والكائنات القابلة للاستدعاء (Callable Objects) في Cpp

تطبيقات على التعاود

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

حساب تسلسلات فيبوناتشي Fibonnaci sequence

هذه هي الطريقة الأبسط لاستخدام التكرارية للحصول على العنصر رقم N من سلسلة Fibonnaci:

int get_term_fib(int n) {
    if (n == 0)
        return 0;
    if (n == 1)
        return 1;
    return get_term_fib(n - 1) + get_term_fib(n - 2);
}

لكن المشكلة في هذه الطريقة أنّها غير مناسبة للأعداد الكبيرة، فكلما زادت قيمة ‎n‎، زاد عدد استدعاءات الدالة بشكل أسي (exponentially). يمكن الاستعاضة عن هذه الطريقة بالتكرارية المُذيّلة (tail recursion) على النحو التالي:

int get_term_fib(int n, int prev = 0, int curr = 1) {
    if (n == 0)
        return prev;
    if (n == 1)
        return curr;
    return get_term_fib(n - 1, curr, prev + curr);
}

سيحسُب كل استدعاء للدالّة الحدّ التالي في تسلسل Fibonnaci، وعليه فإنّ عدد استدعاءات الدالّة يزيد خطيًا مع ‎n‎.

التكرارية مع التذكّر Recursion with memoization

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

يوضّح المثال التالي كيفية حساب تسلسل فيبوناتشي باستخدام التكرارية التذكيرية:

#include <map>

int fibonacci(int n) {
    static std::map < int, int > values;
    if (n == 0 || n == 1)
        return n;
    std::map<int,int>::iterator iter = values.find(n);
    if (iter == values.end()) {
        return values[n] = fibonacci(n - 1) + fibonacci(n - 2);
    } else {
        return iter->second;
    }
}

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

#include <map>
int fibonacci(int n, std::map<int, int> values)
{
    if (n==0 || n==1)
        return n;
    std::map<int,int>::iterator iter = values.find(n);
    if (iter == values.end())
    {
        return values[n] = fibonacci(n-1) + fibonacci(n-2);
    }
    else
    {
        return iter->second;
    }
}

في هذا المثال، يُطلَب من المُستدعي أن يحفظ القاموس الذي يحتوي القيم المُخزّنة. ميزة هذا أنّ الدالّة أصبحت الآن متعدّدة المداخل (reentrant)، وأنّه المستدعي يستطيع إزالة القيم التي لم تعد مطلوبة، وهذا يحسّن استخدام الذاكرة. بالمقابل، يعيب هذه الطريقة أنّها تكسر التغليف (breaks encapsulation). إذ يمكن للمُستدعي تغيير الخرج عن طريق ملء القاموس بقيم غير صحيحة.

الكائنات القابلة للاستدعاء Callable Objects

الكائنات القابلة للاستدعاء هي هياكل C++‎ يمكن استخدامها كدوال، وتدخل فيها كل الأشياء التي يمكنك تمريرها إلى دالة المكتبة القياسية في C++‎ 17‏ invoke()‎ أو التي يمكن استخدامها في مُنشئ std::function، وهذا يشمل: مؤشّرات الدوال، والأصناف التي تحتوي على operator()‎، والأصناف ذات التحويلات الضمنية، ومراجع الدوال، ومؤشّرات الدوال التابعة ومؤشّرات الحقول (Pointers to member data)، وتعابير لامبدا.

تُستخدَم الكائنات القابلة للاستدعاء في العديد من خوارزميات مكتبة القوالب القياسية STL كدوال شرطية (predicate).

مؤشّرات الدوال Function Pointers

تعدّ مؤشّرات الدوال الطريقة الأبسط لتمرير الدوال، ويمكن استخدامها أيضًا في لغة C، وإن أردت استخدامها ككائنات قابلة للاستدعاء، فيمكنك تعريف مؤشّر الدالّة على النحو التالي:

typedef returnType(*name)(arguments); // All
using name = returnType(*)(arguments); // <= C++11
using name = std::add_pointer<returnType(arguments)>::type; // <= C++11
using name = std::add_pointer_t<returnType(arguments)>; // <= C++14

يستخدم المثال التالي مؤشّر دالة لكتابة دالة مخصّصة لترتيب المتجهات:

using LessThanFunctionPtr = std::add_pointer_t<bool(int, int)>;
void sortVectorInt(std::vector<int>&v, LessThanFunctionPtr lessThan) {
    if (v.size() < 2)
        return;
    if (v.size() == 2) {
        if (!lessThan(v.front(), v.back())) // استدعاء مؤشر الدالة
            std::swap(v.front(), v.back());
        return;
    }
    std::sort(v, lessThan);
}
bool lessThanInt(int lhs, int rhs) {
    return lhs < rhs;
}
sortVectorInt(vectorOfInt, lessThanInt); // تمرير المؤشر إلى دالة حرّة
struct GreaterThanInt {
    static bool cmp(int lhs, int rhs) {
        return lhs > rhs;
    }
};
sortVectorInt(vectorOfInt, &GreaterThanInt::cmp); // تمرير المؤشر إلى دالة تابعة ساكن

كان بإمكاننا استدعاء مؤشّر الدالّة بدلًا من ذلك، بإحدى الطرق التالية :

(*lessThan)(v.front(), v.back())
std::invoke(lessThan, v.front(), v.back()) // <= C++17

الأصناف ذات التابع operator()‎‏ (الكائنات الداليّة Functors)

يمكن استخدام كل الأصناف التي تحمّل ‎operator()‎ تحميلًا زائدًا ككائنات دوال، ويمكن كتابة هذه الأصناف يدويًا (يشار إليها غالبًا باسم الكائنات الدالية - functors)، أو إنشاؤها تلقائيًا بواسطة المُصرِّف عن طريق كتابة تعابير لامدا (منذ C++‎ 11 وما بعده).

struct Person {
    std::string name;
    unsigned int age;
};
// كائن دالي، يعثر على الشخص باسمه
struct FindPersonByName {
    FindPersonByName(const std::string &name) : _name(name) {}
    // التابع المزاد تحميله والذي سيُستدعى
    bool operator()(const Person &person) const {
        return person.name == _name;
    }
    private:
        std::string _name;
};
std::vector<Person> v; // نفترض أنّه يحتوي البيانات
std::vector<Person>::iterator iFind =
    std::find_if(v.begin(), v.end(), FindPersonByName("Foobar"));
// ...

بحكم أنّ للكائنات الدالية هويّتها الخاصة، فلا يمكن وضعها في التعريفات النوعية typedef، ويجب قبولها عبر وسيط القالب. يمكن أن يكون تعريف ‎std::find_if‎ على الشكل التالي:

template < typename Iterator, typename Predicate >
Iterator find_if(Iterator begin, Iterator end, Predicate &predicate) {
        for (Iterator i = begin, i != end, ++i)
            if (predicate( *i))
                return i;
        return end;
    }