Рекурсия: Зеркало в зеркале

В функциональных языках, таких как Лиспекс, итерации и циклы обычно реализуются с помощью рекурсии. Это руководство научит вас, что такое рекурсия, и как писать собственные рекурсивные функции для решения распространенных задач.

Что такое рекурсия?

Рекурсия — это простая, но мощная идея: функция, которая вызывает сама себя.

Чтобы функция не вызывала себя бесконечно, рекурсивная функция должна иметь две ключевые части:

1. Базовый случай (Base Case): Условие, которое сообщает функции, когда прекратить рекурсию.
2. Рекурсивный шаг (Recursive Step): Часть, где функция вызывает саму себя, но с немного измененными входными данными, которые приближают ее к базовому случаю.

Давайте посмотрим на это в действии на классическом примере.

Пример 1: Вычисление факториала

Факториал числа n (записывается как n!) — это произведение всех положительных целых чисел до n включительно. Например, 5! = 5 * 4 * 3 * 2 * 1 = 120.

Вот рекурсивная функция на Лиспексе для вычисления факториала:

(define (factorial n)
  (if (<= n 1)
      1
      (* n (factorial (- n 1)))))

(factorial 5)  ; ⇒ 120

Как это работает

Когда мы вызываем (factorial 3), вот что делает интерпретатор:

1. 3 <= 1? Нет. Следовательно, вычисляем (* 3 (factorial 2)).
2. Для этого нужно вычислить (factorial 2). 2 <= 1? Нет. Следовательно, вычисляем (* 2 (factorial 1)).
3. Для этого нужно вычислить (factorial 1). 1 <= 1? Да. Он достигает базового случая и возвращает 1.
4. Теперь он может решить шаг 2: (* 2 1) равно 2.
5. Теперь он может решить шаг 1: (* 3 2) равно 6.

Конечный результат — 6.

Пример 2: Рекурсия по списку

Рекурсия — это основной способ "пройтись циклом" по списку в Лиспексе. Распространенный шаблон — обработать первый элемент, а затем рекурсивно вызвать функцию для остальной части списка.

Давайте напишем функцию для суммирования всех чисел в списке.

(define (sum-list lst)
  (if (empty? lst)
      0
      (+ (list-first lst) (sum-list (list-rest lst)))))

(sum-list (list 10 20 30))  ; ⇒ 60

Как это работает

1. sum-list вызывается со списком (list 10 20 30).
2. Список не пуст, поэтому вычисляется (+ 10 (sum-list (list 20 30))).
3. sum-list вызывается со списком (list 20 30).
4. Список не пуст, поэтому вычисляется (+ 20 (sum-list (list 30))).
5. sum-list вызывается со списком (list 30).
6. Список не пуст, поэтому вычисляется (+ 30 (sum-list (list))).
7. sum-list вызывается с пустым списком (). Он достигает базового случая и возвращает 0.
8. Затем результаты "всплывают": (+ 30 0) равно 30, (+ 20 30) равно 50, и, наконец, (+ 10 50) равно 60.

Замечание о хвостовой рекурсии

При очень глубокой рекурсии (например, (factorial 10000)) простой рекурсивный шаблон может иногда приводить к ошибке, называемой "переполнение стека". Для решения этой проблемы можно использовать технику, известную как хвостовая рекурсия (tail recursion).

Функция является хвостово-рекурсивной, если рекурсивный вызов — это самое последнее действие, которое она выполняет. Это позволяет интерпретатору Лиспекс выполнить оптимизацию (оптимизация хвостового вызова, Tail Call Optimization), чтобы избежать ошибок переполнения стека. Это часто достигается с помощью переменной-"аккумулятора".

Вот хвостово-рекурсивная версия нашей функции факториала:

(define (factorial n)
  (let ((factorial-helper (lambda (n acc)
                             (if (<= n 1)
                                 acc
                                 (factorial-helper (- n 1) (* acc n))))))
    (factorial-helper n 1)))

(factorial 5)  ; ⇒ 120 (хвостовая рекурсия)

Заключение

Рекурсия — это фундаментальная концепция в Лиспексе. Понимая базовый случай и рекурсивный шаг, вы можете выполнять любые виды итераций или циклов чистым, функциональным способом.

Теперь попробуйте написать свою собственную рекурсивную функцию! Например, сможете ли вы написать функцию my-length, которая рекурсивно вычисляет длину списка?