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

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

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

يجب أن تحتوي الدالة العودية على حالة أساسية واحدة على الأقل و_حالة عودية_ واحدة على الأقل.

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

إليك مثالًا يحصي عناصر مصفوفة.

def count:
  if length == 0 then
    0                       # base case
  else
    1 + (.[1:] | count)     # recursive case
  end;

([] | count),           # => 0
([11, 22, 33] | count)  # => 3

يمكن أن تحتوي الدالة العودية على حالات أساسية متعددة و/أو حالات عودية متعددة. على سبيل المثال، متتالية فيبوناتشي هي متتالية عودية ذات حالتين أساسيتين.

def fibonacci:
  if . == 0 then
    0
  elif . == 1 then
    1
  else
    (. - 1 | fibonacci) + (. - 2 | fibonacci)
  end;

10 | fibonacci          # => 55

يتضمّن عدّ عدد مرات ظهور قيمة معطاة x في مصفوفة حالتين عوديتين.

def count_occurrences(x):
  if length == 0 then
    0
  elif first == x then
    1 + (.[1:] | count_occurrences(x))
  else
    (.[1:] | count_occurrences(x))
  end;

[11, 22, 33, 22, 44] | count_occurrences(22)    # => 2

في الممارسة العملية، غالبًا ما يتم التكرار على المصفوفات وبُنى البيانات الأخرى القابلة للتعداد باستخدام دوال مدمجة، مثل map و reduce، أو باستخدام التدفقات مثل [.[] | select(...)]. خلف الكواليس، بعض الدوال المدمجة مُنفَّذة باستخدام العَودية.

العَودية اللانهائية

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

قد تنتج مشكلة العَودية اللانهائية هذه عن:

• نسيان تنفيذ حالة أساسية.
• عدم تعريف الحالة الأساسية كأول شرط.
• عدم تعديل الوسيط بشكل صحيح عند إجراء الاستدعاء العودي، وبالتالي عدم الوصول إلى الحالة الأساسية أبدًا.

تحسين الاستدعاء الذيلي

كما هو موضح في ويكيبيديا:

الاستدعاء الذيلي هو استدعاء روتين فرعي يتم كإجراء أخير في إجراء. إذا كان هدف الاستدعاء الذيلي هو الروتين الفرعي نفسه، فيقال إن الروتين الفرعي عودي ذيلي.

لنتأمل تنفيذ fibonacci الوارد أعلاه. تستدعي الحالة العودية نفسها مرتين. الإجراء الأخير الذي تحتاج الدالة إلى تنفيذه هو الجمع. ولأن الإجراء الأخير ليس استدعاءً لنفسها، فإن تلك الدالة عودية، لكنها ليست عودية ذيلية.

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

تُطبّق jq تحسين الاستدعاء الذيلي، لكن فقط للدوال التي لا تستقبل وسائط. طريقة الاستفادة من ذلك هي تعريف دالة «داخلية» لا تستقبل وسائط، تأخذ نوعًا ما من الحالة كمدخل. يمكن للدالة الداخلية تعديل الحالة حسب الحاجة، وتمرير الحالة الجديدة إلى الاستدعاء العودي الذيلي. تنشئ الدالة الخارجية الحالة الأولية وتمررها إلى الدالة الداخلية لبدء العَودية.

يمكن تنفيذ دالة fibonacci عودية ذيلية بالاحتفاظ بالمتسلسلة المحسوبة حتى الآن كجزء من الحالة.

def fibonacci:
  def _fib:
    # input: {limit: number, series: array}
    if (.series | length - 1) >= .limit then
      .series[.limit]                                   # base case
    else
      .series += [.series[-1] + .series[-2]] | _fib     # recursive case
    end;
  {limit: ., series: [0, 1]} | _fib;

10 | fibonacci          # => 55