توابع بازگشتی

بازگشت

«توابع بازگشتی» توابعی هستند که خودشان را فراخوانی می‌کنند.

یک تابع بازگشتی باید دست‌کم یک «حالت پایه» و دست‌کم یک «حالت بازگشتی» داشته باشد.

یک حالت پایه مقداری را برمی‌گرداند بدون اینکه تابع را دوباره فراخوانی کند. یک حالت بازگشتی تابع را دوباره فراخوانی می‌کند و ورودی را طوری تغییر می‌دهد که در نقطه‌ای با حالت پایه مطابقت پیدا کند.

در اینجا مثالی را می‌بینید که عنصرهای یک آرایه را می‌شمارد.

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(...)]. در لایه‌های زیرین، بعضی از توابع داخلی با بازگشت پیاده‌سازی شده‌اند.