C: الدوال — المتقدمة

العودية كمرآتين متقابلتين — صور تتداخل ضمن صور حتى يختفي ضوء البعيد. دالة تستدعي نفسها تحل المشكلات عبر قوة الاختزال التدريجي.

1. مبادئ العودية

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

1. الشرط العودي： يمكن تفكيك المشكلة إلى مشكلات فرعية أصغر من نفس النوع
2. حالة الأساس (شرط الإنهاء)： المشكلة الفرعية الأصغر لها إجابة مباشرة ولا تستدعي بشكل عودي بعد ذلك

int factorial(int n) {
    if (n <= 1) {
        return 1;
    }
    return n * factorial(n - 1);
}

خذ factorial(4) كمثال، عملية التنفيذ：

factorial(4)
= 4 * factorial(3)
= 4 * 3 * factorial(2)
= 4 * 3 * 2 * factorial(1)
= 4 * 3 * 2 * 1
= 24

2. أمثلة العودية الكلاسيكية

(1) المضروب

تعريف مضروب n： n! = n x (n-1)!، و 0! = 1.

long factorial(int n) {
    if (n <= 1) return 1;
    return n * factorial(n - 1);
}

لاحظ أن نوع long له نطاق محدود؛ factorial(20) قريب بالفعل من حد 64 بت.

(2) متتالية فيبوناتشي

تعريف فيبوناتشي： F(1)=1, F(2)=1, F(n)=F(n-1)+F(n-2).

long fib(int n) {
    if (n <= 2) return 1;
    return fib(n - 1) + fib(n - 2);
}

(3) أبراج هانوي

انقل n أقراص من العمود A إلى العمود C، باستخدام العمود B كمساعد. القاعدة： لا يمكن وضع قرص أكبر على قرص أصغر.

#include <stdio.h>

void hanoi(int n, char from, char mid, char to) {
    if (n == 1) {
        printf("%c -> %c\n", from, to);
        return;
    }
    hanoi(n - 1, from, to, mid);
    printf("%c -> %c\n", from, to);
    hanoi(n - 1, mid, from, to);
}

int main(void) {
    hanoi(3, 'A', 'B', 'C');
    return 0;
}

A -> C
A -> B
C -> B
A -> C
B -> A
B -> C
A -> C

الفكرة： انقل أولًا n-1 أقراص علوية إلى العمود المساعد، ثم انقل أكبر قرص إلى العمود الهدف، ثم انقل n-1 قرصًا من العمود المساعد إلى العمود الهدف. 3 أقراص تتطلب 7 نقلات； n قرصًا تتطلب 2^n - 1 نقل.

▶ مثال

حساب مجموع أرقام عدد صحيح بشكل عودي：

#include <stdio.h>

int digit_sum(int n) {
    if (n < 10) return n;
    return n % 10 + digit_sum(n / 10);
}

int main(void) {
    printf("%d\n", digit_sum(12345));
    printf("%d\n", digit_sum(7));
    return 0;
}

15
7

digit_sum(12345) = 5 + digit_sum(1234) = 5 + 4 + digit_sum(123) = ... = 5+4+3+2+1 = 15.

3. نطاق المتغيرات

يحدد النطاق أي مناطق من الكود يمكنها رؤية متغير واستخدامه.

(1) نطاق الكتلة

المتغيرات المعرّفة داخل {} مرئية فقط داخل تلك الكتلة وتُدمَّر عند انتهاء الكتلة：

int main(void) {
    int x = 10;
    {
        int y = 20;
        printf("%d %d\n", x, y);
    }
    printf("%d\n", x);
    return 0;
}

y موجود فقط في الكتلة الداخلية ولا يمكن الوصول إليه من الكتلة الخارجية.

(2) نطاق الملف

المتغيرات المعرّفة خارج جميع الدوال لها نطاق ملف وهي مرئية من نقطة تعريفها حتى نهاية الملف. تُسمّى المتغيرات العامة：

int count = 0;

void increment(void) {
    count++;
}

int main(void) {
    increment();
    increment();
    printf("%d\n", count);
    return 0;
}

(3) حجب الاسم

المتغير في نطاق داخلي يحجب متغيرًا بنفس الاسم في نطاق خارجي：

int x = 100;

int main(void) {
    int x = 10;
    printf("%d\n", x);
    return 0;
}

المخرجات 10؛ x الداخلية تحجب x العامة. لا يمكن الوصول إلى x العامة مباشرة داخل الكتلة الداخلية.

4. فئات التخزين

تحدد فئات التخزين مدة حياة المتغير ومرئيته. في C أربع كلمات مفتاحية لفئات التخزين： auto و static و extern و register.

(1) auto

auto هي فئة التخزين الافتراضية للمتغيرات المحلية وتُحذف عادةً. تُنشأ المتغيرات عند دخول الكتلة وتُدمَّر عند الخروج منها：

void func(void) {
    auto int x = 10;
}

هذا يكافئ int x = 10;.

(2) static

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

#include <stdio.h>

void counter(void) {
    static int count = 0;
    count++;
    printf("Call #%d\n", count);
}

int main(void) {
    counter();
    counter();
    counter();
    return 0;
}

Call #1
Call #2
Call #3

بدون static، ستُعاد تهيئة count إلى 0 في كل مرة، وتطبع دائمًا "Call #1".

عندما يُعدِّل static متغيرًا عامًا أو دالة، يقيد مرئيته على الملف الحالي (ربط داخلي)؛ لا يمكن للملفات المصدرية الأخرى الوصول إليه عبر extern.

(3) extern

تُصرِّح extern عن متغير عام مُعرَّف في ملف مصدري آخر، وتُخبر المترجم "هذا المتغير موجود، لكنه غير مُعرَّف في الملف الحالي"：

file1.c：

int shared_data = 42;

file2.c：

#include <stdio.h>

extern int shared_data;

int main(void) {
    printf("%d\n", shared_data);
    return 0;
}

extern لا تخصص ذاكرة؛ هي تصريح فقط. المشاريع متعددة الملفات تحتاج extern لمشاركة البيانات العامة.

(4) register

تُقترح register على المترجم تخزين المتغير في سجل المعالج للوصول الأسرع：

void fast_loop(void) {
    register int i;
    for (i = 0; i < 1000000; i++) {
    }
}

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

▶ مثال

فيبوناتشي التكرارية باستخدام حلقة (تجنب الحساب المتكرر للعودية)：

#include <stdio.h>

long fib_iter(int n) {
    if (n <= 2) return 1;
    long prev = 1;
    long curr = 1;
    long next;
    int i;

    for (i = 3; i <= n; i++) {
        next = prev + curr;
        prev = curr;
        curr = next;
    }
    return curr;
}

int main(void) {
    int i;
    for (i = 1; i <= 10; i++) {
        printf("F(%d) = %ld\n", i, fib_iter(i));
    }
    return 0;
}

F(1) = 1
F(2) = 1
F(3) = 2
F(4) = 3
F(5) = 5
F(6) = 8
F(7) = 13
F(8) = 21
F(9) = 34
F(10) = 55

هذه النسخة التكرارية لها تعقيد زمني O(n)، أفضل بكثير من O(2^n) للعودية الساذجة.

❓ أسئلة شائعة

📖 ملخص

• العودية يجب أن تتضمن حالة أساس، وإلا سيفيض المكدس
• عودية فيبوناتشي الساذجة غير فعّالة؛ المشكلات الحقيقية تحتاج حلقات أو حفظ نتائج
• المتغيرات المحلية لها نطاق كتلة؛ والمتغيرات العامة لها نطاق ملف
• المتغيرات المحلية static تستمر طوال البرنامج، لكن نطاقها يظل كما هو
• extern تتيح مشاركة المتغيرات بين الملفات؛ register ليس له أهمية تُذكر في المترجمات الحديثة

📝 تمارين

1. اكتب دالة عودية void print_reverse(int n) تطبع أرقام عدد صحيح موجب بترتيب عكسي (مثلًا： 123 تُخرج 3 2 1).
2. اكتب دالة تستخدم متغير static لعدّ عدد مرات استدعائها. استدعها 5 مرات في main، ثم اطبع العدد.
3. نفّذ البحث الثنائي بشكل عودي： ابحث عن قيمة هدف في مصفوفة مرتّبة؛ أرجع الدليل إذا وُجدت، أو -1 إذا لم تُوجد.

فريق Web-Tutorial التقني

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

من نحن