الدّالّة (6) - Recursion 1

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

قد يكون من الصعب فهم الـ Recursion في البداية، ولكنها أداة قوية يمكن استخدامها لحل مجموعة واسعة من المشكلات.

فيما يلي مثال لدالّة Recursion بسيطة في لغة C++:

#include <iostream>
using namespace std;
void f(int n)
{
    if (n < 1)
        return;
    else
        cout << "round:" << n << endl;
    f(n - 1);
}

int main()
{
    f(5);
    return 0;
}

الدالة f(int n) هي دالة recursive تقوم بطباعة السلسلة "round:" متبوعة بالعدد الصحيح n إلى شاشة المخرجات n من المرات.

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

المخرجات:

round: 5
round: 4
round: 3
round: 2
round: 1

يمكن أن يكون من الصعب قليلًا فهم دوال الـ Recursive في البداية، ولكنها أداة قوية يمكن استخدامها لحل مجموعة واسعة من المشكلات.

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

void f(int n)
{
    if (n < 1)
        return; //base case
    else
        cout << "round:" << n << endl; //logic
    f(n - 1); //subproblem
}

المحتويات الثلاثة لدالة الـrecursive هي:

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

فيما يلي مثال على دالة recursive في لغة C++‎ تحسب مضروب الرقم:

#include <iostream>
using namespace std;
int fact(int n)
{
    if (n == 0 || n == 1)
        return 1;
    else
        return n*fact(n - 1);
}

int main()
{
    cout << fact(5) << endl;
    return 0;
}

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ...

F(n) = F(n - 1) + F(n - 2)

#include <iostream>
using namespace std;
int fib(int n)
{
    if (n == 0 || n == 1)
        return n;
    else
        return fib(n - 1) + fib(n - 2);
}

int main()
{
    cout << fib(3) << endl;
    return 0;
}

2