بازگشت در

درباره‌ی بازگشت

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

یک تابع بازگشتی باید حداقل یک حالت پایه و حداقل یک حالت بازگشتی داشته باشد.

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

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

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