الاستدعاء الذاتي في لغة C: الحالات الأساسية والعاملي وعمق المكدّس

دالة تستدعي نفسها

لا شيء يمنع دالة C من استدعاء نفسها. فاسمها موجود ضمن النطاق داخل جسمها، وهذا مشروع:

void countdown(int n) {
    printf("%d\n", n);
    countdown(n - 1);      /* تستدعي نفسها - لكنها لا تتوقّف أبدًا! */
}

وهي أيضًا معطوبة. تطبع إلى الأبد، ثم إلى الأعداد السالبة، حتى ينهار البرنامج. وما ينقصها هو حالة أساسية: شرط تُرجِع الدالة عنده دون أن تستدعي نفسها.

#include <stdio.h>

void countdown(int n) {
    if (n <= 0) {              /* الحالة الأساسية: توقّف */
        printf("Liftoff!\n");
        return;
    }
    printf("%d\n", n);
    countdown(n - 1);          /* الحالة التكرارية: مشكلة أصغر */
}

int main(void) {
    countdown(5);
    return 0;
}

لكل دالة تكرارية ذاتيًا هذان الجزءان بالضبط:

• حالة أساسية - أصغر مدخل، يُجاب عنه مباشرةً، دون استدعاء آخر.
• حالة تكرارية - تحلّ المشكلة بدلالة نسخة أصغر حتمًا من نفسها.

و"أصغر حتمًا" هو الجزء الذي يخطئ فيه الناس. فـ countdown(n - 1) تتحرّك نحو 0 في كل استدعاء. أما countdown(n) فلا، ولا countdown(n / 2) لو كان بإمكان n أن تظلّ 1 إلى الأبد. يجب أن يقلّص كل مسار المشكلةَ، وإلا لن تُبلَغ الحالة الأساسية أبدًا.

العاملي

المثال الأول المعياري. n! هو n × (n-1) × ... × 1، و0! معرَّف بأنه 1. وذلك التعريف تكراري ذاتيًا سلفًا: n! = n × (n-1)!.

#include <stdio.h>

unsigned long long factorial(int n) {
    if (n <= 1) {                       /* الحالة الأساسية: 0! و1! كلاهما 1 */
        return 1;
    }
    return n * factorial(n - 1);        /* الحالة التكرارية */
}

int main(void) {
    for (int i = 0; i <= 10; i++) {
        printf("%2d! = %llu\n", i, factorial(i));
    }
    printf("20! = %llu\n", factorial(20));
    return 0;
}

تتبّع factorial(4) لترى كيف تُركَّب الإجابة. تنزل الاستدعاءات، وتقع عمليات الضرب في طريق الصعود:

factorial(4)  -> 4 * factorial(3)
                      factorial(3) -> 3 * factorial(2)
                                           factorial(2) -> 2 * factorial(1)
                                                                factorial(1) -> 1   (base case)
                                           factorial(2) = 2 * 1  = 2
                      factorial(3) = 3 * 2  = 6
factorial(4)  = 4 * 6  = 24

لا يُضرَب شيء حتى تُرجِع الحالة الأساسية. وينتظر كل استدعاء معلّق، محتفظًا بقيمة n الخاصة به، وهذه هي النقطة الجديرة بالاستيعاب: تلك الاستدعاءات المنتظرة تشغل ذاكرة.

لاحظ نوع الإرجاع. يفيض int عند 13! تقريبًا، فيُنتج عددًا خاطئًا بصمت - ولا تفحص C ذلك. ويوصلك unsigned long long إلى 20! ولا أبعد، لأن 21! يتجاوز 64 بتًا. والاستدعاء الذاتي ليس العامل المقيِّد هنا؛ بل النوع.

وتستخدم الحالة الأساسية n <= 1 بدل n == 1 عن قصد: فـ factorial(0) ينبغي أن تساوي 1، و<= تعالج ذلك. ومع n == 1، كان استدعاء factorial(0) سيتكرّر إلى -1 و-2 ولن ينتهي أبدًا - وهو توضيح جيد لكيف يمكن لحالة أساسية "صحيحة بداهةً" أن تُغفل مدخلًا.

فيبوناتشي ولماذا تكون الصيغة الساذجة فخًّا

فيبوناتشي هو الكلاسيكي الآخر: كل عدد هو مجموع العددين اللذين قبله، بدءًا من 0 و1. والتعريف التكراري الذاتي يكتب نفسه.

#include <stdio.h>

long long calls = 0;

int fib(int n) {
    calls++;
    if (n < 2) {
        return n;                       /* fib(0) = 0, fib(1) = 1 */
    }
    return fib(n - 1) + fib(n - 2);
}

int main(void) {
    for (int n = 10; n <= 35; n += 5) {
        calls = 0;
        int result = fib(n);
        printf("fib(%2d) = %-8d (%lld calls)\n", n, result, calls);
    }
    return 0;
}

انظر إلى أعداد الاستدعاءات. تستغرق fib(10) مئة وسبعة وسبعين استدعاءً؛ وتستغرق fib(35) نحو ثلاثين مليونًا. وكل خطوة بمقدار 5 تضاعف العمل نحو إحدى عشرة مرة.

والسبب مرئي في شجرة الاستدعاءات. تستدعي fib(5) كلًّا من fib(4) وfib(3)؛ وتستدعي fib(4) الدالة fib(3) مرة أخرى؛ وكل واحدة منها تعيد حساب fib(2) من الصفر. ولا يُحفظ شيء، فتُحلّ المسائل الفرعية نفسها مرارًا، وينمو عدد الاستدعاءات نحو 1.6ⁿ تقريبًا. وبهذه الطريقة ستعمل fib(50) أيامًا؛ وfib(100) ستعمّر أطول من الكون.

أما صيغة الحلقة فتحتفظ بالقيمتين الأخيرتين وهي خطّية:

#include <stdio.h>

long long fibFast(int n) {
    if (n < 2) {
        return n;
    }
    long long prev = 0, curr = 1;
    for (int i = 2; i <= n; i++) {
        long long next = prev + curr;
        prev = curr;
        curr = next;
    }
    return curr;
}

int main(void) {
    for (int n = 10; n <= 90; n += 10) {
        printf("fib(%2d) = %lld\n", n, fibFast(n));
    }
    return 0;
}

تُرجِع fib(90) فورًا. والدرس ليس "الاستدعاء الذاتي بطيء" - بل أن الاستدعاء الذاتي مع مسائل فرعية متداخلة بطيء ما لم تحفظ الإجابات. خزّن النتائج في مصفوفة أثناء حسابها (التحفيظ) فتصبح الصيغة التكرارية الذاتية خطّية أيضًا.

مكدّس الاستدعاءات وفيضان المكدّس

يحتاج كل استدعاء دالة إلى مكان يحفظ فيه وسائطه ومتغيّراته المحلّية والعنوان الذي يعود إليه. وذلك التخزين هو إطار المكدّس، يُدفَع عند بدء الاستدعاء ويُسحَب عند عودته. والاستدعاء الذاتي يكدّس الإطارات واحدًا فوق الآخر - فلدى factorial(1000) ألف إطار حيّ في آن واحد، لكلٍّ منها قيمة n خاصة به.

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

Segmentation fault (core dumped)

ذلك هو فيضان المكدّس، وهناك طريقتان للوقوع فيه:

الاستدعاء الذاتي اللانهائي - حالة أساسية غائبة أو يتعذّر بلوغها. وهذا خطأ، والانهيار فوري:

int bad(int n) {
    return bad(n - 1);      /* no base case - crashes in a fraction of a second */
}

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

وتستطيع بعض المترجمات تحويل الاستدعاء الذاتي الذيلي - حيث يكون الاستدعاء الذاتي آخر ما تفعله الدالة، دون عمل معلّق بعده - إلى حلقة، بإعادة استخدام إطار واحد. فـ countdown أعلاه ذيلية؛ أما factorial فلا، لأن الضرب ما زال يجب أن يقع بعد عودة الاستدعاء. لكن C لا توجب هذا التحسين، فقد يحدث وقد لا يحدث تبعًا للمترجم والرايات. لا تكتب أبدًا شيفرة C لا تعمل إلا لأن المحسِّن ألغى استدعاءً ذيليًا.

أين يفوز الاستدعاء الذاتي فعلًا

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

والبحث الثنائي مثال نظيف: ابحث في النصف، ثم في نصف ذلك النصف.

#include <stdio.h>

/* تُرجِع فهرس الهدف، أو -1 */
int binarySearch(const int a[], int low, int high, int target) {
    if (low > high) {
        return -1;                          /* الحالة الأساسية: لم يبقَ شيء */
    }
    int mid = low + (high - low) / 2;       /* يتجنّب الفيضان مع الفهارس الكبيرة */

    if (a[mid] == target) {
        return mid;                         /* الحالة الأساسية: وُجد */
    }
    if (a[mid] < target) {
        return binarySearch(a, mid + 1, high, target);
    }
    return binarySearch(a, low, mid - 1, target);
}

int main(void) {
    int sorted[] = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91};
    int n = sizeof(sorted) / sizeof(sorted[0]);

    int targets[] = {23, 2, 91, 50};
    for (int i = 0; i < 4; i++) {
        printf("%2d -> index %d\n", targets[i], binarySearch(sorted, 0, n - 1, targets[i]));
    }
    return 0;
}

حالتان أساسيّتان هنا، وهذا معتاد: واحدة للنجاح وواحدة للاستنفاد. والعمق نحو log₂(n)، فحتى مليار عنصر لا يحتاج إلا إلى ثلاثين إطارًا.

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

استدعاء ذاتي أم حلقة؟

Use a loop when       the problem is linear - counting, summing, scanning
Use recursion when    the data is nested - trees, nested structures, divide and conquer
Rewrite recursion     if the depth can grow with the input size without bound
Never use recursion   when subproblems overlap, unless you memoize

ملاحظتان عمليّتان. تكلّف الاستدعاءات الذاتية أكثر قليلًا من تكرار حلقة - إطار يُدفَع ويُسحَب في كل مرة - فللحلقات الساخنة البسيطة تفوز الصيغة التكرارية في السرعة وفي الذاكرة معًا. والتنقيح مختلف: فأثر المكدّس من استدعاء ذاتي عميق هو مئات الإطارات المتشابهة، فاطبع الوسيط عند الدخول (كما يفعل عدّاد calls أعلاه) حين لا ينتهي شيء ما.

كتابة دالة تكرارية ذاتيًا: قائمة تحقّق

1. جِد الحالة الأساسية أولًا. ما أصغر مدخل، وما إجابته؟ إن لم تستطع تسميتها، فلا يمكن كتابة الدالة.
2. افترض أن الاستدعاء الذاتي يعمل. لا تتتبّعه ذهنيًا - ثق بأن factorial(n - 1) تُرجِع (n-1)! واكتب الخطوة الواحدة التي تحوّلها إلى الإجابة.
3. تحقّق من أن كل مسار يتقلّص. يجب أن يتحرّك كل استدعاء ذاتي نحو الحالة الأساسية لكل مدخل ممكن، بما في ذلك 0 والسوالب.
4. تحقّق من العمق. كم إطارًا سيغوص هذا تقريبًا مع بيانات حقيقية؟ الآلاف مقبولة؛ الملايين لا.
5. تحقّق من التداخل. إن حُسبت المسألة الفرعية نفسها مرتين، فأنت بحاجة إلى تحفيظ أو إلى حلقة.