الدوال العودية

العودية

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

تحتاج الدالة العودية إلى حالة أساسية واحدة على الأقل وإلى حالة عودية واحدة على الأقل.

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

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

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(...)]. وفي الخلفية، تُنفَّذ بعض الدوال المدمجة باستخدام العودية.