Рекурсія у

Про концепцію Рекурсія

Рекурсивні функції - це функції, які викликають самі себе.

Рекурсивна функція повинна мати щонайменше один базовий випадок і щонайменше один рекурсивний випадок.

Базовий випадок повертає значення, не викликаючи функцію знову. Рекурсивний випадок знову викликає функцію, змінюючи вхідні дані так, щоб вони в якийсь момент відповідали базовому випадку.

Ось приклад, який рахує елементи масиву.

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