Рекурсия: let rec и хвостовые вызовы

Осваиваем главный инструмент повторения в функциональном языке — рекурсию, и её эффективную форму с хвостовыми вызовами.

Хвостовая рекурсия — рекурсия, где рекурсивный вызов является самым последним действием функции, что позволяет компилятору выполнить её без роста стека.

В функциональном стиле циклы часто заменяются рекурсией: вместо изменяемого счётчика мы описываем задачу через саму себя на меньших данных. OCaml поддерживает циклы, но идиоматичный способ обхода данных — рекурсия, и важно понимать её устройство, чтобы не упереться в переполнение стека.

Ключевое слово rec

let rec factorial n =
  if n <= 1 then 1
  else n * factorial (n - 1)
(* factorial 5 = 120 *)

Без rec имя factorial внутри тела ещё не было бы видно. Это сознательное решение языка: по умолчанию let не рекурсивен.

Проблема глубокой рекурсии

В factorial выше после рекурсивного вызова остаётся работа — умножение на n. Значит, каждый вызов держит на стеке свой кадр. Для больших n это переполнит стек. Решение — аккумулятор: накапливаем результат в дополнительном параметре, и рекурсивный вызов становится последним действием.

let factorial n =
  let rec loop acc i =
    if i <= 1 then acc
    else loop (acc * i) (i - 1)   (* хвостовой вызов *)
  in
  loop 1 n

Здесь loop (acc * i) (i - 1) — последнее, что делает функция. Это и есть хвостовой вызов.

Как работает под капотом

Когда рекурсивный вызов стоит в хвостовой позиции, текущий кадр стека больше не нужен. Компилятор OCaml выполняет оптимизацию хвостового вызова: переиспользует текущий кадр, превращая рекурсию в цикл. Поэтому хвостовая версия работает с любым n в постоянной памяти стека, тогда как нехвостовая «съест» стек на больших значениях с исключением Stack_overflow. Различить легко: если после рекурсивного вызова есть хоть одна операция, вызов не хвостовой.

(* Нехвостовая: после вызова есть «1 +»  *)
let rec length = function
  | [] -> 0
  | _ :: t -> 1 + length t

(* Хвостовая: вызов — последнее действие *)
let length lst =
  let rec loop acc = function
    | [] -> acc
    | _ :: t -> loop (acc + 1) t
  in loop 0 lst

Взаимная рекурсия

let rec is_even n = if n = 0 then true else is_odd (n - 1)
and is_odd n = if n = 0 then false else is_even (n - 1)

Частые ошибки

Забыть rec. Тогда компилятор скажет, что имя функции не определено внутри тела.
Считать любую рекурсию хвостовой. Если результат вызова ещё участвует в вычислении — она не хвостовая.
Бояться рекурсии из-за производительности. Хвостовая рекурсия компилируется в цикл.

Итоги

Рекурсивные функции требуют let rec; взаимная рекурсия — let rec ... and ....
Хвостовой вызов — последнее действие функции; такую рекурсию компилятор превращает в цикл.
Аккумулятор делает рекурсию хвостовой и безопасной для больших данных.