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

نبذة عن الاستدعاء الذاتي

القدرة على تعريف شيء ما بدلالة نفسه تُسمى العودية. وفي F#، تظهر العودية غالبًا في الدوال العودية، وهي دوال تستدعي نفسها.

تحتاج الدالة العودية إلى حالة أساسية واحدة على الأقل وإلى حالة عودية واحدة على الأقل. الحالة الأساسية تُرجع قيمة دون استدعاء الدالة مرة أخرى. أما الحالة العودية فتستدعي الدالة مرة أخرى، مع تعديل المدخل بحيث يطابق الحالة الأساسية في مرحلة ما.

تُعرَّف الدوال العودية مثل الدوال العادية، لكن مع المعدِّل rec. وبدون هذا المعدِّل، لن تتمكن الدالة من استدعاء نفسها، وأي محاولة لفعل ذلك ستؤدي إلى خطأ في التصريف. لذلك يجب اختيار العودية صراحةً.

let rec factorial x =
    // Base case
    if x = 1 then
        1
    // Recursive case
    else
        x * factorial (x - 1)

غالبًا ما تُعالَج القوائم بشكل عودي. على سبيل المثال، إليك كيفية استخدام العودية لحساب طول قائمة:

let rec length list =
    match list with
    | [] -> 0
    | x::xs -> 1 + length xs

length [1; 2; 3]
// => 3

كثير من الدوال المدمجة مُعرَّفة عوديًا.

من المشكلات المحتملة في الدوال العودية أن كل استدعاء (عودي) للدالة يؤدي إلى تخصيصات على المكدس، فيجعله ينمو. ولأن المكدس يمتلك قدرًا محدودًا من الذاكرة، فقد تتسبب الدوال التي تستخدم عددًا كبيرًا من الاستدعاءات العودية في إطلاق StackOverflowException. ويعتمد عدد الاستدعاءات العودية التي تحفّز هذا السلوك على عدة عوامل، مثل الذاكرة المتاحة على المكدس ومقدار البيانات التي يشغلها كل استدعاء للدالة على المكدس.

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

إليك نسخة ذات عودية ذيلية من دالة حساب طول القائمة:

let rec lengthRecursive acc list =
    match list with
    | [] -> acc
    | x::xs -> lengthRecursive (acc + 1) xs

let length list = lengthRecursive 0 list

من الشائع جدًا تعريف الدالة المساعدة العودية كدالة متداخلة، وهو ما يخفي الطبيعة العودية للدالة عن المستدعي:

let length list =
    let rec lengthRecursive acc remainder =
        match remainder with
        | [] -> acc
        | x::xs -> lengthRecursive (acc + 1) xs

    lengthRecursive 0 list

يدعم F# الأنواع العودية من خلال أنواع الاتحاد المميّز. في نوع الاتحاد المميّز العودي، تشير حالة واحدة أو أكثر من حالاته إلى نوع الاتحاد المميّز نفسه في بياناتها. ومثل الدوال العودية، يجب أن تمتلك الأنواع العودية حالة أساسية. وبخلاف الدوال العودية، لا تستخدم الأنواع العودية الكلمة المفتاحية rec.

type RussianDoll =
    | Doll                 // Base case
    | Layer of RussianDoll // Recursive case

إليك دالة (ليست ذات عودية ذيلية) للتعامل مع النوع العودي أعلاه:

let layers doll =
    match doll with
    | Doll -> 0 // Base case
    | Layer innerDoll -> 1 + layers innerDoll // Recursive case

layers (Layer Doll)
// => 1