Рекурсивні функції

Рекурсія

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

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

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

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

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(...)]. Під капотом деякі вбудовані функції реалізовано через рекурсію.