أساسيات الاستدعاء الذاتي

جزء من قسم Fundamentals في رحلة C على Coddy — الدرس 50 من 63.

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

لنلقِ نظرة على دالة عودية بسيطة تحسب المضروب (factorial):

int factorial(int n) {
    // الحالة الأساسية: مضروب 0 أو 1 هو 1
    if (n <= 1) {
        return 1;
    }
    
    // الحالة العودية: n! = n * (n-1)!
    return n * factorial(n - 1);
}

تحتاج كل دالة عودية إلى:

حالة أساسية لإيقاف العودية
حالة عودية تقترب من الحالة الأساسية

على سبيل المثال، حساب factorial(3):

factorial(3) يستدعي factorial(2)
factorial(2) يستدعي factorial(1)
factorial(1) يعيد 1 (الحالة الأساسية)

factorial(2) يُرجع 2 * 1 = 2
factorial(3) يُرجع 3 * 2 = 6

التحدي

سهل

أنشئ دالة باسم sumToN تستخدم العودية (recursion) لحساب مجموع الأرقام من 1 إلى n.

على سبيل المثال:

sumToN(3) يجب أن تعيد 6 (1 + 2 + 3)
sumToN(5) يجب أن تعيد 15 (1 + 2 + 3 + 4 + 5)

يجب أن تقوم دالتك بما يلي:

استخدام حالة أساسية (base case) عندما تكون n هي 1 (إرجاع 1)
خلاف ذلك، إرجاع n زائد مجموع الأرقام من 1 إلى (n-1)

ورقة مرجعية

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

تحتاج كل دالة عودية إلى:

حالة أساسية (base case) لإيقاف العودية
حالة عودية (recursive case) تنتقل نحو الحالة الأساسية

مثال - دالة المضروب (factorial):

int factorial(int n) {
    // الحالة الأساسية: مضروب 0 أو 1 هو 1
    if (n <= 1) {
        return 1;
    }
    
    // الحالة العودية: n! = n * (n-1)!
    return n * factorial(n - 1);
}

كيفية تنفيذ factorial(3):

factorial(3) يستدعي factorial(2)
factorial(2) يستدعي factorial(1)
factorial(1) يعيد 1 (الحالة الأساسية)
factorial(2) يعيد 2 * 1 = 2
factorial(3) يعيد 3 * 2 = 6

جرّب بنفسك

#include <stdio.h>

// اكتب دالة sumToN الخاصة بك هنا

// لا تقم بتغيير دالة main()
int main() {
    int n;
    scanf("%d", &n);
    
    printf("%d", sumToN(n));
    return 0;
}